問題では最大データが2147483647とあるので、ビット0から30までを列挙し、すべての数値の各ビットに対してand演算を行えばよいのです。
データが大きいとタイムアウトします。
すべての数の位取り和を求めるには、桁の1つが0である限り、最終的な位取り和の結果もその場所で0でなければならないことに注意してください。
例えば、9、10、11、12を合計した場合、下位3桁はそれぞれその桁の数字が0なので、最終的な和の結果は下位3桁は0になり、4桁すべてが1である末尾4桁だけは和の結果が1になるので、その桁で合計したすべての数字の最終的な結果は末尾4桁で1になります。 上位桁の数字はすべて0なので、それ以上のことはありません。
ビット和の結果は、すべての数値の2進数の共通接頭辞であり、下位ビットはすべて0であることがわかります。たとえば、上記の例では、共通接頭辞は最後から4ビット目の1であり、下位3ビットはすべて0であるため、結果は1 0 0 0 0となり、8となります。
mからnまでの各数が少しずつ1ずつ加算されていくので、1ずつ加算されるたびに低い位置から変わっていくことになります。したがって、すべての数の共通接頭辞は、左右の端点mとnの共通接頭辞となります。したがって、mとnの共通接頭辞を求め、低い位置をすべて0で埋めればよいことになります。
共通接頭辞を求めるには、右シフト演算を使います。mとnを、2つの数が等しくなるまで同時に右にシフトします。もちろん、シフトした回数を記録しておき、シフトした回数だけmを左にシフトするのが最終的な答えです。
例えば上の図では、9と12は右に3回シフトした後、つまり共通の接頭辞1を見つけた後、1を左に3回シフトした後、等しくなります。
コードは以下の通り：
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int shift = 0; //右シフトの回数を記録する
while(m < n) { //mとnを同時に2つの数が等しくなるまで右シフトする。
m >>= 1;
n >>= 1;
++shift;
}
return m << shift; //whileループを抜けた後、mとnが共通の接頭辞となり、左に3回シフトした結果が答えとなる。
}
};
