两个整数的移位和异或函数

Question

我的程序中有一个很奇怪的操作。给定两个二进制数 a 和 b。第二个数字告诉我构建了多少个求和数，即数字中 1 的数量。他们的位置（2 的幂）表明在获得新的被加数之前 a 移动了多远。

示例：

    a = 1100101
    b =   10110
 index= 6543210

b 在索引 1、2 和 4（从右到左）处有一个 1，因此被加数是（用零填充），是 a:

的移位

(a << 1), (a << 2), (a << 4)

将它们全部异或： (a << 1) ^ (a << 2) ^ (a << 4)

第二个例子：

a = 110101
b =  10101

结果：

(a << 0) ^ (a << 2) ^ (a << 4)

通常，我现在会对 a 和 b 进行排序，使 b 更短，然后对 b 的索引进行 for 循环，并将移位的加数放入一个数组中，最后遍历该数组以对它们进行异或运算。

但是没有更流畅的方法吗？

Answer 1

也许，Python 不是处理此类问题的最佳选择。

res = 0  # this is where the result will be
while b:
    b, flag = divmod(b, 2)
    res ^= a*flag
    a <<= 1

Answer 2

您可以尝试使用 functools 中的 reduce

from functools import reduce
a = 0b1100101
b = 0b10101
print( reduce(lambda a,x: a^x, (a << i for i in range(len(bin(b))-2) if (b&(1<<i))>0),0) )

(a << i for i in range(len(bin(b))-2) 表达式为您提供移位的数字，然后您使用 reduce 对所有数字进行异或运算，初始值从 0 开始因为那不会改变位模式

>>> [ i for i in range(len(bin(b))-2) if (b & (1<<i))>0 ]
[1, 2, 4]

>>> [a << i for i in range(len(bin(b))-2) if (b & (1<<i))>0 ]
[202, 404, 1616]

>>> reduce(lambda a,x: a^x, (a << i for i in range(len(bin(b))-2) if (b&(1<<i))>0),0)
1806

编辑

Marat 提供的答案要快得多

$ python -mtimeit -s 'from functools import reduce; a=0b1100101; b=0b10110' 'reduce(lambda a,x: a^x, (a << i for i in range(len(bin(b))-2) if (b&(1<<i))>0),0)'
100000 loops, best of 5: 3.01 usec per loop
$ python -mtimeit -s 'res=0; a=0b1100101; b=0b10110' 'while b: b, flag = divmod(b, 2); res ^= a*flag; a <<= 1'
20000000 loops, best of 5: 18.5 nsec per loop

两个整数的移位和异或函数

Bit shift and XOR function of two ints

python

bit

bit-shift

xor