Given a positive integer n, find and return the longest distance between any two adjacent 1's in the binary representation of n. If there are no two adjacent 1's, return 0.
Two 1's are adjacent if there are only 0's separating them (possibly no 0's). The distance between two 1's is the absolute difference between their bit positions. For example, the two 1's in "1001" have a distance of 3.
 
Example 1:
Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.

Example 2:
Input: n = 5
Output: 2
Explanation: 5 in binary is "101".

Example 3:
Input: n = 6
Output: 1
Explanation: 6 in binary is "110".

Example 4:
Input: n = 8
Output: 0
Explanation: 8 in binary is "1000".
There aren't any adjacent pairs of 1's in the binary representation of 8, so we return 0.

Example 5:
Input: n = 1
Output: 0

 
Constraints:

1 <= n <= 109

Difficulty: introductory

Starter code:

class Solution:
    def binaryGap(self, n: int) -> int:
        

Solutions:
class Solution:
    def binaryGap(self, n: int) -> int:
        maxDist = 0
        currDist = 0
        while n:
            if n & 1 and currDist != 0:
                maxDist = max(maxDist, currDist)
                currDist = 1
            elif n & 1:
                currDist = 1
            elif not n & 1 and currDist != 0:
                currDist+=1
            n >>= 1
        return maxDist

class Solution:
    def binaryGap(self, n: int) -> int:
        bins = ''
        maxv = 0
        i = 0
        pre = None
        while n > 0:
            if n % 2 == 1:
                if pre is not None:
                    maxv = max(maxv,i-pre)
                pre = i
            n //= 2
            i += 1
        
        return maxv

class Solution:
    def binaryGap(self, n: int) -> int:
        binary_string = bin(n)[2:]
        # The binary string has to begin with a 1, if n is a positive integer.

        left, right, current_distance, global_max = 0, 1, 1, 0

        print(binary_string)
        while right <= len(binary_string) - 1:
            print(left, right, current_distance, global_max)
            if binary_string[right] == '0':
                right += 1; current_distance += 1
            else:
                global_max = max(global_max, current_distance)
                left = right; right += 1; current_distance = 1
            
        return global_max

class Solution:
    def binaryGap(self, N: int) -> int:
        bit_list = bin(N)[2:]
        stack = []
        dis = 0
        for b in bit_list:
            if not stack and b == '1':
                stack.append(b)
            elif stack and b == '0':
                stack.append(b)
            elif stack and b == '1':
                dis = max(dis, len(stack))
                stack = ['1']
        return dis
            


class Solution:
    def binaryGap(self, n: int) -> int:
        if n == 0:
            return 0
        
        # Move RSB to first 1
        while n & 1 == 0:
            n = n >> 1
            
        global_max = local_max = 0
        while n > 0:
            # Reset if found another 1
            if n & 1 == 1:
                global_max = max(global_max, local_max)
                local_max = 1
            # Keep counting towards local max
            else:
                local_max += 1
            n = n >> 1
            
        return global_max