이 글은 게일 라크만 맥도웰 저자의 ‘코딩인터뷰 완전분석’을 읽으며, 깨달은 사실과 내용을 정리하는 글입니다.
자세한 내용이 궁금하다면 http://www.yes24.com/Product/Goods/44305533 에서 책을 구매하시면 좋겠습니다.

이번 포스팅에서는 면접을 대비해서 비트 조작에 대해 정리해보겠습니다.

책에서는 비트 조작 같은 CS 개념과 기타 알고리즘, 수학·논리 퀴즈 관련 내용이 한 챕터에 들어있습니다만, 분량 관계로 여러 소주제로 나눠 포스팅하겠습니다.

비트 조작 기법은 다양한 문제에서 활용된다고 저자가 설명합니다.
비트 조작을 명시적으로 요구하는 문제가 존재하고, 코드를 최적화할 때 유용하게 사용되기도 합니다.

본격적으로 비트 조작 개념과 여러 트릭에 대해 알아보겠습니다.

직접 비트 조작해보기

먼저 비트 조작에 익숙해지기 위해, 직접 손으로 비트를 조작해보는 연습을 해봅시다.

문제를 단순화하기 위해, 모든 숫자는 4비트 숫자라고 가정하겠습니다.

기본적인 연산 기호의 의미는 아래와 같으므로, 참고하시기 바랍니다.

• & : AND
• | : OR
• ^ : XOR
• ~ : NOT
• << : (산술) 좌측 시프트
• >> : (산술) 우측 시프트

기본 예제 문제

문제	정답
0110 + 0010	1000
0011 + 0010	0101
0110 - 0011	0011
1000 - 0110	0010
0011 * 0101	1111
0011 * 0011	0101
1101 » 2	0011
1101 ^ 0101	1000

트릭을 사용할 수 있는 문제

문제	정답	트릭
0110 + 0110	1100	0110에 2를 곱한 것과 동일하므로, 좌측 시프트를 1번 수행하면 된다.
0100 * 0011	1100	0100은 4이므로, 0011에 좌측 시프트를 2번 수행한 것과 같다.
1101 ^ (~1101)	1111	자기자신을 부정한 값과 XOR 연산을 수행하면 모든 비트가 1로 채워진다. (대응되는 비트가 무조건 서로 다르기 때문에)
1011 & (~0 « 2)	1000	~0은 모든 비트가 1로 구성된다. 2번 좌측 시프트를 수행하면 마지막 2개 비트가 0으로 구성된다. 이것과 AND 연산을 수행한다는 것은 곧, 마지막 2개 비트를 삭제하겠다는 것과 동일하다.

비트 조작시, 알아야 할 사실과 트릭

비트 조작 문제를 풀 때, 아래 표현식을 알아두면 좋다고 합니다.

하지만 외우려고 하지는 말고, 어떻게 도출된 결과인지 이해하는 것이 중요합니다.

참고로 0s 는 모든 비트가 0으로 이루어진 것을 의미하고, 1s 는 모든 비트가 1로 이루어진 것을 의미합니다.

x ^ 0s = x	x & 0s = 0s	x | 0s = x
x ^ 1s = ~x	x & 1s = x	x | 1s = 1s
x ^ x = 0s	x & x = x	x | x = x

2의 보수와 음수

컴퓨터는 일반적으로 음수의 정수를 저장할 때 2의 보수를 활용합니다.

보수가 뭔가요?

보수는 ‘보충해주는 수’를 의미합니다.

다시말해, ‘다음 자릿수로 넘어가기 위해 필요한 수’ 입니다.

예를 들어, 3의 8에 대한 보수는 5가 되고, 7에 대한 13의 보수는 6이 됩니다.

그렇다면 컴퓨터는 왜 2의 보수를 사용하는 것일까요?

부호비트만을 사용해서 양수·음수를 표현한다면

부호비트가 0이라면 양수, 1이라면 음수로 취급한다면 계산 결과가 정확하지 않다는 문제가 발생합니다.

예를 들어, 10진수 1과 10진수 -1을 서로 더하는 경우를 생각해볼까요?

1. (10진수 1 = 0001) , (10진수 -1 = 1001)
2. 0001 + 1001 = 1010 = 10진수 -2

어떤가요? 우리는 10진수 0을 기대했지만, 결과가 전혀 다릅니다.

이 문제를 해결하기 위해, 1의 보수를 사용할 수 있습니다.

1의 보수를 사용해서 양수·음수를 표현한다면

1의 보수를 사용하면 산술 결과를 정확하게 얻을 수 있지만, 0을 표현하는 이진수가 두 종류가 됩니다.

다시 아까 살펴본 예제를 가져와볼까요?

1. (10진수 1 = 0001) , (10진수 -1 = 1001 → 1의 보수화 → 1110)
   • 참고로 보수를 취할 때는 부호비트는 제외합니다.
2. 0001 + 1110 = 1111

결과로 1111 이 도출됩니다. 이 말은 즉, 0을 표현하는 이진수로 0000 뿐만 아니라, 1111 도 포함해야 한다는 것을 의미합니다.

이것은 컴퓨터에 오류를 초래할 수 있는 문제입니다.

이 문제를 해결하기 위해서, 2의 보수가 도입됐습니다.

2의 보수를 사용해서 양수·음수를 표현한다면

2의 보수를 사용하면 완벽하게 계산할 수 있습니다.

1. (10진수 1 = 0001) , (10진수 -1 = 1001 → 2의 보수화 → 1111)
2. 0001 + 1111 = 10000 → 초과하는 좌측 비트는 버린다 → 0000

2의 보수를 취한 값으로 연산을 수행하고, 초과하는 비트는 버린다면 우리가 원하는 0000 을 도출할 수 있습니다.

산술 시프트 vs 논리 시프트

시프트에도 ‘산술 시프트’와 ‘논리 시프트’ 2가지 종류가 존재합니다.

• 우측 산술 시프트
  • 모든 비트를 (부호비트 포함) 우측으로 시프트한다.
  • 그 후, 부호 비트는 기존의 값으로 채운다.
  • 1011 → 1101
• 우측 논리 시프트
  • 모든 비트를 (부호비트 포함) 우측으로 시프트한다.
  • 1011 → 0101

기본적인 비트 조작

이제부터 설명할 연산들은 굉장히 중요하므로, 반드시 알고 있어야 한다고 저자가 이야기합니다.

단순히 암기하는 것이 아니라, 그 원리까지 이해하고 있는 것이 중요합니다.

비트값 확인 연산 : i번째 비트값 확인

// i : 확인할 비트 자리 (가장 우측 = 0)
boolean getBit(int num, int i) {
	return ((num & (1 << i)) != 0);
}

1. 1을 i만큼 좌측 시프트합니다.
   • Ex. i = 4 라면, 10000
2. 기존 수와 AND 연산을 합니다.
3. 그 결과가 0이라면, i번째 비트가 0이라는 것을 의미합니다.
   1이라면, i번째 비트는 1입니다.

비트값 채워넣기 : i번째 비트를 1로 만들기

int setBit(int num, int i) {
	return num | (1 << i);
}

1. 1을 i만큼 좌측 시프트합니다.
2. 기존 수와 OR 연산을 합니다.

비트값 삭제하기 : i번째 비트를 0으로 만들기

int clearBit(int num, int i) {
	return num & ~(1 << i);
}

1. 1을 i만큼 좌측 시프트합니다.
2. 그 결과에 NOT 연산을 합니다.
3. 기존 수와 AND 연산을 합니다.

비트값 삭제하기 : 최상위 비트 ~ i번째 비트를 모두 0으로 만들기

int clearBitsMSBToI(int num, int i) {
	return num & ((1 << i) - 1)
}

1. 1을 i만큼 좌측 시프트하고, 1을 뺍니다.
   • 이 연산을 통해, 0 ~ i-1 까지의 비트를 1로 설정할 수 있습니다.
   • Ex. i = 2인 경우, 0100 → 1 빼기 → 0011
2. 기존 수와 AND 연산을 합니다.

비트값 삭제하기 : i ~ 0번째 비트를 모두 0으로 만들기

int clearBitsITo0(int num, int i) {
	return num & (-1 << (i+1));
}

1. -1을 i+1만큼 좌측 시프트합니다.
   • -1은 모든 비트가 1로 구성됩니다. (2의 보수를 취하기 때문에)
   • 따라서 -1을 i+1만큼 좌측으로 시프트하면, ‘최상단 비트 ~ i+1’ 비트가 모두 1로 구성됩니다.
   • Ex. i = 2인 경우, -1 → 2의 보수 → 1111 → i+1 좌측 시프트 → 1000
2. 기존 수와 AND 연산을 합니다.

비트값 바꾸기 : i번째 비트를 원하는 값으로 변경하기

//newValueIs1 = true: 1로 변경 , false: 0으로 변경
int updateBit(int num, int i, boolean newValueIs1) {
	int newValue = (newValueIs1) ? 1 : 0;
	num = num & ~(1 << i); //i번째 비트를 0으로 만들기
	return num | (newValue << i);
}

1. 1을 i만큼 좌측 시프트하고 NOT 연산을 적용합니다.
2. ‘1번 결과값’과 num을 AND 연산합니다.
   • 이 작업을 통해, 변경할 비트의 값을 0으로 수정합니다. (비트 삭제)
3. ‘2번 결과값’과 ‘원하는 값을 i만큼 좌측 시프트한 결과값’을 OR 연산합니다.

마무리하며

비트 조작은 그 개념을 확실히 잡아두고, 추가적으로 필요한 부분을 조금씩 암기해두는 것이 면접에서 유리하게 작용할 것 같습니다.

개인적으로 가장 약한 부분이 비트 조작인데, 이번 기회에 관련 개념을 확실히 잡아둘 수 있어서 좋았습니다.

이 포스팅을 통해 개념을 잡고, 많은 문제를 접하면서 비트 연산에 익숙해지도록 연습하면, 좋은 결과가 있을 것이라고 생각합니다.