Python位求和算法
Python位求和算法
提问于 2018-07-31 02:21:27
我正在尝试实现一个函数，该函数将用于判断生成器的输出是否连续。我倾向于的方法是遍历生成器。对于每个值，我右对齐值的位(忽略0b)，计算1的数量，并对1的数量进行移位。
#!/usr/bin/python3
from typing import Tuple
def find_bit_sum(top: int, pad_length: int) -> int :
"""."""
return pad_length * (top + 1)
def find_pad_length(top: int) -> int :
"""."""
return len(bin(top)) - 2 # -"0b"
def guess_certain(top: int, pad_length: int) -> Tuple[int, int, int] :
"""."""
_both: int = find_bit_sum(top, pad_length)
_ones: int = sum(sum(int(_i_in) for _i_in in bin(_i_out)[2 :]) for _i_out in range(1, top + 1))
return _both - _ones, _ones, _both # zeros, ones, sum
def guess(top: int, pad_length: int) -> Tuple[int, int, int] : # zeros then ones then sum
"""."""
_bit_sum: int = find_bit_sum(top, pad_length) # number of bits in total
_zeros: int = _bit_sum # ones are deducted
_ones: int = 0 # _bit_sum - _zeros
# detect ones
for _indexed in range(pad_length) :
_ones_found: int = int(top // (2 ** (_indexed + 1))) # HELP!!!
_zeros -= _ones_found
_ones += _ones_found
#
return _zeros, _ones, _bit_sum
def test_the_guess(max_value: int) -> bool : # the range is int [0, max_value + 1)
pad: int = find_pad_length(max_value)
_zeros0, _ones0, _total0 = guess_certain(max_value, pad)
_zeros1, _ones1, _total1 = guess(max_value, pad)
return all((
_zeros0 == _zeros1,
_ones0 == _ones1,
_total0 == _total1
))
if __name__ == '__main__' : # should produce a lot of True
for x in range(3000) :
print(test_the_guess(x))在我的生命中，我不能让guess()同意guess_certain()。guess_certain()的时间复杂性是我的问题:它适用于小范围的[0, top]，但人们可以忘记256位数字(top)。find_bit_sum()函数可以完美地工作。find_pad_length()函数也可以工作。
top // (2 ** (_indexed + 1))我已经尝试了guess()函数的40或50个变体。这让我彻底失望了。guess()函数是概率函数。在其完成状态下:如果它返回False，则生成器肯定不会生成range(top + 1)中的每个值；但是，如果它返回True，则生成器可能会生成每个值。我们已经知道生成器range(top + 1)是连续的，因为它确实生成0和top之间的每个数字；因此，test_the_guess()应该返回True。
我真诚地为我混乱的解释道歉。如果你有任何问题，请不要犹豫，尽管问。
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-07-31 04:35:16
我调整了您的ones_found赋值语句，以说明每个int(top // (2 ** (_indexed + 1)))的2次幂的数量，以及在下一次2的幂之前发生的额外“翻转”。下面是结果语句：
_ones_found: int = int(top // (2 ** (_indexed + 1))) * (2 ** (_indexed)) + max(0, (top % (2 ** (_indexed + 1))) - (2 ** _indexed) + 1)为了清晰和快速，我还随意地将语句转换为按位运算符，如下所示：
_ones_found: int = ((top >> _indexed + 1) << _indexed) + max(0, (top & (1 << _indexed + 1) - 1) - (1 << _indexed) + 1)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51600086
复制相关文章
相似问题