Python 位求和算法

Question

我正在尝试实现一个函数，用于判断发电机的输出是否连续。我倾向于使用的方法是遍历生成器。对于每个值，我右对齐值的位（忽略 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 位数字 (tops)。 find_bit_sum() 函数完美运行。 find_pad_length() 函数也有效。

top // (2 ** (_indexed + 1))

我已经尝试了 40 或 50 个 guess() 函数的变体。这让我非常沮丧。 guess() 函数是概率性的。在其完成状态：如果它 returns False，那么生成器肯定不会产生 range(top + 1) 中的每个值；但是，如果它 returns True，那么生成器可能是。我们已经知道生成器 range(top + 1) 是连续的，因为它确实生成了 0 和 top 之间的每个数字；所以，test_the_guess() 应该返回 True。

对于混乱的解释，我深表歉意。如果您有任何问题，请随时提问。

Answer 1

我调整了你的 ones_found 赋值语句以说明每个 int(top // (2 ** (_indexed + 1))) 的 2 的幂数，以及在下一个 2 的幂之前发生的额外 "rollover" .这是结果语句：

_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)

Python 位求和算法

Python Bit Summation Algorithm

python-3.x

algorithm

math

bit

bits