Binary Gap

January 12, 2018

A binary gap is a sequence of 0-bits between 1-bits in the binary representation of a number. For instance, 2010 = 101002 has a binary gap of length 1 between its first and third bits; the two 0-bits that end the number are not part of a binary gap because there is no trailing 1-bit. Thus, the length of the maximal binary gap in 20 is 1. The length of the maximal binary gap in 52910 = 10000100012 is 4.

Your task is to write a program that finds the length of the maximal binary gap in a number. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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: