5. 비트 조작

손으로 비트 조작 해보기

비트 조작에 익숙하지 않기 때문에 연습 문제를 풀어보면서 이해해보도록 하자

1. 0110 + 0110
2. 0100 * 0011
3. 1101 ^ (~1101)
4. 1101 & (~0 << 2)

다음은 해당 문제에 대한 풀이법이다. 물론 정석적으로 푸는 방법도 있지만, 해당 문제에 대해 쉽게 접근해보는 방법을 제시한다.

1번, 0110 + 011+은 0110 * 2와 같은 의미이므로 0110을 왼쪽으로 한 번 시프트한 1100이다.
2번, 0110은 4와 같고, 4를 곱하는 것은 왼쪽으로 두 번 시프트하는 것과 같으므로, 0011을 왼쪽으로 두 번 시프트하면 1100이 된다.
3번, 어떤 비트와 그 비트를 부정한 값을 XOR하면 항상 1이 된다. 그러므로, a^(~a)는 모든 비트가 1이 되므로 1111이 된다.
4번, ~0을 하면 모든 비트가 1이 되며, 따라서 ~0 << 2는 마지막 비트 두 개만 0인 비트가 된다. 이 값과 다른 값을 AND 연산하면 마지막 두 비트의 값을 삭제한 값을 얻는다. 즉 1000이 된다.

비트 조작을 할 때 알아야 할 사실들과 트릭들

비트 조작 문제를 풀 때 다음의 표현식들을 알아 두면 좋다. 각 표현식들이 왜 참이 되는지 확인해보고, 생각해보는 것을 적극 추천한다. '0s'는 모든 비트가 0인 값이며, '1s'는 모든 비트가 1인 값을 나타낸다.

x ^ 0s = x
x ^ 1s = ~x
x ^ x = 0

x & 0s = 0
x & 1s = x
x & x = x

x | 0s = x
x | 1s = 1s
x | x = x

한 비트에서 일어나는 일은 다른 비트에 어떤 영향도 미치지 않는 다는 점을 기억하며, 위의 표현식이 한 비트에 대해서 참이 된다면, 일련의 비트들에 대해서도 참이 된다.

2의 보수와 음수

컴퓨터는 일반적으로 정수를 저장할 때 2의 보수 형태로 저장한다. 양수를 표현할 때에는 아무 문제가 없지만, 음수를 표현할 때에는 그 수의 절댓값에 부호비트를 1로 세팅한 뒤 2의 보수를 취한 형태로 표현한다. N비트 숫자에 대한 2의 보수는 2의 N승에 대한 보수값과 같다. 여기서 N은 부호비트를 뺀 나머지 값을 표현할 때 사용되는 비트의 개수이다.

4비트로 표현된 정수 -3을 살펴보자. 비트 4개 중에서 하나는 부호비트, 값은 나머지 세 개가 표현한다고 했을 때 2의 3승에 대한 보수를 구해보자. -3의 절댓값인 3의 8에 대한 보수는 5가 된다. 5를 2진수로 표현하면 101이 되고, 따라서 -3을 4비트의 2진수로 표현하면 1101이 된다. 여기서 첫 번째 비트는 부호비트를 나타낸다.

2의 보수를 표현하는 다른 방법은 양수로 표현된 2진수를 뒤집은 뒤 1을 더해 주는 것이다. 예를 들어 3을 2진수로 표현하면 011이 되는데, 이 숫자를 뒤집으면 100이 되고, 여기에 1을 더하면 101이 된다. 여기에 마지막으로 부호비트를 앞에 붙여주면 1101이 된다.

산술 우측 시프트 vs 논리 우측 시프트

우측 시프트 연산에는 두 가지 종류가 있다. 하나는 산술 우측 시프트, 이는 기본적으로 2로 나눈 결과와 같다. 다른 하나는 논리 우측 시프트, 이는 우리가 일반적으로 비트를 옮길 때 보이는 것처럼 움직인다.

논리 우측 시프트는 비트를 옆으로 옮긴 다음에 최상위 비트에 0을 넣는다. 즉 >>> 연산과 같다. 최상위 비트가 부호비트인 8비트 정수에 논리 우측 시프트를 적용하면 다음과 같다.

10110101 -> 01011010 (한 칸씩 이동하고, 왼쪽을 0으로 채움)

산술 우측 시프트는 비트를 오른쪽으로 옮기기는 하지만 부호비트는 바꾸지 않는다. 따라서 이 연산은 대략 값을 2로 나눈 효과가 있고, >> 연산과 같다.

10110101 -> 11011010 (한 칸씩 이동했지만, 부호비트는 변하지 않음)

다른 방법으로 살펴보자, 예를 들어 값이 존재하고 이를 계속적으로 시프트로 밀어낸다고 가정 하면, 산술 우측 시프트에서 또는, 논리 우측 시프트에서는 어떤 반응을 보이게 될까?
논리 시프트를 사용하면 최상위 비트에 0을 반복적으로 채워 넣으므로 결과적으로 0이 되며, 산술 시프트를 사용하면 최상위 비트에 1을 반복적으로 채워 넣게 되므로 결과적으로 -1이 될 것이다.

기본적인 비트 조작 : 비트값 확인 및 채워넣기

비트값 확인

아래의 메서드는 1을 i비트만큼 시프트해서 00010000과 같은 값을 만든다. 그 다음 AND 연산을 통해 num의 i번째 비트를 뺀 나머지 비트를 모두 삭제한 뒤, 이 값을 0과 비교한다. 만약 이 값이 0이 아니라면 i번째 비트는 1이어야 하고, 0이라면 i번째 비트는 0이어야 한다.

boolean getBit(int num, int i) {
	return ((num & 1 << i)) != 0);
}

비트값 채워넣기

SetBit는 1을 i비트만큼 시프트해서 00010000과 같은 값을 만든다. 그 다음 OR 연산을 통해 num의 i번째 비트값을 바꾼다. i번째를 제외한 나머지 비트들은 0과 OR 연산을 하게 되므로 num에 아무 영향을 끼치지 않는다.

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

비트값 삭제하기

이 메서드는 setBit를 거의 반대로 한 것과 같다. NOT 연산자를 이용해 (00010000)을 11101111과 같이 만든 뒤 num과 AND 연산을 수행한다. 그러면 나머지 비트의 값은 변하지 않은 채 i번째 비트값만 삭제된다.

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

최상위 비트에서 i번째 비트까지 모두 삭제하려면 (1 << i)로 i번째 비트를 1로 세팅한 뒤 이 값에서 1을 뺀다. 그러면 i번째 비트 밑은 모두 1로 세팅되고 그 위로는 모두 0으로 세팅된다. 이 mask 값과 num을 AND 연산한다면 하위 i개의 비트를 뺀 나머지 비트를 모두 삭제할 수 있다.

int clearBitsMSBthroughI(int num, int i) {
	int mask = (1 << i) - 1;
	return num & mask;
}

i번째 비트에서 0번째 비트까지 모두 삭제하려면 어떻게 해야 할까? 모든 비트가 1로 세팅된 -1을 왼쪽으로 i+1만큼 시프트하면 된다. 그러면 i번째 비트 위로는 모두 1로 세팅되고 하위 i개 비트는 모두 0으로 세팅된다.

int clearBitsIthrough0(int num, int i) {
	int mask = (-1 << (i + 1));
	return num & mask;
}

비트값 바꾸기

i번째 비트값을 v로 바꾸고 싶다면, 우선 11101111과 같은 값을 이용해 (i=4인 경우) i번째 비트값을 삭제해야 한다. 그 뒤 우리가 바꾸고자 하는 값 v를 왼쪽으로 i번 시프트한다. 그러면 i번째 비트값은 v가 될 것이고, 나머지는 모두 0이 될 것이다. 마지막으로 OR연산을 이용해 i번재 비트값을 v로 바꾸어 준다.

int updateNit(int num, int i, boolean bitIs1) {
	int value = bitIs1 ? 1 : 0;
	int mask = ~(1 << i);
	return (num & mask) | (value << i);
}