help with finding binary gap

[djwilson0495]

Hi I'm trying to write a code to give the biggest gap in a binary number. Here's my code:

N = int(input("Please enter an integer:"))

def binary_gap(N):
    binary = str(bin(N))[2:]
    bin_gap = False
    bin_max = 0
    bin_counter = 0
    for num in binary:
        if num == 1:
            if bin_max < bin_counter:
                # if the current gap is bigger than the largest recorded gap set this gap as bin_max
                bin_max = bin_counter
            bin_gap = True
        elif bin_gap:
            # adds 1 to the counter total.
            bin_counter += 1
    
    print(binary)
    print(f"The largest binary gap in {N} is {bin_counter}")

binary_gap(N)

And here's the output that I'm getting:

Output:
Please enter an integer:45
101101
The largest binary gap in 45 is 0

I'm not sure why its giving me zero as I'm printing the binary number and I can see that the answer should be 1.

[Gribouillis]

I think the problem is that if num == 1 should be if num == '1'.

[deanhystad]

bin(N) returns a string, so there is no need to for str(bin(N)). You could also use f'{N:b}' which creates a string without the leading "0b".

Your main problem is that your string does not contain 0 and 1 but rather '0' and '1'.

Once you get that working you'll find the counting logic is flawed. You never reset your bin_counter, so your program counts the number of zeroes in the number, not the largest gap.

I also thing your logic is backward. You are counting '0', so you should update bin_max when you get a '0', not a '1'. As is I think your program fails if the maximum gap comes at the end of the number.

You can do a little housekeeping. bin_gap doesn't do anything. I think you were using it to skip the leading '0' in '0b...', but that problem was fixed elsewhere. 'binary' will always start with '1', so 'bin_gap' no longer has a job. Get rid of him. Variables should clearly describe what the variable is. This thing counts gaps or '0', so use 'max_gap" or 'max0' instead of 'max_bin'. I don't know if 'max_bin' is counting zeroes or ones.

Finally, I think the function binary_gap() is a poor design. Only functions designed to produce output should contain print statements. Your function counts binary gaps (whatever that is) and should return a number. I don't know when I would ever need to measure binary gaps, but a small change would make this a function that could potentially be reused. Your program should call the function and print the results.

[djwilson0495]

Thanks guys I've got it sorted now. I'm posting my code in case anyone else has a similar issue when trying to do this.

N = int(input("Please enter an integer:"))

def binary_gap(N):
    binary = (bin(N))[2:]
    br = binary[::-1]
    max_gap = 0
    bin_counter = 0
    bin_gap = False
    for num in binary:
        if num == '0':
            if bin_gap == True: 
                bin_counter += 1
                if max_gap < bin_counter:
                    # if the current gap is bigger than the largest recorded gap set this gap as bin_max
                    max_gap = bin_counter
        elif num == '1':
            # adds 1 to the counter total.
            bin_counter = 0 
            if bin_gap == False:
                bin_gap = True
            elif bin_gap == True:
                bin_gap = False
    
    print(binary)
    print(f"The largest binary gap in {N} is {max_gap}")

binary_gap(N)

[deanhystad]

I think you function still needs some housekeeping. Why are you doing this?

br = binary[::-1]

"br" never gets used anywhere. Remove it.

And why this test?

if num == '0':
...
elif num == '1':

Are you expecting something other than '0' or '1'? If num can only be '0' or '1' use else instead of elif num == '1':

And what is the purpose of 'bin_gap'? If you remove all references of bin_gap from your function it gives you the same result. Get rid of it.

def binary_gap(N):
    bin_counter = 0
    max_gap = 0
    for num in bin(N)[2:]:
        if num == '0':
            bin_counter += 1
            max_gap = max(max_gap, bin_counter)
        else:
            bin_counter = 0
    return max_gap
     
N = int(input("Please enter an integer:"))
print(f"The largest binary gap in {N} is {binary_gap(N)}")

You don't need to convert the number to a binary string either.

def binary_gap(number):
    max_gap = gap = 0
    while number > 0:
        if number % 2:
            gap = 0
        else:
            gap += 1
            max_gap = max(max_gap, gap)
        number = number // 2
    return max_gap

while True:
    try:
        number = int(input('Enter Number: '))
        print(f'Max gap for {number} = {binary_gap(number)}')
    except:
        break

[Gribouillis]

Here is my binary attempt

def lowgap(n):
    return (n & -n).bit_length() - 1

def igap(n):
    if n & 1:
        n >>= lowgap(n + 1)
    while n:
        g = lowgap(n)
        yield g
        n >>= g
        n >>= lowgap(n + 1)

def maxgap(n):
    return max(igap(n), default=0)

for n in [7, 234, 37733222, 763623, 22300033, 9862444]:
    print(maxgap(n), bin(n))

Output:
0 0b111
1 0b11101010
4 0b10001111111100001101100110
2 0b10111010011011100111
6 0b1010101000100010110000001
2 0b100101100111110100101100

[perfringo]

Simple algorithm for finding binary gap is: "convert int into binary, strip trailing zeros, split at '1' to list, find longest element in list and get this element length". Python implementation of this is one-liner which is much shorter than algorithm itself in spoken language.

[deanhystad]

I think trailing zeros are a gap, so the description (and program) are even shorter.

Convert number to a binary string. Split the string into strings of contiguous '0'. Return length of the longest string.

def binary_gap(num):
    return max([len(zero) for zero in bin(num)[2:].split('1')])

print(128, binary_gap(128))
print(42, binary_gap(42))
print(15, binary_gap(15))

[perfringo]

As far as I know binary gap definition is something like:

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

According to such definition trailing zeros should be ignored.

There is no need for loop as split returns list, so it could be written as:

len(max(format(N, 'b').strip('0').split('1')))

[deanhystad]

Clever. I didn't think about '000' > '00' > '0'.

To be honest I've never heard about "binary gap" and a google search indicates it is a made up programming exercise thing. You are correct. The descriptions mention consecutive zeroes surrounded by ones.