Java 对整数数组的操作

Question

我正在考虑 Java 中的整数数组。数组大小由用户在程序开始时确定

我的想法是 - 给定相应二进制值的任何位置 - 对于只有一个操作数具有 1 的任何位，结果应显示 1，对于任何其他组合，结果应显示 0。通过以下示例可以更好地解释该过程

这样的数组 {4,5,6} 应该 return 3 因为：

或数字 {12,4,9}

12 = 1100
 4 = 0100
 9 = 1001
---------
Val- 0001

我想这样做，但我意识到 - 因为我使用 XOR - 我的第一个示例的代码将 return 7 :

static void cpuTurn(int[] nimArray){
    int[] val = new int[nimArray.length];
    int holding = 0;

    for (int i = 0; i < nimArray.length; i++) {
        holding = holding^nimArray[i];
    }
}

如何正确实现这个操作？

Answer 1

这样理解：

holding = 0
at 4:
holding = holding ^ 4; // 0 ^ 4 = 4 i.e. holding = 4, binary => 0 ^ 100 = 100  
at 5:
holding = holding ^ 5; // 4 ^ 5 = 1 i.e. holding = 1, binary => 100 ^ 101 = 1 
at 6:
holding = holding ^ 6; // 1 ^ 6 = 7 i.e. holding = 7, binary => 1 ^ 110 = 111

因此持有的最终价值是7。

如果要设置超过2个1出现次数为0

    public static int[] split(int num){
        int[] splits = new int[31]; 
        for(int i=0; i < 31; ++i){
            splits[i] = (num>>i & 1);
        }
        return splits;
    }

    static void cpuTurn(int[] nimArray){
        int[] val = new int[nimArray.length];
        int holding = 0;
        int [] holdings = split(holding);
        for (int i = 0; i < nimArray.length; i++) {
            int [] splits = split(nimArray[i]);
            for(int j = 0; j < splits.length; ++j)
                 holdings[j]+=splits[j]
        }

        int [] newVal = new int[31];
        int k =0;
        for(k = 0; k < 31; ++k)
            if(holdings[k]>1 || holdings[k]==0)
                newVal[k] = 0;
            else
                newVal[k] = 1;

        int finalValue = 0;
        for(k = 0; k < 31; ++k)
             finalValue |= newVal[k]<<k;

        System.out.println(finalValue);

    }

Answer 2

可能有更聪明的方法，但您可以通过选择仅在数组中出现一次的位并将它们组合在一起来迭代解决它。以下是使用流执行此操作的方法：

IntStream.range(0, 32)
        .map(i -> 1 << i)
        .filter(i -> Arrays.stream(array).filter(n -> (n & i) != 0).count() == 1)
        .reduce(0, (a, b) -> a | b)

Ideone Demo

Answer 3

我认为您可以通过跟踪哪些位不是唯一的来相当简单地做到这一点。

static int xor(int[] arr) {
    int all = 0;
    int dup = 0;

    for (int x : arr) {
        // for each x in arr, record the bits which are
        // in common with the bits we've already seen
        dup |= x & all;
        all |= x;
    }

    // remove bits which were not unique
    return all & ~dup;
}

想想这是如何工作的，你可以说变量 all 为每一位保留一个计数器，但我们只能数到 1。当我们做 x & all 时，我们得到一个 1我们在 x 中至少见过一次 plus 一次，有效地让我们数到 2。 dup 然后跟踪我们看到的每一位不止一次。

最后我们只做 all & ~dup 删除我们不止一次看到的任何位。

Java 对整数数组的操作

Java operations on an array of integers

java

arrays

boolean

xor

nim-game