[LeetCode] 201. Bitwise AND of Numbers Range

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

Bitwise AND of Numbers Range - LeetCode

Bitwise AND of Numbers Range

 

 

int 자료형이며 0 이상인 left와 right가 주어진다.

이때 left이상 right이하인 수들의 모든 & 비트연산 값을 구해주면 된다.

 

& 연산의 경우 하나하나 해주면 되겠지만

최악의 경우는 0~2147483647(int 최대범위) 까지 계산할경우

32비트끼리의 연산을 2^31 번 해야하므로

약 2^36＞10^9 (10억) 번의 연산을 해야하므로 당연히 터지게 된다.

어떻게 하면 좋을까 고민을 하며 일단 5비트까지의 수를 쭉 봤다.

 

00001
00010
00011
00100
00101
00110
00111
01000
01001
01010
01011
01100
01101
01110
01111
10000
10001
10010
10011
10100
10101
10110
10111
11000
11001
11010
11011
11100
11101
11110
11111

 

모든 & 연산의 장점 중 하나는 하나라도 0이 껴있으면 모두 0이 되는 점이고,

위 숫자들을 보면 각 자리별 1과 0이 연속으로 나오는 것을 알 수 있다.

예를 들어, 2^4 자리수를 보면 0~15까지 16개는 0, 16~31까지 16개는 1이다. => (0,1)

2^3 자리수는 0~7까지 8개는 0, 8~15까지 8개는 1, 16~23 8개는 0, 24~31 8개는 1이다. => (0,1,0,1)

...

2^0 자리수 => (0,1,0,1,...,0,1)

 

보면 각 자리수별로 0과 1이 나타나는 규칙이 홀수번엔 0, 짝수번엔 1이 되고,

각각의 개수는 각 자리수가 나타내는 값이다.

즉, 해당 수를 각 자리수로 나누었을때 몫이 홀수일 경우 0, 짝수일 경우 1이 된다.

 

이럴 경우 우리는 right와 left만 보고 문제를 풀 수 있다.

먼저 결과값 ret을 0으로 놓고, right와 left의 차 sub를 구하자.

i를 0부터 31까지 훑으며 sub가 2^i  이상인 경우에는 무조건 0과 1이 공존하므로 결과값의 해당 자리수는 0 이 된다. (ret += 0, 예: 2^4 자리 비교에서 0과 16=> 0, 1)

sub가 2^i 보다 작을 경우에는 left를 2^i로 나눈 몫과 right를 2^i로 나눈 몫이 각각 홀수인지 짝수인지 비교하자.

둘다 같다면 해당 자리수 변화가 없는 것이고, 다르다면 해당 자리수 변화가 있는 것이다.

다만 이때 홀수라면 해당 자리수가 0이고, 짝수라면 1이 되므로 짝수일 경우에만 생각하면 된다.

즉, 0 <= i <= 31에서 sub<2^i 일때,

ret에 ((left >> i (left는 2^i로 나눈 몫) )& 1 (1로 나눴을때 나머지. 홀,짝)) & ((right >> i) & 1) * 2^i를 더해주면 된다.

(위 식이 어려울 경우 비트연산 몫/나머지를 구하는 방법을 검색해보자)

 

전체 코드는 아래와 같다.

요새 숏코딩을 조금씩(아주 조금만) 해보고 있어 코드가 난해할 수 있다.

 

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        long pow[32];
        pow[0] = 1;
        for (int i=1; i<=31; i++) pow[i] = 2*pow[i-1];
        int sub = right - left;
        int ret = 0;
        for (int i=0; i<=31 && right>=pow[i]; i++) if (sub<pow[i]) ret += pow[i] * (((left>>i)&1) & ((right>>i)&1));
        return ret;
    }
};