ホームに戻る
XORに関する知見
競技プログラミングではXORを使った問題がよく見られます。
XORの基本的な動作は次のようなものです。
0^0 → 0
1^0 → 1
0^1 → 1
1^1 → 0
排他的論理和は要は1の数が奇数なら1、偶数なら0になると考えられます。
いくつかの数で排他的論理和をとる場合も実際にXORをとらなくても、
1の数を数えて偶奇を判定してXORの結果としても良い。
0^0^0 → 0 (1の数が偶数)
0^0^1 → 1 (1の数が奇数)
0^1^1 → 0 (1の数が偶数)
1^1^1 → 1 (1の数が奇数)
また、排他的論理和はビットの桁の繰り上がりが無い。
よって、排他的論理和によって与えられた数値の最大ビットを超えるビットを使用した数値はあらわれない。
また、各ビットの桁間で計算結果の移動が無いのでビットの桁ごとに分けて考えるという手法は良くある。
実際に各桁のビットを丁寧に見ていくだけで解ける問題がある。
ある桁のビットが1であるものの個数を求めるときに2分探索を用いることがある。
求めたい桁より上のビットを0クリアした後ソートすると、
求めたいビットが0か1かで分けることができ、その後2分探索で個数を数えることができる。
1回ソートしておいてその結果を何度も使う場合はこの方法は有効である。
排他的論理和にはビットの桁の繰り上がりが無いが結果が元の数値より大きくなることはありうる。
A^B>AあるいはA^B>Bということはありうる。
よって、0<=A,B<=10000000000であるからといって、
XORをとる問題である場合に起こりうる最大の値を10000000000に見積もってしまったり、
INFを定義する場合にINFを10000000001などとやってしまうと失敗する。
XORをとって値が2倍以上にはならないのでこの場合はINFを2000000000とすれば安全。
XORは加算や減算のように数値の増加や減少を保証しない。
よって、ある数値のXORをとったときに結果が増えるか減るかはXORをとる数値次第です。
よってXORをとった値でmaxを記録していくminを記録していくという場合にはうまくいかない場合が多い。
特に動的計画法でdp[N]=(XORをとる値)とすると失敗する場合がある。
動的計画法ならdp[N][XORをとる値]=(その場合の値)とすべきだろう。
特にXORはこの性質があるために問題に用いられることが多い。
次のような計算法則が成り立ちます。
A^0 = A
A^A = 0
A^B = B^A
A^B=C ならば A=B^C
意外に忘れがちなのですが、A^Bの答えはもちろん1通りです。
n個の数から2個取り出して排他的論理和がxになるようなペアはいくつか？
この場合にO(N^2)は必要ありません。O(N)で十分なので注意しましょう。
また、次のような法則も成り立ちます。
A+B >= A^B
A+B = A^B + ((A&B)<<1)
A^B = (A|B)-(A&B)
A&(B^C) = (A&B)^(A&C)
和と排他的論理和を使う問題はよく出ます。
例えば、A+B=X,A^B=YのときX,Yが与えられるのでA,Bを求める。
まず、X<Yのとき該当するA,Bは存在しない。
次に、和で桁上がりするビットは((X-Y)>>1)で特定できる。
よって、YのビットをAに割り振るか、Bに割り振るかで候補はすべて列挙できる。
例えば、X=100010,Y=11000であった場合、
((X-Y)>>1)=101である。
よって、A=??1?1,B=??1?1まで特定できる。
ここでYを見れば、?に何が当てはまるかわかる。
例えば排他的論理和を累積のように求めてある区間の排他論理和を求めることができる。
すなわち、{a,b,c,d,e,f}があったとき、
c^d^e^f = (a^b^c^d^e^f)^(a^b)
とできる。
最初に累積のように最初からの排他的論理和をとっておくことで、
連続した区間の排他的論理和をO(1)で求めることができる。
特に、
a^b^c^d^e^f=a^bであれば、c^d^e^f=0である。
いくつかの数の排他的論理和が0のとき、間のどこで分けても双方の排他的論理和は等しい。
a^b^c^d^e^f=0のとき、a^b^c=d^e^fでありa=b^c^d^e^fでもある。
a1,a2,a3,a4,...,anの時、全てのai^..^ajについてという問題があった場合、
bx = a1^a2^...^axとするとき、ai^...^aj=bi-1^...^bjとできる。
よって、左からbiを更新しつつbjで評価して全てのai^..^ajについてを実現する方法がある。
連続した数値のXORをとる場合の法則
f(x) = 1^2^3^...^x のとき、
結果はxが1増えるたびに1,x+1,0,x,1,x+1,0,x,... と繰り返す。
次のように続く
1:1
2:3
3:0
4:4
5:1
6:7
N個の数からいくつかの排他的論理和でXを作れるか判定する。
N個の値からいくつかを選択する場合、
いずれかの数といずれかの数の排他的論理和を何回とっても結果に影響しない。
例えば、
A,B,Cの3つの数があったとき、
A^B,B,CとしてもA^Bを選んだ場合はAとBを選んだことになり、
A^BとBを選んだ場合はAだけを選んだことになる。
この前提で次のような変換をする。
まず1xxx(xは0か1)となるような数を1つ選ぶ。
この数があれば他の数はすべて0xxxに変換できる。
0xxxである数のうち01xxとなるような数を1つ選ぶ。
同じように他のすべてを00xxに変換できる。
このような変換を続けると001xなどが選べない場合がある。
この場合は上位ビットの選択次第で自由に選べない。
例えば次のように結果が出たとする。
1101
0110
0001
0000
0000
先頭1番目のビットを1にしたければ1番目の数を選ばざるを得ない。
先頭1、2番目のビットを1にしたければ1番目を選び2番目を選ばない。
このように上から貪欲に立てたいビットを選択することが可能。
先頭3番目のビットは上位ビット次第で選べないビットとなる。
// vector v のいくつかの xor で p を作れるか？
long long f(vector<long long> v, ll p){
long long index = 0;
for(long long i = 62; i >= 0; i--){
long long flag = 0;
for(long long j=index;j<v.sz;j++){
if(v[j]&(1LL<<i)){
flag = 1;
swap(v[index],v[j]);
break;
}
}
for(long long j=index+1;j<v.sz;j++){
if(v[j]&(1LL<<i)){
v[j]^=v[index];
}
}
if(flag==1){
index++;
}
}
index = 0;
for(long long i = 62;i >= 0; i--){
if(index==v.sz)break;
if((v[index]&(1LL<<i))!=0&&(p&(1LL<<i))==0){
index++;
}
else if((v[index]&(1LL<<i))!=0&&(p&(1LL<<i))!=0){
p ^= v[index];
index++;
}
}
if(p==0)return 1;
return 0;
}
例題１：SRM543 EllysXors
LからRまでxorをとり続けた場合の結果を答えよ。
(1<=L<=R<=4000000000)
例えば、L=2、R=5なら、
(((2^3)^4)^5)=0
解法はこのようにできる。
long long f(long long a){
long long ret;
if(a%4==0)ret = a;
if(a%4==1)ret = 1;
if(a%4==2)ret = a+1;
if(a%4==3)ret = 0;
return ret;
}
long long L=2;
long long R=5;
long long ans = f(R)^f(L-1);
XORと加算が混合する問題は桁上がりが発生するのでややこしい。
この場合は桁上がりするとどうなるかを丁寧に考えてやるしかない。
例題２：Codeforces627A XOR Equation
A,Bは正の整数である。A+B=s、A^B=xのときA,Bの組み合わせは何通りか？
(2<=s<=1000000000000、0<=x<=1000000000000)
例えば、s=3、x=3のとき(A,B)=(1,2),(2,1)の2通り。
この場合はまずxに注目する。
xを2進数で見たときにその桁が[0,1]、[1,0]の組みなのか[0,0]、[1,1]の組なのかわかる。
次に、xが0の桁でsが1の桁である場合はその桁へ繰り上げが発生しないといけないことになります。
このことからどの桁が繰り上げられるべきかという桁がわかります。
繰り上げられるべき桁を繰り上げた結果とxを足すとsになるはずです。
そうならなければ答えは1つも存在しないことになります。
そうなれば答えが存在します。
解法はこのようにできる。
long long s, x;
cin >> s >> x;
long long c = 0;
long long d = 0;
int flag = 0;
for (int i = 60; i >= 0; i--) {
if ((x >> i) & 1)c++;
else {
if (flag == 1) {
d |= (1LL << i);
flag = 0;
}
if ((s >> i) & 1)flag = 1;
}
}
if (s != d * 2 + x)cout << 0 << endl;
else {
if (d != 0) printf("%I64d\n", (long long)pow(2, c));
else printf("%I64d\n", (long long)pow(2, c) - 2); // 繰り上げが発生しない場合に(3,0)、(0,3)のような解を除く
}
例題３：AtCoder Regular Contest 066 XOR Sum
任意の非負整数A,BがありA^B=u、A+B=vが成り立つ0<=u,v<=Nの範囲でのu,vの組み合わせは何通りか？
例えば、N=3のとき、u,v=(0,0)、(0,2)、(1,1)、(2,2)、(3,3)の5通り。
この場合はまず必ずu<=vであるという条件に注目する。
よって、vの上限を超えないようにすればuはu<Nの条件は必ず満たす。
ゆえにvの上限を超えないように上限を見ていく動的計画法を考える。
vは1回も桁上がりが許されない上限と1回だけ許される場合とそれ以外に分かれる。
1回だけ許される場合は1回繰り上げされると次は繰り上がりが許されない状態に戻る。
vの桁が0か1かでXORの(0,0)、(0,1)、(1,0)、(1,1)どのパターンが許されるか考えれば良い。
なお、(0,1)と(1,0)は和もXORも同じになるので1つの場合と考える。
// dには上の桁から2進数で0か1かが入っている。
// 最上位桁は必ず0である。
long long dp[100][3];
clr(dp,0);
dp[0][0] = 1;
for(int i = 1; i < 100; i++){
// 0
if(d[i]==0){
dp[i][0] += dp[i-1][0]; //(0,0)
dp[i][0] += dp[i-1][1]; //(1,1)
dp[i][1] += dp[i-1][1]; //(1,0)
dp[i][2] += dp[i-1][1]; //(0,0)
dp[i][2] += dp[i-1][2]*3; //(0,0)、(0,1)、(1,1)
}
// 1
else{
dp[i][0] += dp[i-1][0]; //(0,1)
dp[i][1] += dp[i-1][0]; //(0,0)
dp[i][1] += dp[i-1][1]; //(0,1)
dp[i][2] += dp[i-1][1]*2; //(0,0)、(0,1)
dp[i][2] += dp[i-1][2]*3; //(0,0)、(0,1)、(1,1)
}
dp[i][0] %= MOD;
dp[i][1] %= MOD;
dp[i][2] %= MOD;
}
cout << (dp[99][0]+dp[99][1]+dp[99][2])%MOD << endl;
