[Coding Interview University] 비트 연산 : 이론 및 구현

<본 블로그는 코딩인터뷰대학 님의 Git과 서적을 참고해서 공부하며 작성하였습니다 :-)>

 

🫧 비트 조작

: 0s 는 모든 비트가 0 인 값

: 1s 는 모든 비트가 1 인 값

: 연산들이 비트 단위로 이루어 진다!

: 한 비트에서 일어나는 일이 다른 비트에 어떤 영향도 미치지 않는다

 

🫧 2의 보수와 음수

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

: 양수를 표현할 땐 문제 없음

: 음수를 표현할 땐 그 수의 절댓값에 부호비트를 1로 세팅한 뒤 2의 보수를 취한 형태로 표현함

: N비트 숫자에 대한 2의 보수는 2^N 에 대한 보수값과 같음 (N은 부호비트를 뺀 나머지 값을 표현할 때 사용되는 비트의 개수)

: 2의 보수를 표현하는 다른 방법은 양수로 표현된 2진수를 뒤집은 뒤 1을 더해 주는 것

 

 

 

🫧 산술 우측 시프트 VS 논리 우측 시프트

• 산술 우측 시프트
  • 기본적으로 2로 나눈 결과와 같음
• 논리 우측 시프트
  • 일반적으로 비트를 옮길 때 보이는 것처럼 움직임
  • 비트를 옆으로 옮긴 다음에 최상위 비트에 0을 넣는다 (>>> 연산)
  • 비트를 오른쪽으로 옮기긴 하지만 부호비트는 바꾸지 않는다

 

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

💖 비트값 확인

: 1 을 i 비트만큼 시프트에서 00010000와 같은 값 만들기

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

: 이 값이 0이 아니라면 i번째 비트는 1, 0이라면 i번째 비트는 0이어야 함

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

 

🧡 비트값 채워넣기

: 1을 i비트만큼 시프트해서 00010000와 같은 값 만들기

: OR 연산을 통해 num의 i번째 비트값 바꾸기

: i번째를 제외한 나머지 비트들은 0과 OR 연산을 하므로 num에 영향 없음

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

 

💛 비트값 삭제하기

: 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 clearBitMSBthroughI(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번째 비트값을 삭제해야 함

: 바꾸고자 하는 값 v를 왼쪽으로 i번 시프트 한다

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

: 마지막으로 OR 연산을 이용해 i번째 비트값을 v로 바꿔준다

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

 

🫧 2의 보수, 음수

: 컴퓨터가 정수를 저장할 때는 대부분 2의 보수 형태로 저장

: 음수를 나타내기 위해서는 기존의 수에서 비트를 뒤집은 다음(1의 보수) 1을 더해주면 되는데, 이는 기존의 수를 2의 보수 표현을 이용해서 음수로 나타낸 것

 

🫧 산술 시프트, 논리 시프트

: 비트를 1bit씩 밀면서 생긴 빈자리에 새로운 bit를 채워주는 연산

 

🫧 기본 연산

• NOT [~] : 1이면 0, 0이면 1
• OR [|] : 두 값 중 1이 하나라도 있다면 1, 아니면 0
• 합집합 개념과 유사하다.
• XOR [^] : 두 값이 다르면 1, 같으면 0
• 실제로는 XOR에 들어가는 값 중 1의 갯수가 홀수개이면 1
• AND [&] : 두 값 모두 1이라면 1, 아니면 0
• 교집합 개념과 유사하다.
• SHIFT [<< >>] : 비트 단위로 한 칸씩 미는 연산

 

🫧 함수 구현

1. Get : 특정 위치의 비트 값을 가져온다.
2. Set : 특정 위치의 비트 값을 세팅한다.
3. Count : 세팅된 비트 값이 몇 개인지 반환한다.
4. Clear : 비트를 0으로 초기화 한다.
5. Toggle : 비트를 반전시킨다.
6. MSB : 최상위 비트를 찾는다.
7. LSB : 최하위 비트를 찾는다.

 

🫧 비트마스크(BitMask)

: 여러 표현 시 비트를 이용하여 메모리 사용을 줄이고 효율적으로 표현할 수 있다

ex) 집합 {1,2,3,5}가 있을 때 11101로 나타낼 수 있고 저장할 때는 10진수로 29를 저장하면 된다

: 배열을 이용할 필요없이 정수 하나만으로 저장이 가능하므로 메모리 사용을 줄일 수 있다