Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
Example 1:
Example 2:
Solution
Bitwise-AND of any two numbers will always produce a number less than or equal to the smaller number.
Consider the following example:
Desired Range: [5,12]
Starting from 12, the loop will first do
12 & 11 = 8
Next iteration, the loop will do
8 & 7 = 0
why did we skip anding of 10,9? Because even if we did so, the result would eventually be anded with 8 whose value would be lesser than equal to 8.
Hence, you start from the range end and keep working your way down the range till you reach the start.
Code
0 1 2 3 4 5 6 7 8 9 |
class Solution { public int rangeBitwiseAnd(int m, int n) { while (n > m) { n = n & n - 1; } return m & n; } } |
We encourage you to write a comment if you have a better solution or having any doubt on the above topic.