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

6 Responses to “Binary Gap”

  1. Paul said

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

    import re
    
    c = re.compile("10+(?=1)")
    
    def bingap(n):
        b = bin(n)[2:]
        match = c.findall(b)
        return max(map(len, match)) - 1 if match else 0
    
  2. matthew said

    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.

    #include <stdint.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <algorithm>
    
    char *binary(uint32_t n, char *s) {
      for (int i = 0; i < 32; i++) {
        s[31-i] = '0' + ((n>>i)&1);
      }
      return s;
    }
    
    int main(int argc, char* argv[]) {
      if (argc < 2) abort();
      uint32_t n = strtoul(argv[1],0,0);
      char buff[33];
      int max = 0;
      n = ~n; // invert as we want runs of zeroes
      while (n != 0) {
        fprintf(stderr,"n=%s\n", binary(n,buff));
        uint32_t t = n|(n-1);     // Extend ones
        uint32_t m = t+1;         // Mask
        uint32_t b = n&~m;        // Block of ones
        n = n-b;
        fprintf(stderr,"t=%s\n", binary(t,buff));
        fprintf(stderr,"m=%s\n", binary(m,buff));
        fprintf(stderr,"b=%s\n", binary(b,buff));
        fprintf(stderr,"\n");
        // Ignore blocks at start or end. Count bits with popcount
        if (!(b&(1|(1L<<31)))) max = std::max(max,__builtin_popcountl(b));
      }
      fprintf(stdout,"%d\n", max);
    }
    
    $ g++ -Wall bgap.cpp -o bgap
    $ ./bgap 529
    n=11111111111111111111110111101110
    t=11111111111111111111110111101111
    m=11111111111111111111110111110000
    b=00000000000000000000000000001110
    
    n=11111111111111111111110111100000
    t=11111111111111111111110111111111
    m=11111111111111111111111000000000
    b=00000000000000000000000111100000
    
    n=11111111111111111111110000000000
    t=11111111111111111111111111111111
    m=00000000000000000000000000000000
    b=11111111111111111111110000000000
    
    4
    
  3. matthew said

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

  4. nobody said

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

  5. Daniel said

    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.

    #include <stdio.h>
    
    int calc_binary_gap(unsigned long x) {
      if (!x) return 0;
      // Remove trailing 0-bits
      x >>= __builtin_ctzl(x);      
      int binary_gap = 0;
      while (1) {
        // Remove trailing 1-bits
        x >>= __builtin_ctzl(~x);
        if (!x) return binary_gap;
        // Count trailing 0-bits
        int current_gap = __builtin_ctzl(x);
        if (current_gap > binary_gap) binary_gap = current_gap;
        // Remove trailing 0-bits
        x >>= current_gap;
      }
    }
    
    int main(void) {
      int binary_gap = calc_binary_gap(529);
      printf("%d\n", binary_gap);
    }
    

    Output:

    4
    
  6. def binary_gap(n, gap=0, maxx=0, closed=0):
    	while n:
    		if n & 1:
    			if closed:
    				maxx = max(maxx, gap)
    				gap = 0
    			else: closed, gap = 1, 0
    		else: gap += 1
    		n >>= 1
    	return maxx
    
    print(binary_gap(529))
        # => 4
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: