D - XOR World

競プロ XOR

はじめに

競技プログラミング、AtCoder Beginner Contest 121
D - XOR World
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

f(A,B)をA,A+1,...,Bの排他的論理和としたとき、f(A,B)を求めてください。

▼排他的論理和とは
整数c1,c2,...,cnのビットごとの排他的論理和yは、以下のように定義されます。

・yを二進表記した際の2k(k≥0) の位の数は、
c1,c2,...,cnのうち、
二進表記した際の2kの位の数が1となるものが奇数個ならば1、偶数個ならば0である。

例えば、3と5の排他的論理和は6です(二進数表記すると: 011 と 101 の排他的論理和は 110 です)。

制約

・入力は全て整数である。
・0≤A≤B≤10^12

入力

入力は以下の形式で標準入力から与えられる。

A B

出力

f(A,B)を計算し、出力せよ。

解き方

以下を参考にしています。
drken1215.hatenablog.com
qiita.com

f(A,B)（A,A+1,...,B）の排他的論理和

まず、
求めなければならない「f(A,B)（A,A+1,...,Bの排他的論理和）」は
「f(0,B) XOR f(0,A-1)（(0～Bの排他的論理和) XOR (0～(A-1)の排他的論理和)）」と書き換えることができます。

これは、
XORの性質としてX XOR X=0（Xは任意の数）というものがあり
f(0,B)とf(0,A-1)のXORをとることによって
両者で重なっているf(0,A-1)の部分が全て0になり（X XOR X=0）
最終的に残る部分がf(A,B)になるからです。

参考と具体例：
qiita.com

また、通常の足し算ならば
3～10までの和を求める場合
上と同じ形にすると
(1～10までの和)ー(1～3までの和)＝(3～10までの和)
というように
全体を足した数から不要な部分を引くことにより
欲しい部分が求まりますが
XORでは引くのではなく、
XORすることで答えが出すことができます。

「足し算」と「引き算」がどちらもXORであることも
XORの特徴らしいです。

参考と具体例：
drken1215.hatenablog.com

特徴を見つける

f(0,X)を書き出してみると以下のようになります。

X 2進数 f(0,X)
0 0 0
1 1 1
2 10 11
3 11 0
4 100 100
5 101 1
6 110 111
7 111 0
8 1000 1000
9 1001 1
10 1010 1011
11 1011 0
12 1100 1100
13 1101 1
14 1110 1111
15 1111 0

上の書き出しから
Xが奇数のとき、f(0,X)は0と1を繰り返す
ということが分かります。

以上から、
以下のようにすればf(0,X)を求められることが分かります。

①Xが奇数のとき
(X+1)/2が偶数なら0、奇数なら1
すなわち、(X+1)/2%2

②Xが偶数のとき
Xが奇数のときの値は
上の式にXを入れるだけですぐ出せるので、これを利用する。
（Xが偶数のとき
f(0,X-1)とf(0,X+1)の値は上の式に入れるだけで
答えが分かる。）

出し方は以下の二通り
①f(0,X-1)を使う
②f(0,X+1)を使う

①f(0,X-1)を使う
f(0,X-1)はまだXとXORしていない状態なので
f(0,X)を出すには「X XOR f(0,X-1)」をする。

X 2進数 f(0,X)
3 11 0
4 100 100

Xを4とすると、
f(0,X-1)はf(0,3)すなわち0
f(0,4)は 0 XOR 100=100

②f(0,X+1)を使う
f(0,X+1)は余分に X+1 が XOR されている状態なので
f(0,X)を出すには「(X+1) XOR f(0,X+1)」をする。

X 2進数 f(0,X)
4 100 100
5 101 1

Xを4とすると、
f(0,X+1)はf(0,5)すなわち1
f(0,4)は 1 XOR 101=100
※XORは引き算もXOR

下のコードでは①を用いています。

全体のコード

using System;
using System.Linq;
using System.Collections.Generic;

class Damondai
{
    static void Main()
    {
        var ab = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
        var A = ab[0];
        var B = ab[1];
        //f(A,B)をf(0,B)^f(0,A-1)に変形
        var ans = Solve(A - 1) ^ Solve(B);
        Console.WriteLine(ans);
    }
    static long Solve(long num)
    {
        //奇数の場合
        if (num % 2 == 1) return Calc(num);
        //偶数の場合
        else
        {
            //0なら0を返す
            if (num <= 0) return 0;
            //Xが偶数のとき f(0,X)=X^(X-1)
            return num ^ Calc(num - 1);
        }
    }
    static long Calc(long num)
    {
        return (num + 1) / 2 % 2;
    }
}