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.

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.

var sum = 0;
var sumCarry = 0;
var anyCarry = 0;

for (var b : values) {
    var c = sum & b;
    sum ^= b;
    anyCarry |= sumCarry & c;
    sumCarry ^= c;
}

var setTwice = ~sum & sumCarry & ~anyCarry;

You could probably use a Map to maintain counts. Most of the following is just setup and visualization. It's just the getExclusivePairs that you need:

import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.IntStream;
import java.util.stream.Collectors;

public class BitSets {
    public static void main(String[] args) {
        int[] bitSets = new int[9];
        final int MASK = 0b1_1111_1111;
        ThreadLocalRandom rand = ThreadLocalRandom.current();
        IntStream.range(0, bitSets.length).forEach(ix -> bitSets[ix] = rand.nextInt() & MASK);
        System.out.println("  8 7654 3210");
        System.out.println("-------------");
        for (int j = 0; j < bitSets.length; j++) {
            System.out.printf("%d %s%n", j, StringUtils.toBinaryStringGrouped(bitSets[j]).substring(28));
        }

        Map<Integer, List<Integer>> found = getExclusivePairs(bitSets); 
        found.entrySet().
            stream().forEach(e -> System.out.printf("Bit %d is set exactly twice in the following bitsets: %s%n", e.getKey(), e.getValue()));
    }

    private static Map<Integer, List<Integer>> getExclusivePairs(int[] bitSets) {
        Map<Integer, List<Integer>> counter = new HashMap<>();
        for(int ixBitset = 0;ixBitset < bitSets.length;ixBitset++) {  
            for(int ixBit = 0;ixBit < bitSets.length;ixBit++) {  
                boolean isSet = (bitSets[ixBitset] & (1 << ixBit)) > 0;
                if (isSet) {
                    counter.computeIfAbsent(ixBit, k -> new ArrayList<Integer>()).add(ixBitset);
                }
            }
        }
        return counter.entrySet().stream().filter(e -> e.getValue().size() == 2).collect(Collectors.toMap(Map.Entry::getKey,
                    Map.Entry::getValue));
    }
    private static class StringUtils {
        public static String toBinaryStringGrouped(int n) {
            return StringUtils.grouped(StringUtils.toBinaryString(n));
        }

        private static String grouped(String s) {
            StringBuilder sb = new StringBuilder(s);
            for (int i = sb.length() - 4; i >= 4; i -= 4) {
                sb.insert(i, '_');
            }
            return sb.toString();
        }

        public static String toBinaryString(int n) {
            StringBuilder sb = new StringBuilder("00000000000000000000000000000000");
            for (int bit = 0; bit < 32; bit++) {
                if (((n >> bit) & 1) > 0) {
                    sb.setCharAt(31 - bit, '1');
                }
            }
            return sb.toString();
        }
    }
}