c - 在一组数字中找到唯一的位

Question

最好的解释方式是演示。

有一组数字。它们可能会重复，所以:

1110, 0100, 0100, 0010, 0110 ...

我正在寻找的数字是设置了位的数字，没有出现在其他任何数字中。结果是数字(在本例中为 1 - 第一个数字)和位位置(或掩码很好)所以 1000(第 4 位)。可能有不止一种解决方案，但为此它可能是贪婪的。

我可以通过迭代来做到...对于每个数字N，它是:

N & ~(其他数字 OR'd together)

但比特的本质是，如果您跳出框框思考，总会有更好的方法。例如，多次出现的数字永远不会有唯一的位，并且对 ORing 没有影响。

Answer 1

您只需要记录每个位是否被看过一次或多次，以及是否被看过两次或多次。独特的位是那些已经看到一次或多次而不是两次或更多的位。这可以使用按位运算有效地完成。

count1 = 0
count2 = 0

for n in numbers:
    count2 |= count1 & n
    count1 |= n

for n in numbers:
    if n & count1 & ~count2:
        return n

如果您不想对数字进行两次迭代，您可以跟踪您看到的包含每个位的某个数字。如果数字存储在磁盘上并且流式传输它们需要磁盘访问，这可能是一个很好的优化，但当然它会使代码更加复杂。

examples = [-1] * wordsize
count1 = 0
count2 = 0

for n in numbers:
    if n & ~count1:
        for i in xrange(wordsize):
            if n & (1 << i):
                examples[i] = n
    count2 |= count1 & n
    count1 |= n

for i in xrange(wordsize):
    if (count1 & ~count2) & (1 << i):
        return examples[i]

您可能会在设置示例的循环中使用技巧来更有效地提取位索引，但由于此代码最多执行 'wordsize' 次，因此可能不值得。

这段代码很容易转换为 C...为了清楚起见，我只是用 Python 编写的。