【Atcoder】ARC129 A - Smaller XOR を解いていこう！《C++，解説》

#初めに
　皆さんこんにちは！ 競プロの問題の理解を深めるために解説記事を書いていこうと思います！今回は ARC129 A です！
気に入っていただけたらLGTMして頂けるとうれしいです！
何かあればコメントや[Twitter]{https://twitter.com/python05238919}からお願いいたします!
それでは解いていきましょう！

#A - Smaller XOR
####問題概要
$A \leq B \leq C$
####制約
・$1 \leq N \leq 10^{18} $
・$1 \leq L \leq R \leq 10^{18} $
・入力はすべて自然数

##考察
まずXORについて述べます．
####XORとは？
XORとは排他的論理和といい，以下の真理値となります．つまりどちらかが真のときは真であり，どちらも真もしくは偽のときは偽になります．

$x$	$N$	出力
0	0	0
1	0	1
0	1	1
1	1	0

####入力例2で考えてみる．
　入力は以下になります

10 2 19

10を2進数にすると $10 = 1010_{(2)}$ となります．2進数で$N$と$x$が1の桁数が条件である$(x \oplus N ) < N$を満たします． 実際に$x=1aaa_{(2)}$のとき

1000 xor N = 0010 // < N
1001 xor N = 0011
1010 xor N = 0000
1011 xor N = 0001
1100 xor N = 0110
1101 xor N = 0111
1110 xor N = 0100
1111 xor N = 0101　//8個が満たす

　このように8個の整数が条件を満たすことがわかります．
　これにより$N$で１の桁数が条件を満たします．また$x$は範囲が決まっているのでそれを考慮すると条件を満たす整数の数は1の桁を$i$すると範囲$R$まででは
$min(R, 2^{i+1}-1) - (2^{i}-1)$
となります．差をとっているのは$i$の桁を数を求めています．
実際に$i = 3$のとき代入すると
$15 - 7 = 8$
　より上記と一致します．
同様に$i = 1$のとき
$3 - 1 = 2$
これより
$8+2=10$
よって答えが一致することがわかります．

実際には$L$では差をとり，$R$では和をとることで答えが導きます．
それでは実装していきましょう！

##実装
$N$を2進数にはせず，bitを用いることにより$0$か$1$か見ていきます．これにより計算量は$O(log_2N)$となります.
各桁で整数を数えたときに負の数にもなりうるので
$max(0, min(R, 2^{i+1}-1) - (2^{i}-1))$
このようにして実装します．
また**$L$は範囲内に含まれる**ので$0$から$L$より小さい範囲を$0$から$R$の範囲を引くことで答えを出します．

##正解コード
正解コードは以下になります．

#include <bits/stdc++.h>
using namespace std;
 
int main(){
//入力
    long long N, L, R, ans = 0, cntR = 0, cntL = 0;
    cin >> N >> L >> R;
    for(int i = 63; i >= 0; i--){
        if((1LL << i) & N){
        //Rでの条件を満たす
            cntR = min(R, (1LL << (i+1))-1);
            cntL = (1LL <<i)-1;
            ans += max(0LL, cntR - cntL);
            cntR = min(L-1, (1LL << (i+1))-1);
            cntL = (1LL << i) - 1;
            ans -= max(0LL, cntR - cntL);
        }
    }
    cout << ans << endl;
}