特殊的按位运算



我想对一组数字执行按位运算。让我们假设数字 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 个计数器,这些计数器由查找的值更新。

相关内容

  • 没有找到相关文章

最新更新