# 201. Bitwise AND of Numbers Range

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

# Solution

Approach 1: Apply bitwise And for every number.

Approach 2: Bit manipulation.

# Code (Python)

Approach 1:

Approach 2:

# Code (C++)

Approach 1:

// Time Limit Exceeded.
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int bitwiseAnd = -1;
        for (int i = m; i <= n; ++i)
        {
            bitwiseAnd &= i;
        }
        return bitwiseAnd;
    }
};

Approach 2:

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int numOfZero = 0;
        while (m < n)
        {
            numOfZero++;
            m >>= 1;
            n >>= 1;
        }
        return n << numOfZero;
    }
};

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        while (m < n)
        {
            n &= n - 1;
        }
        return n;
    }
};