## Binary Gap

### January 12, 2018

Here is our solution:

(define (gap n) (while (even? n) (set! n (/ n 2))) (let loop ((n n) (curr 0) (maxi 0)) (cond ((zero? n) maxi) ((even? n) (loop (/ n 2) (+ curr 1) maxi)) (else (loop (quotient n 2) 0 (max curr maxi))))))

The `while`

discards any 0-bits at the end of the number (there are never any 0-bits at the beginning of a number), then the loop counts 0-bits and resets at every 1-bit. Here’s an example:

> (map gap '(9 15 20 529)) (2 0 1 4)

You can run the program at https://ideone.com/DhZwaR.

Advertisements

Pages: 1 2

In Python, using a regular expression with a lookahead for the trailing 1.

That’s more like it, a nice bit twiddling challenge. It seems to be easier to find blocks of ones than blocks of zeroes and once we do, there is the popcount instruction on more modern x86 processors that tells us how long they are (accessible through the __builtin_popcount() intrinsic on gcc). So here’s some C++ code that uses bit-level operations to sequentially find the rightmost sequential block of ones. To solve the original problem we flip the bits at the beginning and use a simple test at the end to filter out blocks that start or end at the start or end of the bit sequence.

Here’s that code in Matthew Godbolt’s excellent online compiler: https://godbolt.org/g/KiXcsm

programmingpraxis, please consider what happens if the function “gap” is called with a value of zero.

Here’s a solution in C.

It removes the trailing 0 bits, then iteratively removes the trailing 1 bits and counts/removes the trailing 0 bits.

gcc’s built-in count-trailing-zeros function, __builtin_ctz is used for counting trailing 0 bits.

Output: