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
Solution: Bit operation
Bitwise AND all the numbers between left and right will clear out all the low bits. Basically this question is asking to find the common prefix of left and right in the binary format.
5 = 0b0101
7 = 0b0111
the common prefix is 0b0100 which is 4.
Time complexity: O(logn)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 |
// Author: Huahua class Solution { public: int rangeBitwiseAnd(int left, int right) { while (right > left) right &= (right - 1); // clears the lowest set bit. return right; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment