LeetCode //C - 201. Bitwise AND of Numbers Range

201. Bitwise AND of Numbers Range

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:

Example 2:

Example 3:

Constraints:

• 0 < = l e f t < = r i g h t < = 2 31 − 1 0 <= left <= right <= 2^{31} - 1 0<=left<=right<=231−1

From: LeetCode
Link: 201. Bitwise AND of Numbers Range

---

Solution:

Ideas：

• shifts is used to count how many times the numbers are shifted.
• The while loop continues to right shift both left and right until they are equal.
• Each shift represents a bit position where the numbers in the range will have differing values, and therefore, the AND result for that bit will be 0.
• After finding the common prefix (when left equals right), we left shift left by shifts times to get the final result. This is the bitwise AND of all numbers in the range [left, right].

Code:

int rangeBitwiseAnd(int left, int right) {
    int shifts = 0;
    while (left != right) {
        left >>= 1;
        right >>= 1;
        shifts++;
    }
    return left << shifts;
}