Java-операции над массивом целых чисел

Question

Я рассматриваю массив целых чисел в Java.Размер массива определяется в начале программы пользователем

Моя идея состоит в том, что - учитывая любую позицию для соответствующих двоичных значений - результат должен показывать 1 для любого бита, где только один из операндов имеет1 и 0 для любой другой комбинации.Процесс может быть лучше объяснен следующими примерами

Массив, такой как {4,5,6}, должен возвращать 3, потому что:

  100
  101
  110
  ---
= 011

ИЛИ для чисел {12,4,9}

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

Я думал сделать это таким образом, но я понял, что - поскольку я работал с XOR - мой код для первого примера вернет 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

Возможно, есть более разумный способ, но вы можете решить его итеративно, выбрав биты, которые присутствуют только один раз в вашем массиве, и ИЛИ, совместив их.Вот способ сделать это с помощью потоков:

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 2

Я думаю, что вы можете сделать это довольно просто, отслеживая, какие биты не являются уникальными.

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, фактически позволяя нам считать до 2. dup затем отслеживает каждый бит, который мы видим более одного раза.

В конце мы просто делаем all & ~dup, который удаляет любой бит, который мы видели более одного раза.

Answer 3

Понять так:

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.

Если вы хотите установить более двух 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);

    }