Dev Uni

비트 연산

5 min read

수를 2진수로 보고 비트 하나하나에 직접 연산하는 것. 일반 산술 연산보다 빠르고, 여러 개의 참과 거짓을 정수 하나에 담는 데 쓴다.

비트 논리 연산자

논리 연산자는 넷이다.

연산자이름규칙
&AND둘 다 1일 때만 1
|OR하나라도 1이면 1
^XOR다르면 1, 같으면 0
~NOT0과 1을 뒤집는다
  0000 0101   // 5
& 0000 1010   // 10
-----------
  0000 0000   // 0

  0000 0101   // 5
| 0000 1010   // 10
-----------
  0000 1111   // 15

~를 쓸 때는 맨 앞 비트가 부호라는 걸 잊으면 안 된다. 0000 1010인 10을 뒤집으면 1111 0101이라 ~10은 -11이다. 뒤집는 순간 양수가 음수가 된다.

논리 연산자 &&, ||와 달리 비트 연산자 &, |는 결과가 확정되어도 뒤에 있는 식을 실행한다. 단락 회로 평가가 없다.

XOR의 성질

XOR은 성질이 특이하다. a ^ a == 0이고 a ^ 0 == a다. 같은 값이 짝수 번 나오면 사라지므로, 배열에서 하나만 홀수 번 등장하는 값을 찾을 때 전부 XOR하면 그 값만 남는다.

시프트 연산

시프트 연산은 셋이다. <<는 비트를 왼쪽으로 밀어 한 칸에 2배가 되고, >>는 오른쪽으로 밀어 한 칸에 절반이 되며 부호 비트를 유지한다. >>>도 오른쪽으로 밀지만 빈자리를 0으로 채워 부호를 무시한다.

5 << 2는 0001 0100으로 20이고 10 >> 2는 0000 0010으로 2다. 양수에서는 n << 1이 n * 2, n >> 1이 n / 2와 같고 곱셈과 나눗셈보다 빠르다. >>와 >>>의 차이는 음수에서만 드러나는데, >>는 음수를 음수로 유지하지만 >>>는 양수로 만들어버린다.

비트마스크로 부분집합 훑기

비트마스크는 정수 하나의 각 비트를 n번 원소를 골랐는지로 쓰는 기법이다. 완전 탐색에서 부분집합을 전부 만들 때 자주 나온다. 원소가 N개면 부분집합은 2ᴺ개이고, 이는 0부터 2ᴺ-1까지의 정수와 정확히 대응한다. 그래서 반복문 하나로 모든 부분집합을 훑을 수 있다.

for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) {
            // i번째 원소가 포함된 경우
        }
    }
}

1 << n이 곧 2ⁿ이고, mask & (1 << i)로 i번째 비트가 켜져 있는지 확인한다.

참고

XOR로 임시 변수 없이 두 값을 교환하는 요령은 원본에 없다. a ^ a가 0이고 a ^ 0이 a라는 데서 따라오는데, 자바 언어 명세가 ^의 결과를 두 피연산자의 비트별 배타적 논리합으로 정의하고 있으므로 두 항등식은 정의에서 바로 나온다. The Java Language Specification, 15.22.1 Integer Bitwise Operators

시프트로 곱셈과 나눗셈을 대신하는 요령은 양수에서만 성립한다. >>는 버림이 아니라 내림이라 음수에서 어긋난다. -5 >> 1은 -3이지만 -5 / 2는 자바의 정수 나눗셈이 0 쪽으로 잘라내므로 -2다. 원본은 이 단서 없이 기존 값 / 2ⁿ이라고만 적었다. The Java Language Specification, 15.19 Shift Operators

관련

출처