2

问题是如何反转数字的交替位，从LSB. 目前我正在做的是首先做一个

count = -1
while n:
   n >>= 1
   count += 1

首先找到最左边的设置位的位置，然后运行一个循环来反转每个交替位：

i = 0
while i <= count:
 num ^= 1<<i
 i += 2

有没有一个快速破解解决方案而不是这个相当无聊的循环解决方案？当然，解决方案不能对整数的大小做出任何假设。

4

4 回答 4

5

我认为这可能有效：

具有交替掩码的按位 XOR10101010...10应每隔一位反转。

如果要反转 '0011' 中的交替位，下表显示了结果：

i | m | i XOR m
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0

在 python 中，XOR 是通过i ^ m. 当然，您也必须确定掩码的字面值，这取决于您的i数字的大小。

于 2012-10-27T07:59:47.460 回答
2

以前的单线解决方案，

n ^ sum(2**i for i in range(0, len(bin(n))-2, 2))

是 O(lg n) 解，其中 n 是输入数。下面显示的渐近更快的解决方案在时间 O(lg(lg n)) 中运行，也就是说，时间与输入数字中位数的对数成正比。请注意，所示的二进制搜索在测试中运行良好，但也许可以改进。

编辑：表达式-1<<L是一个掩码，它的高位被设置，它的 L 低位被清除。例如，python 将 255 显示为 的值(-1<<8)&255，将 256 显示为 的值(-1<<8)&256。程序首先将 L 加倍（使越来越多的低位清空），直到 L 超过数字 v 中的位数；也就是说，直到(-1<<L)&v为零。每增加一倍 L，它可以使 R 向上移动。然后程序使用二分查找，反复将 LR 差减半，找到 L=R+1 使得v&(-1<<L) == 0和v&(-1<<R) > 0，确定 v 的长度为 L 位。之后，程序将交替位掩码 k 的长度加倍，直到它至少有 L 位长。然后如果 L 是奇数，它将掩码移动一位。（而不是if L & 1: k = k<<1它可以说k <<= L&1. 请注意，我将“备用位”解释为从 MSB 正下方的位开始。要始终切换位 0,2,4...，请删除该if L & 1: k = k<<1行。）然后它通过 &'ing 与(1<<L)-1(2**L)-1 提取 k 的低 L 位。注意，程序的 O(lg(lg n)) 时间界限取决于 O(1) 逻辑运算；但是随着 L 变大（超过几百位），1<<L等等变成 O(lg n) 操作。

def clearaltbits(v):
    if not v:
        return 0
    L, R = 16, 0
    # Find an upper bound on # bits
    while (-1<<L) & v:
        R, L = L, 2*L
    # Binary search for top bit #
    while not (-1<<L) & v:
        m = (L+R)/2
        if (-1<<m) & v:
            R = m
        else:
            L = m
        if L==R+1: break
    print bin(v),'has',len(bin(v))-2,'bits.'
    # Make big-enough alternate-bits mask
    k, b = 0b0101010101010101, 16
    while not (-1<<L) & k:
        k = (k<<b)|k
        b += b
    if L & 1:
        k = k<<1
    k = k & ((1<<L)-1)
    print bin(k^v),'fin'


clearaltbits(3**3)
clearaltbits(5**6)
clearaltbits(7**17)
clearaltbits(13**19)

四个函数调用的输出如下所示。

0b11011 has 5 bits.
0b10001 fin

0b11110100001001 has 14 bits.
0b10100001011100 fin

0b110100111001001110000011001001100110111010000111 has 48 bits.
0b100001101100011011010110011100110011101111010010 fin

0b10011110100000000111000001101101000001011000100011000010010000111010101 has 71 bits.
0b11001011110101010010010100111000010100001101110110010111000101101111111 fin
于 2012-10-27T08:39:55.647 回答
1

扩展 trideceth12 给出的答案 - 这是一个计算和应用掩码的单线：

n ^ sum(2**i for i in range(0, len(bin(n))-2, 2))

...假设您确实想从 LSB 开始，也就是说。

或者，如果您从最重要的设置位开始：

n ^ sum(2**i for i in range(len(bin(n))-3, -1, -2))
于 2012-10-27T08:20:33.167 回答
0

这适用于任何长度的正整数：

def invert_alt_bits(n):
    m = 1
    while True:
        n ^= m
        m <<= 2
        if m > n: break
    return n
于 2012-10-27T10:56:35.267 回答