[leetcode][201] Bitwise AND of Numbers Range

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

---

0 이상 2147483647 이하인 수 m, n(m <n) 이 주어질 때, m ~ n까지 수를 AND 연산한 결과를 반환하라.

---

범위가 2147483647. 21억이다. O(N)으로는 풀 수 없기 때문에 O(logN) 방법을 생각해야한다.

1~7까지의 비트를 적어보자.

 

1 =    1

2 =   10

3 =   11

4 =  100

5 =  101

6 =  110

7 =  111

8 = 1000

 

먼저 볼 것은 4, 8. 앞에 자릿수가 추가되는 경우 이전까지의 비트들은 0이된다. 

=> 앞에서부터 자릿수를 비교해봤을 때, 다른 비트가 나오는 경우는 이후의 비트들도 AND연산을 하면 결국 0이된다고 추측할 수 있다. (prefix를 구해야한다.)

 

m=101011(43), n=101111(47)을 예로 들어보자. 두 수의 prefix는 101000(40)이다. (prefix는 101 이지만 실제로 알고싶은건 101000 이기 때문에 편의상 이렇게 표현)

101011에서 101111이 되기 위해서는 4번째 자리의 0이 1이 되기 위한 과정이 필요하다.

이 때 4번째 자리 이후의 비트들은 모두 0이 될것이다. 즉, 다른 비트가 나오는 4번째 비트 뿐만 아니라 4번째 이후의 비트들의 AND 연산도 0이 될 것이다. 

101011 ~ 101111 값들은 4번째 이후의 비트들만 다른 수들일 것이다. = 101xxx은 항상 공통적으로 나온다.

따라서 101000(40)이 정답이 된다.

 

prefix를 구할 때는 m, n이 같아질때까지 오른쪽으로 한 비트씩 옮겼다가(0보다 작은 비트는 값이 사라진다.), 같아진 순간 오른쪽으로 옮겼던 비트 수만큼 다시 왼쪽으로 옮겨줬다.

 

시간복잡도는 O(logN). N = m이다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/201.%20Bitwise%20AND%20of%20Numbers%20Range.cpp