Python: Find Longest Binary Gap In Binary Representation Of An Integer Number

I would like to know if my implementation is efficient. I have tried to find the simplest and low complex solution to that problem using python. def count_gap(x): ''' P

Solution 1:

I do realize that brevity does not mean readability nor efficiency.

However, ability to spell out solution in spoken language and implement it in Python in no time constitutes efficient use of my time.

For binary gap: hey, lets convert int into binary, strip trailing zeros, split at '1' to list, then find longest element in list and get this element lenght.

defbinary_gap(N):
    returnlen(max(format(N, 'b').strip('0').split('1')))  

Solution 2:

Your implementation converts the integer to a base two string then visits each character in the string. Instead, you could just visit each bit in the integer using << and &. Doing so will avoid visiting each bit twice (first to convert it to a string, then to check if if it's a "1" or not in the resulting string). It will also avoid allocating memory for the string and then for each substring you inspect.

You can inspect each bit of the integer by visiting 1 << 0, 1 << 1, ..., 1 << (x.bit_length).

For example:

defmax_gap(x):
    max_gap_length = 0
    current_gap_length = 0for i inrange(x.bit_length()):
        if x & (1 << i):
            # Set, any gap is over.if current_gap_length > max_gap_length:
                max_gap_length = current_gap_length
            current_gap_length = 0else:
            # Not set, the gap widens.
            current_gap_length += 1# Gap might end at the end.if current_gap_length > max_gap_length:
        max_gap_length = current_gap_length
    return max_gap_length

Solution 3:

defmax_gap(N):
    xs = bin(N)[2:].strip('0').split('1')
    returnmax([len(x) for x in xs])

Explanation:

1. Both leading and trailing zeros are redundant with binary gap finding as they are not bounded by two 1's (left and right respectively)
2. So step 1 striping zeros left and right
3. Then splitting by 1's yields all sequences of 0'z
4. Answer : The maximum length of 0's sub-strings

Solution 4:

As suggested in the comments, itertools.groupby is efficient in grouping elements of an iterable like a string. You could approach it like this:

from itertools import groupby

def count_gap(x):
    b = "{0:b}".format(x)
    return max(len(list(v)) for k, v in groupby(b.strip("0")) if k == "0")

number = 123456print(count_gap(number))

First we strip all zeroes from the ends, because a gap has to have on both ends a one. Then itertools.groupby groups ones and zeros and we extract the key (i.e. "0" or "1") together with a group (i.e. if we convert it into a list, it looks like "0000" or "11"). Next we collect the length for every group v, if k is zero. And from this we determine the largest number, i.e. the longest gap of zeroes amidst the ones.

Solution 5:

I think the accepted answer dose not work when the input number is 32 (100000). Here is my solution:

defsolution(N):
    res = 0
    st = -1for i inrange(N.bit_length()):
        if N & (1 << i):
            if st != -1:
                res = max(res, i - st - 1)
            st = i

    return res