Bit operation question

Question

Is there a way to find the bit that has been set the least amount of times from using only bit operations?

For example, if I have three bit arrays:

11011001

11100000  
11101101

the bits in position 3 and 5 are set to 1 in only 1 of the three vectors.

I currently have an o(n) solution where n is the number of bits in the bitarray, where I go through each bit in the bitarray and increment each time there is a 1, but for some reason I think there is a o(1) solution that I can use with few bitwise operations. Can anyone advise? Thanks.

Answer 1

You can use a duplicate/shift/mask approach to separate the bits and maybe be a little faster than an iterative bit shift scheme, if the total number of values is limited.

Eg for each "bits" 8-bit value, assuming no more than 15 values:

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

Then, at the end, break each bitsSumN value into two 4-bit counts.

Answer 2

Another option is to reflect the bit array. In your example:

111
111
011
100
101
001
000
101

And then use the standard bit counting methods to count the number of bits set.

Doing this naively would most likely be slower than the normal approach, but you could try to adjust the algorithms to pull the bits from different words instead of the techniques they use. The fastest techniques look at multiple bits at a time, though, so would seemingly be difficult to optimize in your case.