找到多个BitSets java的公共父级

Question

我在Bitset方法中找不到这个简单问题的正确解决方案.问题是从最左边的位开始找到位集的公共父节点.这里有些例子:

011
010
001
Common Parent: 0

00 
010
Common Parent: 0

00
11
10
Common Parent: None

1101
111
1100
Common Parent: 11

我的解决方案是AND位组,然后通过查找这些位组的XOR上的第一个设置位找到正确的长度.它适用于某些情况,但其他情况则失败.我有另一个想法,涉及循环比特集,如果你有一个解决方案我会很乐意避免.

[我知道它们可以作为二叉树呈现,但是这涉及一个内存开销,我想通过仅操作位集和一些布尔操作(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.
    }

我在代码中写了一些注释。我希望它有帮助！