Question

Formatted question description: https://leetcode.ca/all/201.html

 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

Algorithm

There are three digits in example [5, 7]. Write their binary as:

101  110  111

The result of the AND is 100. If we observe carefully, we can conclude that the final number is the common part of the left side of all the numbers in the range.

If the above example is not obvious, let’s look at another range[26, 30] , Their binary is as follows:

11010  11011  11100  11101  11110

After discovering the pattern, we only need to write code to find the common part on the left.

Shift m and n, shift one bit to the right at a time, until m and n are equal, record all the number of shifts i, and then shift m back to the left by i, to get the final result.

Code

Java

public class Bitwise_AND_of_Numbers_Range {

    // 5,6,7,8
    // 101,110,111,1000
    public int rangeBitwiseAnd(int m, int n) {
        int i = 0;
        for (; m != n; ++i) {
            m >>= 1;
            n >>= 1;
        }
        return n << i;
    }


    class Solution_overTime {
        public int rangeBitwiseAnd(int m, int n) {

            int result = m;

            for (int i = m + 1; i <= n; i++) {
                result &= i;
            }

            return result;
        }
    }
}

All Problems

All Solutions