🐹 3. Binary Search & Bitwise Operations

05. 비트 조작

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

(0s: 모든 비트가 0인 값, 1s: 모든 비트가 1인 값)

[ 2의 보수와 음수 ]

컴퓨터는 일반적으로 정수를 저장할 때 2의 보수 형태로 저장한다.

양수의 경우 문제가 없지만, 음수를 표현할 때는 절댓값에 부호비트(sign bit)를 1로 세팅한 뒤 2의 보수를 취한 형태로 표현한다.

예시

4비트로 표현된 정수 -3

→ 맨 앞의 1은 부호비트, -3의 절댓값인 3의 8($=2^3$)에 대한 보수는 5이므로 2진수로 표현하면 101

따라서 4비트로 표현하면 1101이 된다.

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

산술 우측 시프트(arithmetic right shift)

• 기본적으로 2로 나눈 결과와 같다.

비트를 옆으로 옮긴다. 단, 부호비트는 바꾸지 않는다.

따라서 이 연산은 대략 값을 2로 나눈 효과가 있고, » 연산과 같다.

논리 우측 시프트(logical right shift)

• 우리가 일반적으로 비트를 옮길 때 보이는 것처럼 움직인다.

비트를 옆으로 옮긴 후 최상위 비트(most significant bit)에 0을 넣는다.

즉, »> 연산과 같다.

예시

x = -93242, count = 40일 때 아래 함수는 어떻게 동작할까?

논리 시프트를 사용하면 최상위 비트에 0을 반복적으로 채워 넣으므로 결과적으로 0이 될 것이다.

산술 시프트를 사용하면 최상위 비트에 1을 반복적응로 채워 넣게 되므로 결과적으로 -1이 될 것이다. (모든 비트가 1로 채워져 있으면 -1이 된다.)

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

비트값 확인

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

1. 1을 i비트만큼 시프트해서 00010000과 같은 값을 만든다.

2. AND 연산을 통해 num의 i번째 비트를 뺀 나머지 비트를 모두 삭제한 뒤, 이 값을 0과 비교한다.

   만약 이 값이 0이 아니라면 num의 i번째 비트는 1이어야 하고, 0이라면 i번째 비트는 0이어야 한다.

비트값 채워넣기

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

1. setBit는 1을 i비트만큼 시프트해서 00010000과 같은 값을 만든다.

2. OR 연산을 통해 num의 i번째 비트값을 바꾼다.

   i번째를 제외한 나머지 비트들은 0과 OR 연산을 하게 되므로 num에 아무 영향을 끼치지 않는다.

비트값 삭제하기

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

이 메서드는 setBit를 거의 반대로 한 것과 같다.

1. NOT 연산자를 이용해 (00010000)을 1101111과 같이 만든다.

2. num과 AND 연산을 수행한다.

   그러면 나머지 비트의 값은 변하지 않은 채 num의 i번째 비트값만 삭제된다.

최상위 비트에서 i번째 비트까지 모두 삭제하려면?

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

1. (1 << i)로 i번째 비트를 1로 세팅한다.

2. 이 값에서 1을 뺀다.

   그러면 i번째 비트 밑은 모두 1로 세팅되고 그 위로는 모두 0으로 세팅된다.

3. 이 mask 값과 num을 AND 연산하면 하위 i개의 비트를 뺀 나머지 비트를 모두 삭제할 수 있다.

i번째 비트에서 0번째 비트까지 모두 삭제하려면?

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

1. 모든 비트가 1로 세팅된 -1을 왼쪽으로 i+1만큼 시프트한다.

   그러면 i번째 비트 위로는 모두 1로 세팅되고 하위 i개 비트는 모두 0으로 세팅된다.

비트값 바꾸기

i번째 비트값을 v로 바꾸고 싶다면?

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

1. 11101111과 같은 값을 이용해(i=4라고 하면) i번째 비트값을 삭제해야 한다.

2. 우리가 바꾸고자 하는 값 v를 왼쪽으로 i번 시프트한다.

   그러면 i번째 비트값은 v가 될 것이고 나머지는 모두 0이 될 것이다.

3. OR 연산을 이용해 i번째 비트값을 v로 바꿔준다.

10. 정렬과 탐색

[ 이진 탐색 ]

: 정렬된 배열에서 원소 x를 찾고자 할 때 사용

1. 중간 원소와 x를 비교한다.
2. x가 더 작다면 왼쪽 절반을, x가 더 크다면 오른쪽 절반을 재탐색한다.

위 과정을 x를 찾거나 부분 배열의 크기가 0이 될 때까지 반복한다.