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

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

 

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

풀이

 

 

 

	const solution = (n) => {
	const rightOne = n & -n;
	const nextHigherOneBit = n + rightOne;
	const rightOnesPattern = (n ^ nextHigherOneBit) / rightOne >> 2;
	return nextHigherOneBit | rightOnesPattern;
	};

view raw 다음 큰 숫자.js hosted with ❤ by GitHub

 

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 연산을 사용하여 패턴을 합쳐준다.

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

 

 

주석 설명 풀이

	const solution = (n) => {
	// input n = 0000 1111 0000(2) 인 경우
	// expected output = 0001 0000 0111(2)
	// 헷갈려서 적음: 왼쪽(= left = 큰 자리수) <-> 오른쪽 (= right = 작은 자리수)
	/*
	* [1 bit 뭉치 중 가장 오른쪽 비트의 값 구하기]
	* -n 구하는 법) 1111 0000 1111(2) 보수 취함 -> 1 더함: 따라서 1111 0001 0000(2)
	* 따라서 0000 1111 0000(2) & 1111 0001 0000(2)
	*/
	const rightOne = n & -n; // 결과: 0000 0001 0000
	/*
	* [왼쪽 비트 패턴 구하기]
	* rightOne 과 n을 더하여 n의 오른쪽 1 뭉치들을 조작하는 과정
	* 왼쪽 비트 값이 여기서 설정됨 (1 뭉치 기준 왼쪽 1들과 1 뭉치 내 자리수 올라가는 고립된 1 숫자끼리 합쳐줌)
	* 0000 1111 0000 + 000 0001 0000 (10진법 덧셈 원리 생각하면 이해 쉬움)
	*/
	const nextHigherOneBit = n + rightOne; // 결과: 0001 0000 0000
	/*
	* [오른쪽 비트 패턴 구하기]
	* 오른쪽 1 bit 뭉치 분리
	* XOR 연산: 비트가 서로 다르면 1, 같으면 0
	* 0000 1111 0000 (XOR) 0001 0000 0000
	*/
	let rightOnesPattern = n ^ nextHigherOneBit; // 결과: 0001 1111 0000
	/*
	* 나머지 1 bit 뭉치들 왼쪽으로 옮기기 (bit shift 계산 순서 상관 없음)
	* [1] 1 bit 뭉치 바로 앞까지 있는 0 싹 다 날려줌
	* 0001 1111 0000 / 0000 0001 0000 ( 나누기 2^4 는 << 4 와 동일함)
	*/
	rightOnesPattern = rightOnesPattern / rightOne; // 결과: 0000 0001 1111
	/*
	* [2] 1 개수 총합이 같아야 하므로 2만큼 shift 해줌
	* 기존 1비트 뭉치(4개)에 자리 올림한 1비트까지 추가된 상태 (XOR 연산) 총 1 개수 5개
	* 1 개수 유지해야하므로 1 (자리 올림된 1 개수) + x (오른쪽 패턴 1 개수) = 4
	* 따라서 오른쪽 패턴 1 개수 = 3
	* 5 - 3 = 2개만큼 shift 해줘야함
	* 즉, 올림에 사용된 1이 중복으로 2개 들어가있음!!! 그래서 2개만큼 빼줌
	* 0000 0001 1111 >> 2
	*/
	rightOnesPattern = rightOnesPattern >> 2 // 결과: 0000 0000 0111
	// 0001 0000 0000 (OR) 0000 0000 0111 (왼쪽 비트 패턴과 오른쪽 비트 패턴끼리 엮어줌)
	const next = nextHigherOneBit | rightOnesPattern; // 0001 0000 0111
	return next;
	};

view raw 다음 큰 숫자 설명 주석.js hosted with ❤ by GitHub

 

여기서 가장 핵심은 가장 오른쪽에 있는 (가장 작은 자리 수)에 있는 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)