### Binary Gap

You are to count the number of bits equal to zero in an integer between two bits equal to one. For example The number 529 has binary representation `1000010001` and contains two binary gaps: one of length 4 and one of length 3.

Therefore zeroes after the most significant ‘1’ will not be counted. Any number without a separated ‘string’ of zeroes, **such as any power of two**, should not have any gaps.

Assumptions:

N is an integer within the range [1..2,147,483,647].

The worst-case time complexity should be O(log(N)) .

Programming language used: C/C++

It helps to understand binary representation and the bitwise operator & for my solutions.

**Solution 1 – shift downward**

Shifting 1000010001 down by one bit will equal 0100001000. 1000010001 & 0000000001 is equal to 0000000001 or 1 in decimal. Therefore you exploit this to get your gap ‘ends’ and then count the zeroes inbetween. This will of course alter N, so you may want to use a temporary variable. We use set a boolean to true after our first ‘1’ to skip trailing zeroes.

**Solution 2 – shift upward**

Similarly, rather than shifting down N we shift upward to it with a temporary variable to get our single ‘1’ bits. In my example below I shift up to 2,147,483,647, the maximum value for a signed integer, which we know is the maximum value for N, as this then tests my assumptions. Indeed, when N is this large you **must** use an unsigned counter, otherwise your temp var will always < 2,147,483,647 and you get an infinite loop:

**Solution 3- shift up through all powers of two**

Similarly to above we can move through all powers of two up to the maximum for our integer (which on my machine is 4 bytes x 8 bits = 32 bits) to get our ‘1’s, so that we do not need to bit shift a number at all. The bitwise AND of this number and our input number will indicate the presence of our ‘1’s.