FilesExpand file tree

 master

/

binary_gap.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

57 lines (50 loc) · 1.51 KB

 master

/

binary_gap.py

Copy path

Top

File metadata and controls

• Code
• Blame

57 lines (50 loc) · 1.51 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

"""

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))