Welcome to Subscribe On Youtube

Question

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

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

 

Example 1:

Input: left = 5, right = 7
Output: 4

Example 2:

Input: left = 0, right = 0
Output: 0

Example 3:

Input: left = 1, right = 2147483647
Output: 0

 

Constraints:

  • 0 <= left <= right <= 231 - 1

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

  • 
    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;
            }
        }
    }
    
    ############
    
    class Solution {
        public int rangeBitwiseAnd(int left, int right) {
            while (left < right) {
                right &= (right - 1);
            }
            return right;
        }
    }
    
  • class Solution:
        def rangeBitwiseAnd(self, left: int, right: int) -> int:
            while left < right:
                right &= right - 1
            return right
    
    ############
    
    class Solution(object):
      def rangeBitwiseAnd(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        while m < n:
          n = n & n - 1
        return n
    
    
  • class Solution {
    public:
        int rangeBitwiseAnd(int left, int right) {
            while (left < right) {
                right &= (right - 1);
            }
            return right;
        }
    };
    
  • func rangeBitwiseAnd(left int, right int) int {
    	for left < right {
    		right &= (right - 1)
    	}
    	return right
    }
    
  • /**
     * @param {number} left
     * @param {number} right
     * @return {number}
     */
    var rangeBitwiseAnd = function (left, right) {
        while (left < right) {
            right &= right - 1;
        }
        return right;
    };
    
    
  • public class Solution {
        public int RangeBitwiseAnd(int left, int right) {
            while (left < right) {
                right &= (right - 1);
            }
            return right;
        }
    }
    

All Problems

All Solutions