Python：找到整数的二进制表示中最长的二进制间隙

Question

我想知道我的实现是否高效。我尝试使用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

请告诉我您的意见。

- user8358337

---

codility的BinaryGap测试允许使用18种不同编程语言写代码，包括：C, C++, C#, Go, Java 8, Java 11, JavaScript, Kotlin, Lua, Objective-C, Pascal, PHP, Perl, Python, Ruby, Scala, Swift 4, 和Visual Basic。因此，我认为没有理由限制这个问题只能用Python解决。 - Henke

Answer 1

我知道简洁并不代表易读或高效。

然而，能够用口语清晰地解释解决方案并在Python中快速实现，构成了我时间的有效利用。

对于二进制间隔：嘿，让我们将int转换为二进制，在末尾删除零，在'1'处拆分成列表，然后找到列表中最长的元素并获取此元素的长度。

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

- Aivar Paalberg

---

超级棒 :thumbsup: - Brian Wylie

这个一行代码确实非常高效。但是我在一个点上卡住了，strip的功能是什么？我运行了没有使用strip的代码，输出结果相同。提前感谢您。 - Encipher

根据定义，二进制间隔是“1之间的零”，因此不应将尾随的零视为二进制间隔。尝试使用 int 32（100000 的二进制表示）运行两个版本。使用strip函数，您会得到0（没有二进制间隔），而不使用strip函数，您会得到5（这是不正确的，因为不存在5个零在1之间）。 - Aivar Paalberg

如果您正在寻找性能方面的优化：@Orenico 在他的答案中使用的 bin() 比 format(N, 'b') 要快得多。 - quassy

如果您想运行相应的Codility测试，只需将binary_gap重命名为solution。此解决方案得分100％正确，并通过了15个测试中的15个。 - Henke

Answer 2

您的实现方式将整数转换为二进制字符串，然后逐个访问字符串中的每个字符。 相反，您可以使用 << 和 & 访问整数中的每个位。 这样做将避免两次访问每个位（首先将其转换为字符串，然后在结果字符串中检查它是否是“1”）。 它还将避免为字符串分配内存以及检查每个子串。

您可以通过访问 1 << 0、1 << 1、...、1 << (x.bit_length) 来检查整数的每个位。

例如：

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

- Jean-Paul Calderone

---

我建议使用 int.bit_length 方法来代替 ceil(log2(...)) 计算，以避免由于四舍五入而导致的边角情况错误。 - Mark Dickinson

你说过你的实现将整数转换为二进制字符串，然后访问字符串中的每个字符，但这并不完全正确，因为我在检测到一个后就会中断然后分割。请问你能否强调一下你的实现在时间和内存复杂度方面应该更好的原因？ - user8358337

你仍然需要访问每个字符。否则，split如何找到正确的拆分位置？它会访问每个字符，直到找到您提供的值。 - Jean-Paul Calderone

嗨，Jean，你的代码比我提供的那个慢得多。我会在答案中添加时间复杂度（作为运行时间测试代码）。 - user8358337

谢谢，Jean。一开始，我害怕在StackOverflow上发布我的代码（因为可能会有负面评论），但是你真的鼓励我继续前进（发布和优化）。祝好运。 - user8358337

Answer 3

def max_gap(N):
    xs = bin(N)[2:].strip('0').split('1')
    return max([len(x) for x in xs])

解释：

1. 在使用二进制间隙查找时，前导零和尾随零都是冗余的，因为它们没有被两个 1（左侧和右侧）所限定。
2. 因此，第一步是去掉左右的零。
3. 然后按照 1 的位置进行分割，得到所有的 0 子串。
4. 解法：最长的 0 子串长度。

- Orenico

---

欢迎来到Stack Overflow！感谢您提供的代码片段，它可能会提供一些有限的、即时的帮助。一个适当的解释将极大地提高其长期价值，描述为什么这是一个好的解决方案，并使其对未来有类似问题的读者更有用。请编辑您的答案添加一些解释，包括您所做的假设。 - sepehr

Answer 4

这是我的解决方案：

def solution(N):
    num = binary = format(N, "06b")
    char = str(num)
    find=False
    result, conteur=0, 0

    for c in char:
        if c=='1' and not find:
            find = True
            
        if find and c=='0':
            conteur+=1

        if c=='1':
            if result<conteur:
                result=conteur
            conteur=0

    return result

- user14197896

Answer 5

如评论中所建议的，itertools.groupby 在像字符串这样的可迭代对象中分组元素非常高效。您可以采用以下方法：

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

首先，我们需要去掉末尾的所有零，因为间隔必须在两端都有一个一。然后使用 itertools.groupby 对一和零进行分组，并提取键（即“0”或“1”）以及组（即如果将其转换为列表，则看起来像“0000”或“11”）。接下来，如果 k 为零，我们收集每个组 v 的长度。从这些长度中，我们确定最大的数字，即在一串一中最长的零间隙。

- Mr. T

Answer 6

我认为被接受的答案在输入数字为32（100000）时无效。以下是我的解决方案：

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

- Jingda Mai

---

这是stackoverflow评论答案的一部分。虽然代码已经很清楚了，但还是需要添加一些解释。 - Harsha Biyani

添加说明。 - Lutaaya Huzaifah Idris

Answer 7

def solution(N):
    # write your code in Python 3.6
    count = 0
    gap_list=[]
    bin_var = format(N,"b")
    for bit in bin_var:
        if (bit =="1"):
            gap_list.append(count)
            count =0
        else:
            count +=1
    return max(gap_list)

- Vasanth

Answer 8

def solution(N):
# write your code in Python 3.6

    iterable_N = "{0:b}".format(N)
    max_gap = 0
    gap_positions = []
    for index, item in enumerate(iterable_N):
        if item == "1":
            if len(gap_positions) > 0:
               if (index - gap_positions[-1]) > max_gap:
                    max_gap = index - gap_positions[-1]
            gap_positions.append(index)
    max_gap -= 1 
    return max_gap if max_gap >= 0 else 0

- Harrison

Answer 9

def solution(N: int) -> int:
    binary = bin(N)[2:]
    longest_gap = 0
    gap = 0
    for char in binary:
        if char == '0':
            gap += 1
        else:
            if gap > longest_gap:
                longest_gap = gap
            gap = 0
    return longest_gap

- m.joy

---

请解释为什么您的答案比其他答案更好。这将有助于人们从您的答案中学习。 - Brian Tompsett - 汤莱恩

Answer 10

这也可以工作：

def binary_gap(n):
    max_gap = 0
    current_gap = 0

    # Skip the tailing zero(s)
    while n > 0 and n % 2 == 0:
        n //= 2

    while n > 0:
        remainder = n % 2
        if remainder == 0:
            # Inside a gap
            current_gap += 1
        else:
            # Gap ends
            if current_gap != 0:
                max_gap = max(current_gap, max_gap)
                current_gap = 0
        n //= 2

    return max_gap

- Hooman Tamimi