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

让我知道你的意见.

Answer 1

我确实认识到简洁并不意味着可读性和效率.

但是,能够用口语拼出解决方案并立即在Python中实现它可以有效地利用我的时间.

对于二进制间隙:嘿,让我们将int转换为二进制,剥离尾随零,在'1'处拆分列表,然后在列表中找到最长元素并获得此元素长度.

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

Answer 2

您的实现将整数转换为基数为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

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. 因此，第 1 步将零向左和向右剥离
3. 然后由 1 分裂产生 0'z 的所有序列
4. 解决方案：0的子串的最大长度