位运算问题

Question

有没有一种方法可以仅使用位运算来找到被设置次数最少的位？

例如，如果我有三位数组:

11011001

11100000  
11101101

仅在三个向量中的 1 个向量中，位置 3 和 5 中的位被设置为 1。

我目前有一个 o(n) 解决方案，其中 n 是位数组中的位数，我遍历位数组中的每个位并在每次出现 1 时递增，但是对于出于某种原因，我认为有一个 o(1) 解决方案，我可以使用它进行少量的按位运算。有人可以建议吗？谢谢。

Answer 1

如果值的总数有限，您可以使用重复/移位/掩码方法来分隔位，并且可能比迭代移位方案更快一点。

例如，对于每个“位”8 位值，假设不超过 15 个值:

bits1 = (bits >> 3) & 0x11;
bits2 = (bits >> 2) & 0x11;
bits3 = (bits >> 1) & 0x11;
bits4 = bits & 0x11;
bitsSum1 += bits1;
bitsSum2 += bits2;
bitsSum3 += bits3;
bitsSum4 += bits4;

然后，最后将每个 bitsSumN 值分成两个 4 位计数。