なぜこの記事を作成しようと思ったの?
この問題に負けたからです。
あと、普通に$XOR$ってめっちゃ出題されるから。
対象読者
900問以上解いても茶色coderな人にぶっさされ！
XORの基本
C++では排他的論理和($XOR$)は^と書きます。($\oplus$も^と同じです。併用します。)
a^bについて以下が成立します。
| a | b | a^b |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
つまり、 異なるビット同士なら1になって、同じビット同士なら0になるという性質があります。例として、$5 \oplus 3=101_{2} \oplus 011_{2}=110_{2}=6$ですね。
灰色以上なら知っておきたいXORの性質
1 , 同じ数同士のXORは0
当たり前ですね。再掲しますが、異なるビット同士なら1になって、同じビット同士なら0になるという性質 があるため、これが成り立ちます。
a^a=0です。
2, 0とのXORは変わらない。
もう上の表を見てください。$0$との$XOR$は変わっていませんね？a^0=aです。
まとめ方に難あり。故にこのような自明なことにいちいち理由をつけなければならないという苦行を強いられている
3,XORは交換できる。
つまり、交換法則があるってことです。a^b=b^aです。これも上の表から自明です。見てください。a,bの位置を変えてもXORは同じですね！
4,XORは結合できる。
結合法則のことです。(a^b)^c=a^(b^c)が成り立ちます。
たかだか状態は8通りしかないので、それぞれについて結合法則が成り立つことを証明すればよいです。
しかし、8通りもやってられないので(?)ここでは違う考え方を提供します。
XORは1の個数の偶奇性によって結果が決まります。
上の表を確認してください。
a,bについて、1の個数の偶奇はXORした後も変化しません。3つの整数a,b,cに対して、(a^b)^cとa^(b^c)を考えましょう。いずれの場合でも各ビット位置の結果は、(a,b,c) のそのビット位置にある1の個数が奇数なら1,偶数なら0となります。つまり、XORする順番を変えても各ビットにおける1の個数は変化しません。よって、結合法則が成り立ちます！
5,XORは自分自身で打ち消せる。
a^b^b=aです。1,2,4の性質から成り立ちます。まずb^bから計算するとa^0となるのでこれは性質2よりaになります。
ここまでのXORの性質を利用することで、次の問題が解けるようになりました!
ABC213-A Bitwise Exclusive Or
茶色以上なら知っておきたいXORの性質
1,XORはビットごとの足し算を2で割った余り
a^b = a+b(mod 2)です。ここで、これは整数全体の式ではなく、各ビットの値($x,y∈${$0,1$})に対して成り立つ式だということを念頭においてください。
2,連続する整数のXORには周期性がある。
$F(n)=0\oplus 1\oplus 2 \oplus \dots \oplus n$とすると、$F(n)$はmod 4によって決まります。
| F(n) | n mod 4 |
|---|---|
| n | 0 |
| 1 | 1 |
| n+1 | 2 |
| 0 | 3 |
他にもこれに関連して、
任意の偶数について、n^(n+1)=1 という性質があります。これは簡単に示せるので、読者への練習問題とします。
具体例
- ABC121-D XOR World diff1164
- ABC185-F Range Xor Query diff1053
3,XORの総和はビット位置ごとに数えられる。
整数列Aの全てのペアについて、
$$\sum_{i<j}(A_i \oplus A_j)$$を求めたくなったとします。
ここで、各bit位置$k$について着目しましょう。
そのビットが1であるような要素数を$C_1$,0であるような要素数を$C_0$とします。
XORがそのビットで1になるときは、片方が1でもう片方が0のペアだから、$C_1 C_0$がペア数になり、そのビット値$2^k$をかければよいので、これを各bitについてやればよいです。
具体例
- ABC147-D Xor Sum4diff1205
4,普通の足し算とXORが等しくなる条件
非負整数a,bについてa+b=a^b ⇔ a&b=0が成立します。ここで&はビットごとのAND演算の事です。a,bの同じビット位置が両方1であると繰り上がりが発生します。一方、XORではその位置は0になります。逆に、共通して1になるビットが存在しなければ繰り上がりは起きないので、XORと足し算が一致します。例えば、5+2=7,5^2=7です。そして、$5=101_2,2=010_2$で正しいですね！
具体例
- ABC098-D Xor Sum 2diff 1404
ここまで読んでいただき、ありがとうございます！