问题描述
我想知道我的实施是否有效.我试图使用 python 找到该问题的最简单和低复杂度的解决方案.
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
让我知道你的意见.
推荐答案
您的实现将整数转换为基数为 2 的字符串,然后访问字符串中的每个字符.相反,您可以使用 << 和 & 访问整数中的每一位.这样做将避免访问每个位两次(首先将其转换为字符串,然后检查结果字符串中是否为1").它还将避免为字符串分配内存,然后为您检查的每个子字符串分配内存.
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.
您可以通过访问 1 << 来检查整数的每一位.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