按一位 'hopping' 查找与给定整数相关的 n 位整数集

Question

给定一个 n 位整数，我想通过单个 1 与单个 0 的互换找到与我的原始整数相关的 n 位整数集，其中互换的 1 和 0 必须相邻

所以我想要的是找到一些函数，例如，如果我给它二进制 1011 （基数 10 中的 11）它 returns 0111 和 1101（以 10 为基数的 7 和 13） IE。所以这看起来像：

>>> bit_hop(11, n=4)
[7, 13]

这个函数知道这个数字有多少位很重要，因为我的另一个限制是我需要它有周期性的边界条件，例如 0111 不仅 return 1011 还有 1110，即。二进制数的边应该是相邻的。

另外，如前所述，每一跳只允许交换一次。这意味着 bit_hop(1010) 应该 return [1100, 0011, 1001, 0110]

有没有人知道如何去做这件事？我知道这应该涉及 >>、<< 和 ^ 操作的一些巧妙用法，但我无法看到合成。

Answer 1

要直接用二进制执行此操作，您必须注意有关该算法的几件事。首先，它总是处理相邻的位，除了从第一位循环到最后一位。其次，这些位必须不同，如果它们相同，则交换它们不会做任何事情。

此代码围绕该值遍历 2 位掩码并测试这些位是否不同，然后使用异或来交换它们。

def bit_hop(x, n):
    for i in range(n-1):
        mask = 3 << i
        if x & mask != 0 and x & mask != mask:
            yield x ^ mask
    mask = (1 << (n-1)) | 1
    if x & mask != 0 and x & mask != mask:
        yield x ^ mask

按一位 'hopping' 查找与给定整数相关的 n 位整数集

Finding the set of n-bit integers related to a given integer by single bit 'hopping'

python

bit-manipulation

bitwise-operators