[LeetCode] 201. Bitwise AND of Numbers Range

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

LeetCode - The World's Leading Online Programming Learning Platform

Leetcode - Bitwise AND of Numbers Range

문제 유형 : 비트마스킹

문제 난이도 : Medium

 

문제

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

정수 left, right가 주어진다. left부터 right까지의 모든 수를 AND연산을 한 값을 구하시오.

 

풀이

5 = 0b101

7 = 0b111

공통 = 0b100

앞쪽 자릿수의 비트들은 중간에서 상쇄된다.

그래서 높은 자릿수쪽에서 공통 비트를 찾으면 되는데, 

쉬프트 연산을 통해서 낮은 자릿수들을 자르면서 확인하는 것이다.

낮은 자리의 비트들을 자르면서 left와 right이 같아질 때 까지 반복하고, 자릿수 체크를 위한 카운트도 누적한다.

left에서 다시 카운트만큼 왼쪽 쉬프트연산을 하면서 자릿수를 복구시킨다.

그 수가 정답이 된다.

 

코드

C++

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

 

Go

func rangeBitwiseAnd(left int, right int) int {
    cnt := 0;
    for left != right {
        left >>= 1
        right >>= 1
        cnt++
    }

    return left << cnt
}