python-algorithms/algorithms/bit/binary_gap.py at master · ilyvsc/python-algorithms · GitHub

History

57 lines (50 loc) · 1.51 KB

Raw

"""

Given a positive integer N, find and return the longest distance between two

consecutive 1' in the binary representation of N.

If there are not two consecutive 1's, return 0

For example:

Input: 22

Output: 2

Explanation:

22 in binary is 10110

In the binary representation of 22, there are three ones, and two consecutive pairs of 1's.

The first consecutive pair of 1's have distance 2.

The second consecutive pair of 1's have distance 1.

The answer is the largest of these two distances, which is 2

"""

# 原方法为 binary_gap，但通过实验发现算法有误，不论是什么数，输出值最多为2。

# 改进方法为binary_gap_improved。

# The original method is binary_gap,

# but the experimental results show that the algorithm seems to be wrong,

# regardless of the number, the output value is up to 2.

# The improved method is binary_gap_improved.

def binary_gap(N):

last = None

ans = 0

index = 0

while N != 0:

if N & 1:

if last is not None:

ans = max(ans, index - last)

last = index

index = index + 1

N = N >> 1

return ans

def binary_gap_improved(N):

last = None

ans = 0

index = 0

while N != 0:

tes = N & 1

if tes:

if last is not None:

ans = max(ans, index - last + 1)

else:

last = index

else:

last = index + 1

index = index + 1

N = N >> 1

return ans

print(binary_gap(111))

print(binary_gap_improved(111))

python-algorithms/algorithms/bit/binary_gap.py at master · ilyvsc/python-algorithms · GitHub

Expand file tree

Breadcrumbs

binary_gap.py

Latest commit

History

Breadcrumbs

binary_gap.py

File metadata and controls