XOR - redultimate/utility GitHub Wiki
概要
- 排他的論理和
性質
- 実装は^を使えばそのままできる.
- 元の数の和を超えない.
- 任意の非負整数nについて
n ^ n = 0
n ^ 0 = 0
- 任意の偶数 n について
n ^ (n + 1) = 1
- 0からAまでのXORは次のように実装できる.
long long f(long long x) {
return (((x+1)/2)%2) ^ (x%2==0 ? x : 0);
}
-
XOR和と加算和が等しいとき
- 2進数で表したときの各桁の1の数の合計が1個以下の場合なので, 複数の数でそれが成り立つときには部分和も成り立つ.
-
累積XOR和
- a, b, cがあった時, b^c = a^(a^b^c) = 0^b^c = b^cなので, aまでの累積XOR和とcまでの累積XOR和を足せば間の累積XOR和が求まる.
注意
使用例
AGC035A XOR Circle
- 以下の2つの性質を使う.
n ^ n = 0
n ^ 0 = n
diverta E XOR Partitioning
ABC121D XOR World
ABC117D XXOR
ABC098D XOR Sum 2
- 尺取り法とXOR和と加算和が等しいときについてのお話.