Python: Find longest binary gap in binary representation of an integer number

binary gap - leetcode
find longest sequence of zeros in binary representation of an integer.
binary gap javascript
binary gap in scala
bin/python
binary period codility python
binary gap php
python binary

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):
    """
        Perform Find the longest sequence of zeros between ones "gap" in binary representation of an integer

        Parameters
        ----------
        x : int
            input integer value

        Returns
        ----------
        max_gap : int
            the maximum gap length

    """
    try:
        # Convert int to binary
        b = "{0:b}".format(x)
        # Iterate from right to lift 
        # Start detecting gaps after fist "one"
        for i,j in enumerate(b[::-1]):
            if int(j) == 1:
                max_gap = max([len(i) for i in b[::-1][i:].split('1') if i])
                break
    except ValueError:
        print("Oops! no gap found")
        max_gap = 0
    return max_gap

let me know your opinion.

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:

def max_gap(x):
    max_gap_length = 0
    current_gap_length = 0
    for i in range(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 = 0
         else:
            # 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

Binary Gap | Practice Problems, The number 15 has binary representation 1111 and has no binary gaps. Write a function: int solution(int N);. that, given a positive integer N,  By definition binary gap is 'zeros between ones', therefore one should not consider trailing zeros as binary gap. Try to run both versions with int 32 (100000 in binary). With strip you get 0 (there is no binary gap) without strip you get 5 (which is incorrect as there is no 5 zeros between ones). – Aivar Paalberg Mar 25 '19 at 7:23

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.

def binary_gap(N):
    return len(max(format(N, 'b').strip('0').split('1')))  

Python bin() Function (With Examples), BinaryGap, Python - Find longest sequence of zeros in binary representation of an integer. in Python 3. of zeros: " + str(theZeros)) return gapHigher print("​Number: " + str(theNumber)) print("Gap Higher: " + str(binaryGap(theNumber)))  C Program to Find The Longest Binary Gap in a Number N 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

def max_gap(N):
    xs = bin(N)[2:].strip('0').split('1')
    return max([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. Solution: The maximum length of 0's sub-strings

Given a positive integer N , find and return the longest distance between two consecutive 1's in the binary representation of N . If there aren't two consecutive 1's,  Write a Java program to find the length of the longest sequence of zeros in binary representation of an integer. Sample example: Number 7 has binary representation 111 and has no binary gaps. Number 8 has binary representation 1000 and contains a binary gap of length 0. Number 457 has binary representation 111001001 and contains a binary gap of length 2.

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 = 123456
print(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.

Converting from string to int in your first comprehension isn't needed as you're comparing to a literal anyway. You can merge the first two  The question description says: N is an integer within the range [1..2,147,483,647]. I think, Colby’s code is assuming the input is 32 bits, since the bitmask is 32bits. Reply

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

def solution(N):
    res = 0
    st = -1
    for i in range(N.bit_length()):
        if N & (1 << i):
            if st != -1:
                res = max(res, i - st - 1)
            st = i

    return res

I got a score of 100 but I'm new to python. Value;. string[] gaps = binaryAfterRegex.Split('1');. int t = 0; find lenght of longest string of zeros. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps. Write a function: function solution(N); that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn’t contain a binary gap. For example, given N

Find longest sequence of zeros in binary representation of an integer. Programming The number 15 has binary representation 1111 and has no binary gaps. The number 20 has binary representation 1 0100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. Find the length of binary gap/s for a given number. If the number has more than one binary gap, then output all lengths of binary gaps. If the number has no binary gap, then output 0. Input

// binary representation of a number. public class GFG {. static int  This problem has a much faster solution than the one (probably) required in the question. For a given n it is solvable in only O(log log n) basic bitwise instructions.

A binary gap within a positive integer N is any maximal sequence of consecutive For example, number 9 has binary representation 1001 contains a binary gap of length 2. Find the length of binary gap/s for a given number. Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby,  Codility Solution to Problem 1 BinaryGap - Find longest sequence of zeros in binary representation of an integer. A binary gap within a positive integer N is any maximal sequence of consecutive

Comments
  • I'd suggest using the int.bit_length method instead of the ceil(log2(...)) computation, to avoid corner-case errors due to rounding.
  • You have said Your implementation converts the integer to a base two string then visits each character in the string but that is not completely correct as I break after detecting one then I split. Could you plz highlight why your implementation should be better in terms of time and memory complexity, please.
  • You still have to visit each character. How else can split find the right place to split? It visits each character until it finds the value you supplied.
  • Hi Jean, Your code is much slower than the one I provided. I will add the time complexity in the answer (as running time test code).
  • Thanks, Jean. In the beginning, i was afraid to publish my codes in StackOverflow (negative comments), but you really encouraged me to keep on going (publish and optimize). Good luck
  • Super nice :thumbsup:
  • This one liner really very efficient. But I got stuck in one point, what is the functionality of strip? I ran that code without using strip and it had same output. Thank you in advance.
  • By definition binary gap is 'zeros between ones', therefore one should not consider trailing zeros as binary gap. Try to run both versions with int 32 (100000 in binary). With strip you get 0 (there is no binary gap) without strip you get 5 (which is incorrect as there is no 5 zeros between ones).
  • Welcome to Stack Overflow! Thank you for the code snippet, which might provide some limited, immediate help. A proper explanation would greatly improve its long-term value by describing why this is a good solution to the problem, and would make it more useful to future readers with other similar questions. Please edit your answer to add some explanation, including the assumptions you've made.
  • This is the part of review answer in stackoverflow. Add some explanation though code is explanatory.
  • Add explanation.
  • You should edit your answer to add a minimal reproducible example demonstrating the problem.
  • Can you explain your code? Dropping code without doing so might not be that helpful.
  • Please explain why your answer is better than the others. This will help people learn from your answer.