LeetCode - 201. Bitwise AND of Numbers Range

코드

/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var rangeBitwiseAnd = function(left, right) {

    let four = left
    if(parseInt(Math.log2(left)) === parseInt(Math.log2(right))) {
        for(let i=left+1;i<=right;i++)
        {
            four = four & i
        }
        return four
    } else return 0
}

풀이 및 소감

접근 방법 1.(X)
left부터 right까지 돌면서 AND 연산을 하면 시간 초과가 날 거 같았는데 혹시 몰라 테스트 하니 역시 시간초과가 났다. 최대 값이 2^31 - 1인 2147483647

접근 방법 2.(통과는 했지만 틀린 풀이 같다.)
먼저 숫자들을 2진수로 변경 시켜 보았다.

1 -> 0001
2 -> 0010
3 -> 0011
4 -> 0100
5 -> 0101
6 -> 0110
7 -> 0111
8 -> 1000

혹시 공통점이 보일지 모르겠다. 바로 2^n 꼴일 때마다 맨 앞의 1이 생기며 나머지가 0으로 되므로 AND 연산을 수행하면 0이 나오는게 자명하다. ex) 7,8을 보면 알 수 있다.
그래서 log2를 취해서 2^n ~ 2^(n+1)-1인 경우만 AND 연산을 해줘서 통과했다. 근데 다시 생각해보니 최대 범위인 2^30 ~ 2^31-1 이면 1073741824 ~ 2147483647 이어서 약 10억 이상의 연산을 진행해야 한다.

통과하고 다른 사람들은 어떻게 풀었다 보다가 위 오류를 찾아서 여기부터는 다른 사람들의 풀이법이다.

접근 방법 3.
One line C++ solution

// c++
int rangeBitwiseAnd(int m, int n) {
    return (n > m) ? (rangeBitwiseAnd(m/2, n/2) << 1) : m;
}

처음에 보고 이게 머지 싶었다.. 한줄로 작성한 코드인데 댓글들을 참고했다. 먼저 두 값이 다르면 무조건 맨 마지막 bit(1의 자리 bit)는 다를 수 밖에 없다. 그래서 /2 연산을 통해 마지막 자리를 지워주다가 두 값이 같아지면 그때의 값을 return해주고 << 1을 통해 왼쪽에 0을 붙여줌으로 써 해결한 것이다.
예시를 통해 좀 더 살펴보자면
n = 11111011000와 m = 11111000011이 있다고 하자.
이 사이의 수들은 무조건 111110xxxxx이라는 것을 알 수 있다. 왜냐하면 n은 최대값, m은 최소값이기 때문이다.

1. n > m 보다 크므로 /2를 해주고 재귀 함수를 작동한다.
2. 그러면 1111101100, 1111100001로 변할 것이다.(2진법을 잘 생각해보자)
3. 위의 과정을 반복하다가 111110로 같아지는 순간 m(기저 값)을 return 해준다.
4. return 된 111110를 << 1를 사용해 1111100처럼 0을 붙여준다.
   이 과정을 하면은 결국 공통된 부분을 찾을 수 있는 것이다.

접근 방법 4.
Simple 3 line Java solution faster than 100%

먼저 접근 방법의 핵심은 두 숫자를 Bitwise-AND 했을 때 무조건 더 작은 숫자보다 작거나 같은 숫자를 생성한다는 것이다.

 while(n>m)
           n = n & n-1;
 return n;

따라서 하나 작은 숫자와 & 연산을 해주면 공통된 부분을 가지고 있고 처음에 주어진 m(작은 값)보다 작아지면 그 전에 계산된 공통된 부분을 리턴해주면 된다.
위 링크의 예제를 참고해도 좋은 방법일 것이다.

추가로 Brian Kernighan algorithm이란 게 있어서 5번에 작성하려고 했는데 댓글에 위의 방법이라는 얘기가 있어서 정리해보려고 한다.

Brian Kernighan algorithm은 원래 set bit의 수를 세는 알고리즘이다. set bit이란 1인 bit를 의미한다.

1. 가장 쉬운 방법은 Brute-Force Solution이다.

n이 주어졌을 때 2진수로 바꾸고 1의 개수를 세리면 된다.

while (n)
    {
        count += (n & 1);    // check last bit
        n >>= 1;
    }

결론적으로 O(logn)이 걸리는 방법이다.

2. Brian Kernighan algorithm

while (n > 0)
    {
        n &= (n - 1);
        count++;
    }

위에서 본 코드랑 같다. 이 방법은 맨 오른쪽 bit를 제거하는 방식이다.
예를 들어 1110100110이라는 수가 있다고 하자. 여기서 1을 빼면 앞부분은 다 똑같고 1110100101이 될 것이다. 그러면 이 두개를 & 연산했을 때 알 수 있는 것은 11101001x0의 x부분이 사라진다는 것이다. 이렇게 n이 0보다 클때까지만 반복하면 1의 개수를 파악할 수 있는 것이다.

접근 방법 5.
과 선배가 푼 방법이다.

from math import log2, ceil
class Solution:
	def rangeBitwiseAnd(self, m: int, n: int) -> int:
    	if n - m == 0: return n
        if n - m == 1: return (n & m) >> 1 << 1
        a = ceil(log2(n - m))
        return (n & m) >> a << a

a를 구하는 부분 빼고는 쉽게 이해가 될 것이다. ceil(log2(n-m))에서 나도 이해하기 어려웠는데 접근 방법 3번에서 봤던 return (n > m) ? (rangeBitwiseAnd(m/2, n/2) << 1) : m; 이걸 수학적으로 푼 것이었다. 저 재귀가 돌려면 n이 m보다 클 때 인데 두 값의 차이는 /2를 해줌으로써 줄어들고 있다. 예를 들어 24와 18이면 차이가 6이난다. 그 다음은 12와 9가 되고 차이는 3이 된다. 이런식으로 결국 처음 차이에서 2로 나눠야하는 횟수만큼 재귀가 도는데 이를 수식으로 표현하면 ceil(log2(n-m))인 것 이다.

---

한 문제를 가지고 다양한 방법으로 정리를 해보았다. 생각보다 시간이 오래걸렸다 ㅠㅠ 그래도 여러 접근 방법을 배우게 된 좋은 기회였다. 다음에는 더 빨리 이해하도록 노력해봐야겠다...