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 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您的实现将整数转换为以二为基数的字符串，然后访问字符串中的每个字符。相反，您可以使用 << 和 & 访问整数中的每一位。这样做将避免访问每个位两次（首先将其转换为字符串，然后检查结果字符串中它是否为“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 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

我确实意识到简洁并不意味着可读性或效率。

然而，能够用口头语言拼出解决方案并立即用 Python 实现它的能力构成了我对时间的有效利用。

对于二进制间隙：嘿，让我们将 int 转换为二进制，去除尾随零，在“1”处拆分为列表，然后在列表中找到最长的元素并获取该元素的长度。

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

原文由 Aivar Paalberg 发布，翻译遵循 CC BY-SA 3.0 许可协议