javaで「^=」という演算子を使った時の処理

Question

leetcodeの問題を解いています。

Cells with Odd Values in a Matrix

インプットが n = 2, m = 3, indices = [[0,1],[1,1]]の場合、
２行３列のマトリクスができて、indicesに入っている配列がそれぞれ[行,列]に該当し、
１ずつ加算されていきます。

例えば、indices[0]は[0,1]ですが、マトリクスの０行目にすべてプラス1、１列目にすべてプラス1、という具合です。

最終的なアウトプットはマトリクス内の奇数の数を出力することなのですが、これに対する解法で理解できない箇所があります。

    public int oddCells(int n, int m, int[][] indices) {
        boolean[] oddRows = new boolean[n], oddCols = new boolean[m];
        for (int[] idx : indices) {
            oddRows[idx[0]] ^= true; // if row idx[0] appears odd times, it will correspond to true.
            oddCols[idx[1]] ^= true; // if column idx[1] appears odd times, it will correspond to true.
        }
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cnt += oddRows[i] ^ oddCols[j] ? 1 : 0; // only cell (i, j) with odd times count of row + column would get odd values.
            }
        }
        return cnt;
    }

特にこの
oddRows[idx[0]] ^= true;

に関してなのですが、^=がXORであることは調べてわかりましたが、なぜ^=をつかうことで、idx[0]が奇数回出現した場合にTrueにできるのかがいまいちわかりません。

詳細をおしえていただけますと幸いです。

Answer 1

XORと加算

XORは2進数の加算器で下一ケタ目の演算結果を求めるのに使います。2進数が偶数/奇数か判定するには下一ケタ目だけあればよい、0:偶数、1:奇数。

2進数の加算を示します。繰り上がりは無視。下一ケタ目をプログラムで求めるなら加算結果の2の剰余を取ります。

A	B	A+B	下1桁目=(A+B)%2
0	0	00	0
1	0	01	1
0	1	01	1
1	1	10	0

0:false、1:trueの置き換えを行うと上の加算結果とXORは同型です。

A	B	A^B
false	false	false
true	false	true
false	true	true
true	true	false

つまり、oddRows[idx[0]] ^= true;は1を足して下一ケタ目を求めているのと同じ。しかも桁溢れしません。

さらに0:false:偶数、1:true:奇数と置き換えると次が導かれます。

A	B	A+B
偶数	偶数	偶数
奇数	偶数	奇数
偶数	奇数	奇数
奇数	奇数	偶数

これはcnt += oddRows[i] ^ oddCols[j] ? 1 : 0;の偶奇判定で使っています。

まとめ

カウンターに1を足して最後に合計を偶奇判定するのが素直なやり方です。しかし偶数か奇数かを知るには常に2進数の下一ケタ目を保持すればよい。1を加算して下一ケタ目を求める計算は(A+1)%2、それと同型な論理演算子のXORを使います。((((false ^ true) ^ true) ^ true) ^ true) ...

boolean[]の初期値

boolean配列の要素の初期値はすべてfalseです。

boolean[] oddRows = new boolean[n], oddCols = new boolean[m];

Comments

[macaroni323]

詳細なご回答ありがとうございました。理解できました。

Answer 2

false ^ true = true
true ^ true = false

つまり、演算を行うたびtrueとfalseが切り替わります。
そのため、奇数回、偶数回がそのままtrue,false に対応します。

Comments

[macaroni323]

ご回答いただきありがとうございました。

Answer 3

oddRows、oddColsというのはbooleanの配列です。
ということで、
oddRows[なんたら] ^= true;
というのは、そのナカミを反転しているってことですね
oddRows[なんたら] = !oddRows[なんたら];
と同じことをしてます

そこで奇偶を出してるわけじゃないですね

Comments

[macaroni323]

ご回答いただきありがとうございました。