1

Is there a efficient algorithm (besides the naive implementation of looping through all the bits) to efficiently find the start and end index of the longest run of 1-bits in a 32bit or 64bit variable?

vlad_tepesch
  • 6,681
  • 1
  • 38
  • 80
  • possible duplicate of [Finding consecutive bit string of 1 or 0](http://stackoverflow.com/questions/3304705/finding-consecutive-bit-string-of-1-or-0) – 2501 Dec 11 '14 at 10:51
  • You can't have lower complexity than O(num-bits) – 2501 Dec 11 '14 at 11:00
  • I'd vote for "not a duplicate", as "Finding consecutive bit string of 1 or 0" doesn't give an efficient answer to this question. – schnaader Dec 11 '14 at 11:09
  • If you can't apply that code to bits then you should start with something much simpler. – 2501 Dec 11 '14 at 11:10
  • 1
    @2501 this may be theoretically correct, but in practice often the runtime complexity can be less because some bit operations parallelize the processing on multiple positions in the variable. For an example take a look at the ways how to calculate the population count. Theoretically it has O(n) but you do it in much less operations. – vlad_tepesch Dec 11 '14 at 11:42
  • 1
    @2501 come on mate, lighten up. Besides, there is a fundamental difference. You can do math on ints. Usually with this type of question, it is assumed that math on ints takes O(1) per operation, but there are still `n` bits. That's no weirder than the more common model in which operations on O(log n) bits take constant time. – harold Dec 11 '14 at 12:23

1 Answers1

2

It is possible to repeatedly compute x & (x << 1) until the result becomes 0. The number of iterations is the count of highest bits set.

From there, to get the start and end index, looking at the previous to the last iteration gives the start index, adding the count gives the end index.

Citing this answer:

The following is based on the concept that if you AND a bit sequence with a shifted version of itself, you're effectively removing the trailing 1 from a row of consecutive 1's. 

      11101111   (x)
    & 11011110   (x << 1)
    ----------
      11001110   (x & (x << 1)) 
        ^    ^
        |    |
   trailing 1 removed

Repeating this N times will reduce any sequence with N consecutive 1's to 0x00.

Combining all this, example for 11101111:

  11101111  start sequence
& 11011110
----------
  11001110
& 10011100
----------
  10001100
& 00011000
----------
  00001000  previous to last iteration, only 1 bit set, so start index = 5
& 00000000
----------
  00000000  end, 4 iterations, so longest bit set count = 4

=> start index = 5, end index = 5 + 4 = 9

If there are multiple competing runs, there will be multiple set bits in the previous to last iteration, e.g. for 111101111:

  111101111
& 111011110
-----------
  111001110
& 110011100
-----------
  110001100
& 100011000
-----------
  100001000  previous to last iteration, start index can be 1 or 6
& 000000000
-----------
  000000000  end, 4 iterations, so longest bit set count = 4

=> start index = 1 or 6, end index = 1 + 4 = 5 or 6 + 4 = 10
Community
  • 1
  • 1
schnaader
  • 49,103
  • 10
  • 104
  • 136