Special bitwise operation
I want to perform an bitwise operation on a set of numbers. Let's assume the numbers 11, 18, 2 and 8. The operation is as follows:
01011
10010
00010
01000
01010 (ans)
Logic when n is even - For a set of n numbers the ith bit of result is 0 if at least n/2 +1 of the numbers have ith bit set to zero. The ith bit of result is 1 if at least n/2 of the numbers have ith bit set to one
Logic when n is odd - For a set of n numbers the ith bit of result is 0 if at least (n+1)/2 of the numbers have ith bit set to zero. The ith bit of result is 1 if at least (n+1)/2 of the numbers have ith bit set to one
In a nutshell: If there are more zero bits than one bits then the result for that position will be zero else the result will be one
What can be the fastest way to compute this?
Operation should be associative. The numbers are 32 bit long and there can be as many 100000 numbers.
I'd suggest you do this with a loop that runs 32 times, once for each bit in the number.
The you mask out all the bits except the ones you want, add the masked numbers and look at the result - it gives you the number of 1 bits.
Eg something like this:
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:
...
I haven't tested it, but you can see where it's going.
Another idea that might be faster is to only loop through your numbers once and keep count of who is winning - 0's or 1's for all 32 bits in parallel. You can use four byte-lookup tables for this, and keep 32 counters in an array that get updated by the looked-up values.
链接地址: http://www.djcxy.com/p/57576.html下一篇: 特殊的按位操作