[leetcode #201] Bitwise AND of Numbers Range

Problem

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

Idea

코드는 짧지만 답을 얻기가 까다로운 문제다. 한참을 생각하다 결국 다른 사람의 풀이를 볼 수 밖에 없었다 🥲

left와 right가 주어지고 left와 right를 포함한 범위 전체의 수를 AND 연산했을 때 나오는 값이 무엇인지 구하면 된다. 범위 내의 수는 고려하지 않고 양끝값만 가지고 답을 구할 수 있는 것이 핵심이다.

left와 right를 right shift시키면서 몇 번 shift했는지 센다. Right shift시키면서 left와 right가 똑같아졌다면 shift를 멈추고 같아진 수를 left shift시켜 값을 구한다.

위와 같은 방법이 가능한 이유는 right shift시키면서 두 수가 같아지는 bit를 범위 내의 모든 수가 포함하고 있기 때문이다. 나머지 bit는 범위 내의 수 중 0을 포함하고 있는 수가 있기 때문에 0이 될 수밖에 없다. 따라서 right shift시키다가 두 수가 같아질 때 shift시킨 만큼 left shift시켜 리턴하기만 하면 된다.

Solution

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while(left != right){
            left = left >> 1;
            right = right >> 1;
            shift++;
        }

        return right << shift;
    }
}

Reference

https://leetcode.com/problems/bitwise-and-of-numbers-range/