201. Bitwise AND of Numbers Range

• Difficulty: Medium

• Topics: Bit Manipulation

• Similar Questions:

Problem:

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: [5,7]
Output: 4

Example 2:

Input: [0,1]
Output: 0

Solutions:

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int ret = 0;
        stack<int> mBitValues;
        stack<int> nBitValues;

        while (m > 0) {
            mBitValues.push(m&(-m));
            m -= m&(-m);
        }

        while (n > 0) {
            nBitValues.push(n&(-n));
            n -= n&(-n);
        }

        while (!mBitValues.empty() && !nBitValues.empty() && mBitValues.top() == nBitValues.top()) {
            ret += nBitValues.top();
            mBitValues.pop();
            nBitValues.pop();
        }

        return ret;
    }
};