問題描述

我想知道我的實(shí)施是否有效.我試圖使用 python 找到該問題的最簡(jiǎn)單和低復(fù)雜度的解決方案.

I would like to know if my implementation is efficient. I have tried to find the simplest and low complex solution to that problem using 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

讓我知道你的意見.

推薦答案

您的實(shí)現(xiàn)將整數(shù)轉(zhuǎn)換為基數(shù)為 2 的字符串，然后訪問字符串中的每個(gè)字符.相反，您可以使用 << 和 & 訪問整數(shù)中的每一位.這樣做將避免訪問每個(gè)位兩次(首先將其轉(zhuǎn)換為字符串，然后檢查結(jié)果字符串中是否為1").它還將避免為字符串分配內(nèi)存，然后為您檢查的每個(gè)子字符串分配內(nèi)存.

Your implementation converts the integer to a base two string then visits each character in the string. Instead, you could just visit each bit in the integer using << and &. Doing so will avoid visiting each bit twice (first to convert it to a string, then to check if if it's a "1" or not in the resulting string). It will also avoid allocating memory for the string and then for each substring you inspect.

您可以通過(guò)訪問 1 << 來(lái)檢查整數(shù)的每一位.0, 1 <<1, ..., 1 <<(x.bit_length).

You can inspect each bit of the integer by visiting 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

這篇關(guān)于Python:在整數(shù)的二進(jìn)制表示中查找最長(zhǎng)的二進(jìn)制間隙的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，也希望大家多多支持html5模板網(wǎng)！