java - 找到多个 BitSets java 的共同父级

Question

我无法在 Bitset 方法中找到这个简单问题的正确解决方案。问题是从最左边的位开始找到位集的公共(public)父级。以下是一些示例:

011
010
001
Common Parent: 0

00 
010
Common Parent: 0

00
11
10
Common Parent: None

1101
111
1100
Common Parent: 11

我的解决方案是对位集进行与运算，然后通过查找这些位集的 XOR 上的第一个设置位来找到正确的长度。它适用于某些情况，但对其他情况无效。我有另一个想法涉及循环 Bitsets，如果您有解决方案，我很乐意避免这种情况。

[我知道它们可以表示为二叉树，但这涉及内存开销，我想通过仅对位集和一些 boolean 运算(AND、OR、NOR、NAND、XOR)进行操作来避免这种开销]

Answer 1

例如，你可以这样做:

    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.
    }

我在代码中写了一些注释。希望对您有所帮助!