finding the common parent of multiple BitSets java

Question

I couldn't find a proper solution to this simple question in Bitset methods. The question is to find the common parent of bitsets, starting from the left most bit. Here are some examples:

011
010
001
Common Parent: 0

00 
010
Common Parent: 0

00
11
10
Common Parent: None

1101
111
1100
Common Parent: 11

My solution was to AND the Bitsets, and then find the correct length by looking for the first set bit on XOR of these Bitsets. It worked for some cases but failed for others. I have another idea which involves looping over the Bitsets which I would be very happy to avoid if you have a solution.

[I know that they can be presented as a binary tree, but that involves a memory overhead which I would like to avoid by operating only over the bitsets and some boolean operations (AND, OR, NOR, NAND, XOR)]

joel314 joel314 · Accepted Answer · 2016-05-25T05:59:04

You could for example do something like this:

    String[] input = {"011","010","001"};

    if(input.length==0) return ;
    int n=input[0].length();
    List<BitSet> bitsets = new ArrayList<>();
    for(String in:input){
        // n is the min length of the inputs
        n=Math.min(n,in.length());
        // If you start counting the indices from the left, you need to reverse the inputs
        String reverse = new StringBuilder(in).reverse().toString();
        // Create the actual bitsets
        BitSet b = BitSet.valueOf(new long[] { Long.parseLong(reverse, 2) });
        bitsets.add(b);
    }

    for(int i=0;i<n;i++){
        boolean equals=true;
        for(int j=1;j<bitsets.size();j++)
            equals &= bitsets.get(j-1).get(i)==bitsets.get(j).get(i);
        if(equals)
            System.out.print(bitsets.get(0).get(i)?"1":"0");
        // You can also print the indices if needed.
    }

I wrote a few comments in the code. I hope it helps!

finding the common parent of multiple BitSets java

3 Answers