how to find the longest consecutive 1 of binary in python

Question

this is my code so the logic basically is supposed to be that the user inputs an integer we check with the first bit of integer whether it is 1 or not if 1 the var count goes up if not we skip it we do this till the longest set of 1's is reached which is set in var temp when I run it with any number it outputs 1

n = int(input('enter your no'))
count = 0
temp = 0
while n>0:
    if n&1 == 0:
        count+=1
    if count>=temp:
        temp = count
        count = 0
    else:
        count = 0
    n = n>>1
print(count, temp)

Answer 1

You can take advantage of binary carry to get more than one bit at a time. This function breaks the number apart into alternating runs of 0s and 1s, and keeps track of the longest run of 1s.

def longest_one_run(n):
    if n < 0:
        # Negative numbers in Python have an infinite number
        # of ones on the left side.  Fix it by capping the
        # number of bits to a reasonable number, say 32.
        n &= (1 << 32) - 1
    longest = 0
    while n > 0:
        if n&1:
            mask = n + 1
        else:
            mask = n - 1
        run = (n ^ mask) >> 1
        run_count = run.bit_length()
        if n&1 and run_count > longest:
            longest = run_count
        n >>= run_count
    return longest

I used an answer from Fast way of counting non-zero bits in positive integer for CountBits to count the number of bits in a run, any of the answers there should suffice. If I had Python 3.10 I would have used .bit_count(). And based on a comment I was able to replace both with .bit_length() which works even better.

Answer 2

More solutions and benchmarks:

random 20-bit numbers:
 0.57 ± 0.25 μs  Kelly3
 1.51 ± 0.48 μs  Kelly
 1.80 ± 0.61 μs  Kelly2
 3.99 ± 0.96 μs  Mark
 4.75 ± 0.54 μs  Yash

random 1000-bit numbers:
 0.00 ± 0.00 ms  Kelly3
 0.03 ± 0.00 ms  Kelly
 0.03 ± 0.00 ms  Kelly2
 0.22 ± 0.01 ms  Mark
 0.27 ± 0.01 ms  Yash

random 10000-bit numbers:
 0.01 ± 0.00 ms  Kelly3
 0.34 ± 0.00 ms  Kelly2
 0.38 ± 0.00 ms  Kelly
 5.29 ± 0.06 ms  Mark
 5.42 ± 0.09 ms  Yash

random 30000-bit numbers:
 0.03 ± 0.00 ms  Kelly3
 1.08 ± 0.01 ms  Kelly2
 1.30 ± 0.11 ms  Kelly
34.77 ± 1.00 ms  Yash
36.38 ± 1.05 ms  Mark

Code (Attempt This Online!):

def Kelly(n):
    return max(map(len, f'{n:b}'.split('0')))

def Kelly2(n):
    return max(map(len, filter(None, f'{n:b}'.split('0'))), default=0)

def Kelly3(n):
    ctr = 0
    while n:
        n &= n >> 1
        ctr += 1
    return ctr

def Mark(n):
    longest = 0
    while n > 0:
        if n&1:
            mask = n + 1
        else:
            mask = n - 1
        run = (n ^ mask) >> 1
        run_count = run.bit_length()
        if n&1 and run_count > longest:
            longest = run_count
        n >>= run_count
    return longest

def Yash(n):
    count = 0
    temp = 0
    while n>0:
        if n&1 == 1:
            count+=1
        else:
            temp = max(temp, count)
            count = 0
        n = n>>1
    temp = max(temp, count)
    return temp

funcs = Kelly, Kelly2, Kelly3, Mark, Yash

import random
from timeit import repeat
from statistics import mean, stdev

# Correctness
for n in [*range(10000), *(random.getrandbits(10) for _ in range(1000))]:
  expect = funcs[0](n)
  for f in funcs[1:]:
    if f(n) != expect:
      print('fail:', f.__name__)
    
def test(bits, number, unit, scale):
  print(f'random {bits}-bit numbers:')

  times = {f: [] for f in funcs}
  def stats(f):
    ts = [t * scale for t in times[f][5:]]
    return f'{mean(ts):5.2f} ± {stdev(ts):4.2f} {unit} '

  for _ in range(10):
    n = random.getrandbits(bits)
    for f in funcs:
      t = min(repeat(lambda: f(n), number=number)) / number
      times[f].append(t)

  for f in sorted(funcs, key=stats):
    print(stats(f), f.__name__)
  print()

test(20, 1000, 'μs', 1e6)
test(1000, 10, 'ms', 1e3)
test(10000, 1, 'ms', 1e3)
test(30000, 1, 'ms', 1e3)

Answer 3

Some bugs in your code.

(1) You wanted to find longest consecutive 1's this condition if n&1 == 0 should be if n&1 == 1.

(2) Your second if always satisfied every time when count>=temp (i.e when count>=0) and it is always true and you are setting to count=0everytime.

Code:

n = int(input('enter your no: ')) #7
count = 0
temp = 0
while n>0:
    if n&1 == 1:
        count+=1
    else:
        temp = max(temp, count)
        count = 0
    n = n>>1
temp = max(temp, count)
print(temp) #3