🦊 3. Binary Search & Bitwise Operations

05. 비트 조각

2의 보수와 음수

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

양수를 표현할 때는 아무 문제가 없지만 음수를 표현할 때는 그 수의 절댓값에 부호비트를 1로 세팅한 뒤 2의 보수를 취한 형태로 표현한다.

4비트로 표현된 정수 -3 에서 비트 1개는 부호, 나머지 3개가 값을 표현할 것이다.

그러면 2^3 에 대한 보수를 구하면

-3

의 8에 대한 보수는 5이다.

따라서 -3 을 4비트의 2진수로 표현하면 1101 이다.

다시 말해 -K 를 N 비트의 2진수로 표현하면 concat(1, 2^(N-1) - K) 가 된다.

또 다른 방법은 양수로 표현된 2진수를 뒤집은 뒤 1을 더하는 방법이다.

3은 011인데 뒤집으면 100이 되고 1을 더하면 101이 된다.

마지막으로 부호비트를 앞에 붙이면 1011이다

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

우측 시프트 연산에는 두 가지 종류가 있다.

산술 우측 시프트는 2로 나눈 결과와 같다.

비트를 옆으로 옮기지만 최상위 부호비트는 바뀌지 않는다.

논리 우측 시피트는 비트를 옮길 때 보이는 것처럼 움직인다.

비트를 옆으로 옮긴 다음 최상위 비트에 0을 넣는다.

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

비트값 확인

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

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

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

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

비트값 채워넣기

1을 i 비트만큼 시프트한 후 OR 연산을 통해 num 의 i 번째 비트값을 바꾼다.

i 번째를 제외한 나머지 비트들은 0 과 OR 연산을 하게 되어 num 값에 영향을 미치지 못한다.

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

비트값 삭제하기

NOT 연산자를 이용해 num 과 AND 연산을 수행한다.

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

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

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

i 번째 비트를 1로 세팅한뒤 이 값에서 1을 빼면 i 번째 비트 밑이 모두 1로 세팅된다.

하위 i 번째 비트를 뺀 나머지 비트를 모두 삭제할 수 있다.

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

반대로 i 번째 비트에서 0 번째 비트까지 삭제하려면?

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

그러면 i 번째 비트 위로는 모두 1, 하위 i개 비트는 모두 0이 된다.

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

비트값 바꾸기

i 번째 비트값을 v 로 바꾸고 싶다면, i 번째 비트값을 삭제한 후

v 를 왼쪽으로 i 번 쉬프트한 값을 OR 연산으로 대입한다.

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

10. 정렬과 탐색 - 탐색 알고리즘

이진 탐색(Binary Search)은 정렬된 배열에서 원소 x를 찾고자 할 때 사용한다.

x를 중간에 위치한 원소와 비교한 뒤, x가 중간에 위치한 값보다 작다면 배열의 왼쪽 절반을 재탐색하고,

크다면 배열의 오른쪽 절반을 재탐색 한다.

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

int binarySearch(int[] a, int x) {
	int low = 0;
	int high = a.length - 1;
	int mid;
	while (low <= high) {
		mid = (low + high) / 2;
		if (a[mid] < x) {
			low = mid + 1;
		} else if (a[mid] > x) {
			high = mid - 1;
		} else {
			return mid;
		}
	}
	return -1;
}