Algorithm
One might consider using a binary search. I have implemented the following algorithm to determine the length of the longest string of 1-bits in a given non-negative integer n. The computational complexity is O(n), but for many values of n it will approach O(log2(n)).
The steps of the algorithm are below, but the reader many find them easier to follow by reading the following section ("Illustration") first.
- Set
longest to 0.
- Set
len equal to the number of bits in n (len = n.bit_length).
- If
len <= 2, return the answer (0, 1 or 2).
- Determine the index
mid of the middle bit of n (mid = len/2 or mid = len >> 1).
- Set
ri = mid+1 and li = mid-1.
- If the value of the middle bit (
n[mid]) is zero go to Step 10.
- (
n[mid] = 1 to reach this step.) Determine the largest index li >= mid and the smallest index ri <= mid such that n[i] = 1 for all ri <= i <= li.
- Set
longest = [longest, ri-li+1].max, li += 1 and ri -= 1.
- If
li == len go to Step 10; else set ln equal to the number comprised of bits at indices li (least significant) to len-1 (most significant). Recursively set to n to ln and go to step 2. This returns the longest string of 1-bits in the number ln (cand). Set longest = [longest, cand].max.
- If
ri < 0 go to Step 11; else set rn equal to the number comprised of bits at indices 0 (least significant) to ri (most significant). Recursively set to n to rn and go to step 2. This returns the longest string of 1-bits in thet number rn (cand). Setlongest = [longest, cand].max`.
- Return
longest in the recursion.
Illustration
Suppose
n = 0b1010011011101011110
#=> 341854
Then
len = n.bit_length
#=> 19
mid = len >> 1
#=> 9
n[mid]
#=> 1
longest = 0
We may picture n as follows
101001101 1 101011110
where the middle bit 1 stands out. Since it is a 1, we look left and right for sequences of 1's. We obtain the following.
10100110 111 01011110
As we have found three 1's, we update longest.
longest = [longest, 3].max
#=> [0, 3].max => 3
We must now examine 0b10100110 and 0b1011110 (the leading zero in the second number drops out).
For the left number we compute the following.
n = 0b10100110
len = n.bit_length
#=> 8
mid = len >> 1
#=> 4
n[mid]
#=> 0
so we have
101 0 0110
(Note n[0] is the least-significant bit). We can rule out both 0b101 and 0b110, since both have 3 bits, which does not exceed the current valule of longest, which is 3.
Now we consider the right half,
n = 0b1011110
len = n.bit_length
#=> 7
mid = len >> 1
#=> 3
n[mid]
#=>1
so we have
101 1 110
As n[mid] #=> 1, we look left and right for strings of 1's and obtain
10 1111 0
As we have discovered a sting of 4 1's, we set
longest = [longest, 4].max
#=> [3, 4].max = 4
Lastly we see that the numbers of bits on the left (2) and on the right (1) are both less than 3, so we are finished, and return longest #=> 4. (The OP actually wants longest - 1 #=> 3, which we regard as a side-calculation.)
Code
def longest_run(n, longest=0)
len = n.bit_length
return [longest, (n & 1) + (n >> 1)].max if len <= 2
mid = len >> 1
ri = mid-1
li = mid+1
if n[mid] == 1
until n[ri] == 0
ri -= 1
end
until n[li] == 0
li += 1
end
cand = li-ri-1
longest = cand if cand > longest
end
if ri >= 0
shift = ri+1
m = n ^ ((n >> shift) << shift)
if m.bit_length > longest
cand = longest_run(m, longest)
longest = cand if cand > longest
end
end
if li <= len - 1
m = n >> li
if m.bit_length > longest
cand = longest_run(m, longest)
longest = cand if cand > longest
end
end
longest
end
Examples
longest_run 341854
#=> 4
longest_run 0b1011110011111000000111100011101111011110
#=> 5
longest_run 0b101111001111100000011110001110111111011111
#=> 6
longest_run 2**500_000-1
#=> 500000
longest_run ("10"*100_000).to_i(2)
#=> 1