SRM519 Div1 Easy - BinaryCards

問題

64枚のカードがあり、i番目のカードの片面には2^i個の点が書いてある 裏は真っ白
a<=i<=bの各iについて、小さいiから順に、「カードを何枚かひっくり返し、計i個の点が見える状態にする」という操作をしていく
各操作では目的達成に必要な最小枚数しかひっくり返さず、複数枚ひっくり返す必要があるときは、書いてある点が多いカードから順にひっくり返す
ある瞬間に見えている点の個数の最大値を求める
1 <= a <= b <= 10^18

解法

例えば末尾が-01111となっている数字の個数だけ点が見えている状態から次の-10000に移るとき、カードをひっくり返す順番の制約より、点の数は
01111 -> 11111 (-> 10111 -> 10011 -> 10001 -> 10000)
と移り変わる
こういう瞬間を考えると、「aとbで異なるbitのうち最も左のもの」以下のbitを全て1にしたもの とaのorが答えになることがわかる

class BinaryCards {
	public:
	ll largestNumber(ll a, ll b) {
		for (int i = 63; i >= 0; i--) if ((a>>i&1)^(b>>i&1)) return b | ((1ll<<i)-1);
		return a;
	}
};