[프로그래머스 Lv. 2] 다음 큰 숫자 - 비트연산자 사용한 시간 복잡도 O(1) JavaScript 풀이

코딩테스트 연습 - 다음 큰 숫자 | 프로그래머스 스쿨 (programmers.co.kr)

 

• n은 1,000,000 이하의 자연수

풀이

 

 

 

 

Time Complexity: O(1)
Auxiliary Space: O(1)

 

아이디어:

오른쪽 대부분의 비트(LSB, Least Significant Bit)는 왼쪽 대부분의 비트보다 빠르게 변화함
이 아이디어는 x에서 1의 가장 오른쪽 문자열을 찾고 패턴의 가장 왼쪽 비트를 제외한 오른쪽 극단으로 패턴을 이동함.
패턴에서 가장 왼쪽에 있는 비트(누락된 비트)를 x의 왼쪽 부분으로 한 위치씩 이동함

상세 설명

해당 추가 테스트 케이스들을 보자.

더 힌트를 얻어보자면..

여기서 규칙을 발견할 수 있다.

가장 오른쪽에 있는 1 뭉치들에 대해서 일정한 패턴이 보인다.

혹은 논리적으로 생각해도 된다.

저 패턴 원리를 논리적으로 쉽게 이해하려면, 비트 연산을 도미노인 것 처럼 생각하면 도움이 된다.
(개인적으로 2진법 연산 할 때 자리수 변화를 도미노처럼 연상하니까 이해하는 것에 도움이 되었다.)

예를 들어 0110 1110 인 경우
주어진 숫자의 가장 최하단 1 비트 값(0010)만큼 더하면
1 비트 3개가 도미노처럼 쭈루룩 올라가서
0111 0000 이 된다. 그러고 나머지 1 비트 2개는 가장 작은 값, 즉 가장 오른쪽으로 밀어주면 된다.

따라서 당연히 같은 비트 수를 가진 수 중에서 바로 다음 큰 값을 갖게 될 것이다.

 

xxxx0 1111 0000 을 예시로 흐름을 정리해보자.

1. [1 bit 뭉치 중 가장 오른쪽 비트의 값 구하기]

rightOne 기준점 찾기: 오른쪽부터 가장 첫번째 1을 찾는다  | xxx0 1111 0000

→ n & -n (2의 보수이므로) 비트 연산을 취해준다.

→   xxx0 0001 0000

 

2. [왼쪽 비트 패턴 구하기]

1 뭉치 기준 왼쪽 1들과 1 뭉치 내 자리수 올라가는 고립된 1 숫자끼리 합쳐줌

nextHigherOneBit (왼쪽 1 패턴): 주어진 숫자 + rightOne

4. [오른쪽 비트 패턴 구하기]

 XOR 연산을 사용하여 오른쪽 1 bit 뭉치를 분리하고, 올림에 사용된 중복된 1 2개를 제거하고 1번에서 구한 righOne 자리수만큼 bit shift 해줌

 

5. [패턴 합쳐주기]

OR 연산을 사용하여 패턴을 합쳐준다.

더 자세히는 해당 코드에 주석으로 같이 정리해두었다.

 

 

주석 설명 풀이

 

여기서 가장 핵심은 가장 오른쪽에 있는 (가장 작은 자리 수)에 있는 1 뭉치 묶음과, 그 1뭉치에서 가장 오른쪽에 있는 1이다. (rightOne)

 

rightOnesPattern 설명
1. 1 뭉치에 1을 더한 값 (이때 올림이 발생한다: 1111(2) + 1(2) → 1 0000(2) ⇢ 10진수 덧셈의 자리변화를 생각하면 된다.)
2. XOR 연산으로 right 패턴만 분리 (기존에 1뭉치 이후로 존재하는 1은 이때 지워진다)

 

예: 1111(2) XOR 연산 이후 rightOnesPattern

→ 1 1111(2)
→ 이때 올림된 1이 2개만큼 중복되어 들어가있음 (올림된 비트, 올라간 비트)
→ 따라서 2개 비트만큼 빼줘야함

→ 그리고 rightOne 기준으로 비트 이동해준다.
→ 결과 0 0111(2)

 

---

 

음수 계산법

* 출처: 4번 문서[0]
2의 보수 계산: 비트를 반전시킨 뒤 1을 더하면 됨 (자리수 바뀌는건 10진수 비교해서 생각하면 됨)

예를 들면
6 (0000 0110) ↔ -6 (1111 1010)
비트 반전: 1111 1001
1 더함: 1111 1010

비트 곱셈, 나눗셈

* 출처: 5번 문서[1]
※ 곱셈의 경우

5 * 4 는 5 * 2^2 (^는 제곱의 표현으로 사용함) 로 해석이 가능하고,
5 << 2 로 변환하여 사용이 가능합니다.
또한,
5 * 5 는 5 * ( 4 + 1 ) 의 형태입니다. 따라서, 5 * ( 2^2 + 2^0 ) 이므로,
(5 << 2) + (5 << 1) 의 형태로 변환하여 사용이 가능합니다.


※ 나눗셈의 경우

5 / 4 는 5 / (2 ^ 2) 로 해석이 가능하고
5 >> 2 로 변환하여 사용이 가능합니다.
결과는 2진수 형태는 0 0 0 0 0 0 0 1 이 되고, 10진수 값으로는 1입니다.
이 때, 정수연산의 나눗셈이므로 나머지는 신경쓰지 않습니다.

---

 

참고 문서

1. 비트 연산자 JavaScript Bitwise (w3schools.com)
2. 로직 설명 Next higher number with same number of set bits - GeeksforGeeks, Next higher number with same number of binary bits set (slideshare.net)
3. 컴퓨터의 음수 표현
2진수의 수와 음수 표현법 [1의 보수와 2의 보수] (tistory.com)
번외. 컴퓨터에서 음수를 표현하는 방법 (hexabrain.net)
4. 비트 나눗셈 Binary Division (이진 나눗셈) (tistory.com) , bit shift(비트 쉬프트)를 이용한 곱셈, 나눗셈 연산 (tistory.com)