最好的解释方式是演示。
有一组数字。它们可能会重复,所以:
1110, 0100, 0100, 0010, 0110 ...
我正在寻找的数字是设置了位的数字,没有出现在其他任何数字中。结果是数字(在本例中为 1 - 第一个数字)和位位置(或掩码很好)所以 1000(第 4 位)。可能有不止一种解决方案,但为此它可能是贪婪的。
我可以通过迭代来做到...对于每个数字N,它是:
N & ~(其他数字 OR'd together)
但比特的本质是,如果您跳出框框思考,总会有更好的方法。例如,多次出现的数字永远不会有唯一的位,并且对 ORing 没有影响。
最佳答案
您只需要记录每个位是否被看过一次或多次,以及是否被看过两次或多次。独特的位是那些已经看到一次或多次而不是两次或更多的位。这可以使用按位运算有效地完成。
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 编写的。
关于c - 在一组数字中找到唯一的位,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8285962/