비트 연산 활용

N번째 비트 조회

변수 target의 N번째 비트가 1인지 여부: AND 연산을 수행합니다.

해당 연산이 0이면 비트가 없는 것이고, 1이면 비트가 있는 것입니다.

 

target & (1<<N)

---

N번째 비트 추가

변수 target의 N번째 비트 추가: OR 연산을 수행합니다.

 

target |= (1<<N)

 

---

N번째 비트 삭제

변수 target의 N번째 비트를 제거하려면, 아래와 같이 NOT과 AND 연산을 해줍니다.

 

target &= ~(1<<N)

---

N번째 비트 토글

변수 target의 N번째 비트를 토글하려면 XOR 연산을 해줍니다.

토글: 비트값이 0이면 1로, 1이면 0

 

target ^= (1<<N)

---

모든 비트가 1인 N개의 비트값 만들기

1<<N에서 1을 빼줍니다.

 

target = (1<<N)-1

---

N번째 값부터 왼쪽 모든 비트 제거

변수 target의 N번째 값부터 왼쪽 모든 비트를 제거하려면, target과 (1<<N) - 1을 AND 연산해줍니다.

(1<<N) - 1은 N개의 비트값이 1이므로, N번째 후(왼쪽) 비트는 모두 0입니다.

 

target &= ((1<<N)-1)

---

N번째 값부터 오른쪽 모든 비트 제거

변수 target의 N번째 값부터 오른쪽 모든 비트를 제거하려면, 아래와 같이 AND 연산을 해줍니다.

 

target &= (-1 << (N+1))

 

-1은 모든 비트값이 채워진 값입니다. -1을 N+1만큼 왼쪽 시프트하면 N번째 값부터 오른쪽 모든 비트가 0이 되고, 이 값을 target과 AND 연산하게 되는 것입니다.

---

집합연산

• 합집합: a|b
• 교집합: a&b
• 차집합 (a-b): a&~b
• a와 b 중 하나에만 포함된 원소들의 집합: a^b

 

집합의 크기 구하기

 

int bitCount(int x){
	if(x==0) return x;
	return x % 2 + bitCount(x / 2); // (x&1) + bitCount(x>>1)
}

---

최소 원소 찾기

변수 target을 이진수로 표혔을 때, 최하위 비트가 나타내는 원소를 찾는 것으로, 이 정수의 이진수 표현에서 끝에 붙어 있는 0이 몇 개인지를 나타냅니다. (최하위 비트의 번호 반환)

 

target & -target

 

 

예를 들어, 3은 이진수로 표현하면 0110 이므로, 최하위 비트가 나타내는 값은 1입니다.

---

최소 원소 지우기

 

target &= (target-1)

 

 

target-1은 최하위 비트를 끄고 그 밑의 비트들을 모두 켠 것이므로, 두 값을 AND 하면 최하위 비트와 그 이하의 비트들은 전부 0이 됩니다. 

이 연산은, 어떤 정수가 2의 거듭제곱 값인지 확인할 때도 유용합니다. 최하위 비트를 지웠을 때 0이 된다면 주어진 수는 2의 거듭제곱임을 알 수 있습니다. (2의 거듭제곱: 10, 100, 1000,...)

---

모든 부분 집합 순회하기

 

for(int subset = target; subset; subset = (subset - 1) & target) {}

 

subset - 1에서 켜져 있던 최하위 비트가 꺼지고 그 밑의 비트들은 전부 켜지게 됩니다. 이 결과와 target의 교집합을 구하면(&연산), 최하위 비트는 이미 꺼져 있으니 최하위 비트가 사라지고, 최하위 비트의 밑의 비트들은  target에 속하지 않았으므로 그 비트들도 모두 꺼지게 됩니다. 즉, 최소 원소를 지워가면서 이를 반복하여 target의 모든 부분 집합을 방문할 수 있습니다. (공집합은 방문하지 않습니다.)

---

나머지 연산

<<N은 2의 N제곱, >>N은 2를 N번 나눈 것입니다.

M이 2의 N 제곱일 때, M으로 나눈 나머지 연산은 아래와 같습니다.

 

target & (M - 1)

 

 

---

 

백준 문제

• 숫자카드 - 소스코드
• 대칭 차집합 - 소스코드

---

[참고자료]

https://velog.io/@emplam27/CS-%EB%B9%84%ED%8A%B8%EC%97%B0%EC%82%B0Bit-Operation

[CS] 비트연산(Bit Operation)

https://debugjung.tistory.com/entry/%EB%B9%84%ED%8A%B8%EC%97%B0%EC%82%B0%EC%9C%BC%EB%A1%9C-%EC%82%B0%EC%88%A0%EC%97%B0%EC%82%B0-%EB%B9%A0%EB%A5%B4%EA%B2%8C-%EC%B2%98%EB%A6%AC%ED%95%98%EA%B8%B0

비트 연산으로 산술연산 빠르게 처리하기