在一组数字中找到一个独特的位

Question

解释这一点的最佳方式是演示.

有一组数字.它们可能会重复,因此:

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

我正在寻找的数字是有点设置的数字,不会出现在任何其他数字中.结果是数字(在这种情况下为1 - 第一个数字)和位位置(或掩码很好)所以1000(第4位).可能有多个解决方案,但为此目的,它可能是贪婪的.

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

N&〜(其他数字也在一起)

但是比特的本质是,如果你在盒子外思考,总有一种更好的方法.例如,出现多次的数字永远不会有唯一的位,并且对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]

您可以使用技巧在设置示例的循环中更有效地提取位索引,但由于此代码在大多数"单词大小"时间执行,因此可能不值得.

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