SRM519 Div1Easy BinaryCards

考察

あるカードをドット面にするとき、それ以下のカードは全部ドット面…じゃあ、めくるカードの集合を出せばいけそう。
1~32まで手でシミュレーションをしていると、「AからBまで遷移させる操作の中で、めくるカードはA^Bの最上位bit以下のもの」であることがわかる。あとはそれを全部めくったものが答え。

ex)

A=1001(9)からB=1100(12)の遷移は9:{1001,1011}→10:{1010}→11:{1011,1111,1101}→12:{1100}であり、めくるカード全体は0111。これはA^B=0101の最上位bitから確認できる。

実装

肝心の、最上位bitの良い求め方がわからなかったので調べたら面白いページが出てきた。明日使えないすごいビット演算.いくつか拝借して関数化した。
maxって型違うと比較できないんだ…というか0はint型なんだ。

#include <bits/stdc++.h>
using namespace std;

class BinaryCards {
public:
    // 最上位bit
    unsigned long long MSB(unsigned long long n){
        n=n&0xFFFFFFFF00000000?n&0xFFFFFFFF00000000:n;
        n=n&0xFFFF0000FFFF0000?n&0xFFFF0000FFFF0000:n;
        n=n&0xFF00FF00FF00FF00?n&0xFF00FF00FF00FF00:n;
        n=n&0xF0F0F0F0F0F0F0F0?n&0xF0F0F0F0F0F0F0F0:n;
        n=n&0xCCCCCCCCCCCCCCCC?n&0xCCCCCCCCCCCCCCCC:n;
        n=n&0xAAAAAAAAAAAAAAAA?n&0xAAAAAAAAAAAAAAAA:n;
        return n;
    }
    long long largestNumber( long long A, long long B ){
        long long diff=MSB(A^B);
        return (B|(max(diff-1,0ll)));
    }
};