我想对一组数字执行按位运算。让我们假设数字 11、18、2 和 8。操作如下:
01011
10010
00010
01000
01010 (ans)
n 为偶数时的逻辑 - 对于一组 n 个数字,如果至少 n/2 +1 的数字的第 i 位设置为零,则结果的第 i 位为 0。如果至少有 n/2 个数字将第 i 位设置为 1,则结果的第 i 位为 1
n 为奇数时的逻辑 - 对于一组 n 个数字,如果至少 (n+1(/2 个数字的第 i 位设置为零,则结果的第 i 位为 0。如果至少 (n+1(/2 的数字将第 i 位设置为 1,则结果的第 i 位为 1
简而言之:如果零位多于一位,则该位置的结果将为零,否则结果将为 1
计算此值的最快方法是什么?
操作应该是关联的。这些数字的长度为 32 位,可以有多达 100000 个数字。
我建议你用一个运行 32 次的循环来做到这一点,数字中的每个位一次。
你屏蔽了除你想要的位之外的所有位,添加屏蔽的数字并查看结果 - 它给你 1 位的数量。
例如,像这样:
numbers = [ ..... ]
for i in range(32):
s = 0
for i in range(len(numbers)):
s + = (numbers[i] & 1)
numbers[i] = numbers[i] >> 2
if s < n / 2:
...
else:
...
我还没有测试过它,但你可以看到它的发展方向。
另一个可能更快的想法是只遍历一次你的数字,并记录谁赢了 - 0 或 1 并行表示所有 32 位。为此,您可以使用四个字节查找表,并在数组中保留 32 个计数器,这些计数器由查找的值更新。