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 <= 2³¹ - 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;
    }
}

201 - Bitwise AND of Numbers Range

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions