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; } }