XOR の性質
ABC121-Dが競技中に解けなかったので、XORの性質について調べて追記していく。コードはpython。
基本
「^」で計算できる。
a = 1 b = 2 c = a^b # 3
整数をビットごとに考えて、aとbで0/1が異なる場合に1それ以外は0となる。
性質
1. 0とXORを取っても値は変わらない
a = 12 b = 0^a # 12
2. 自分自身とXORを取ると0となる
a = 12 b = a^a # 0
3. 左右を交換できる
a = 12 b = 5 a^b == b^a # True
4. 自身にプラス1した数とXORを取ると1になる
a = 12 b = a+1 c = a^b # 1
5. 数の集合の中でXORを取るときには桁ごとに考えていい
足し算のように繰り上がりしないので、桁ごとに答えを考えていくことができる。
6. a==a^b^b
2よりb^bの部分は0で、1よりa^0はaであることから導ける
