🐣 3. Binary Search & Bitwise Operations

3. Binary Search & Bitwise operations

📚 1. 비트 조작

• 연산들이 비트 단위로 이루어짐

2의 보수와 음수

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

• 음수 표현 : 수의 절댓값에 부호 비트(sign bit)를 1로 세팅

• $-k$를 $N$비트의 2진수로 표현하는 방법

  1. $concat(1, 2^{N-1}-k)$
  2. $NOT k + 1$

• 왼쪽 - 오른쪽 절댓값 합산 결과 = 항상 $2^3$
• 부호비트를 제외한 왼쪽 - 오른쪽 2진수 값 항상 동일

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

• 산술 우측 시프트(arithmetic right shift)
  • >> : 부호 비트 동일 (음수 연산시 그대로)
  • 2로 나눈 결과와 동일
• 논리 우측 시프트(logical right shift)
  • >>> : 빈자리 0으로 채움 (음수 연산시 양수로 변경)
  • 일반적인 비트 시프트

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

1. 비트값 확인

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

i번째 비트 값 확인(True

False)

1. 비트값 채워넣기

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

i번째 비트 값 변경

1. 비트값 삭제하기

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

1. 비트값 바꾸기

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