WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #169 Div2 D "Little Girl and Maximum XOR"

問題

AからBの間でXORしたときに最大になるような
2つの整数を選び、そのXORしたときの値を返せ。

例)
A=1 B=2
2(10) xor 1(01) = 3(11)が最大

A=8 B=16
15(01111) xor 16(10000) = 31(11111)が最大

A=1 B=1
1(1) xor 1(1) = 0(0)が最大

制約

1 <= A <= B <= 10^18

考えた事(2時間)

AとBの数が大きく、最大で60ビットぐらいになっちゃうから、
ビット毎に全探索はむりだな~

答えとなる2つの数をx,y(x<=y)として、yは1、xは0にしても大丈夫な
最上位のビットを探す。

たとえばA=8 B=16ならば重み16のビット
A=100 B=50ならば重み64のビット
A=5 B=3ならば重み4のビット
A=16 B=17ならば重み1のビット
・・・がそんなビットになる。

そのビットはyは1、xは0にしなきゃだめ。
(そうしなきゃxorしたとき最大値にならない)
そしてyはそれより下位のビットを全部0に
xはそれより下位のビットを全部1にした時、xorで最大値となる。
y=..1000000..
x=..0111111..

だから見つけたビットから全部1にした1111111・・・という値が答え

ソースコード
typedef long long ll;

int main() {
    
    ll A, B;
    cin >> A >> B;

    // yは1に、xは0にすることが出来る
    // 最上位のビットを見つける
    int b = 62;
    for( ; b >= 0; b-- ){
        ll num = 1LL << b;
        if( A < num && num <= B ){
            // あった!
            break;
        }else if( num <= A && num <= B ){
            // このビットは両方1にしなくちゃだめ
            A -= num;
            B -= num;
        }else{
            // このビットは両方0にしなくちゃだめ
        }
    }

    ll res = 0;
    for( ; b >= 0; b-- ){
        ll num = 1LL << b;
        res += num;
    }

    cout << res << endl;
}