[SOLVED] find the bit position(s) which are exactly set twice over multiple bit fields

find the bit position(s) which are exactly set twice over multiple bit fields

I've 9 bit fields every bit field has 9 nine bits, the 9 LSBs of an int. I want to find the bit position(s) which are exactly set twice over all bit fields.

e.g:

    0.1111.1111
    0.0000.1101
    0.0001.1101
    0.0001.1101
    0.0010.1101
    0.0010.1101
    0.0100.1101
    0.0100.1101
    0.0000.0010

In this example its bit position 1 because at this position the 1 is exactly set two times.

The first time in the first bit field, the second time in the last bit field.

Currently I do a "positional population count" on ints. for every possible bit field, there are 512, I have a corresponding long bit mask, which is used to count the frequency of set bit positions.

0.0100.1101 -> 0000.0000.0001.0000.0000.0001.0001.0000.0001

I sum up the 9 long bit masks of the 9 bit fields. So the first 4 LSBs of the sum represent the frequency bit 0 is set. The second 4 bits represent the frequency bit 1 is set. And so on, so I can scan for a frequency of 2.

This works, but its not as fast as I hoped.

Is there a faster algorithm which I can implement in Java?

I don't need to know all bit positions with a frequency of 2, just one bit position is fine.

Solution

Compared to a full pos-popcount, there is a shortcut.

You can find out two things:

which bits are set at least twice
which bits are set at least 3 times

Then you can find the bits that are set exactly twice as the intersection of the bits that are set at least twice with the bits that are not set at least 3 times.

int set_a1 = 0;
int set_a2 = 0;
int set_a3 = 0;
for (int i : values) {
    set_a3 |= set_a2 & i;
    set_a2 |= set_a1 & i;
    set_a1 |= i;
}
int set_twice = set_a2 & ~set_a3;

Then you can use Integer.numberOfTrailingZeros to get the position of the first (starting from the lsb) bit that was set twice.