[자바] 비트 연산자 알아보기!

비트 연산자란?

• 비트 연산자는 비트(bit) 단위로 논리 연산을 할 때 사용하는 연산자입니다.
• 원소의 수가 많지 않은 경우에, 작업을 여러 번 수행해야 하는 경우 비트 연산으로 최적화를 할 수 있습니다.

 

비트연산자	설명
&	대응되는 비트가 모두 1이면 1을 반환
|	대응되는 비트가 하나라도 1이면 1을 반환
^	대응되는 비트가 서로 다르면 1을 반환
~	비트를 서로 반전
<<	x의 비트를 지정한 수만큼 왼쪽으로 이동
>>	x의 비트를 부호를 유지하면서 지정한 수만큼 오른쪽으로 이동

 

& (비트 AND 연산)

int x = 5;             // 0 0 1 0 1
int y = 19;            // 1 0 0 1 1 

int x_and_y = 5 & 19;  // 0 0 0 0 1 => 1

• 비트 AND 연산은 양쪽 모두 1이어야 1을 반환합니다. boolean 타입을 &&로 연산을 할 때 양쪽 모두 true여야 true를 반환하는 것과 모습이 비슷하죠?!

 

| (비트 OR 연산)

int x = 5;             // 0 0 1 0 1
int y = 19;            // 1 0 0 1 1 

int x_or_y = 5 & 19;   // 1 0 1 1 1 => 23

 

^ (비트 XOR 연산)

int x = 5;             // 0 0 1 0 1
int y = 19;            // 1 0 0 1 1 

int x_xor_y = 5 & 19;  // 1 0 1 1 0 => 22

• 비트 XOR 연산은 양쪽이 다를 때 1을, 같으면 0을 반환합니다.

 

~ (비트 NOT 연산)

int x = 5;          // 00000000 00000101
int y = 19;         // 00000000 00010011

int notX = ~5;      // 11111111 11111010 => -6
int notY = ~19;     // 11111111 11101100 => -20

• NOT 연산자는 단항 연산자입니다. 0과 1을 서로 바꾸어주는 연산을 해줍니다.
• 연산의 결과는 기존 값 + 1에 -1을 곱한 값이 됩니다. 다시 말하면 -(x + 1) 이 되는 것이죠!

 

<< (left shift)

int x = 5;           // 0 0 1 0 1
int x_L_1 = 5 << 1;  // 0 1 0 1 0  =>  10

int y = 19;          // 0 1 0 0 1 1
int x_L_1 = 19 << 1; // 1 0 0 1 1 0  => 38

• 왼쪽으로 한 칸 쉬프트를 한다고 가정하면, 자리수가 하나가 늘어나게 되고 계산값은 기존값의 2를 곱한 값이 나오게 됩니다.

 

>> (right shift)

int x = 5;           // 0 0 1 0 1
int x_R_1 = 5 >> 1;  // 0 0 0 1 0  => 2

int y = 19;          // 0 1 0 0 1 1
int x_R_1 = 19 >> 1; // 0 0 1 0 0 1  => 9

• 오른쪽으로 한 칸 쉬프트를 하면 2로 나눈 뒤 소수점 이하를 버린 결과값이 나오게 됩니다.
• 소수점 이하가 버려지는 것은, 마지막 자리가 쉬프트 되면서 사라지는데 끝자리가 1이었을 경우 그 값이 사라지기 때문입니다.

 

논리 연산에서의 단축 평가

int a = 1, b = 1;

boolean boolAnd = a > b && a++ > b;  // false
boolean boolOr = a == b || a++ == b // true

// a = 1

• 논리 연산에서 사용하는 &&, ㅣㅣ 연산은 단축 평가를 행합니다.
• 위 예제에서 a > b는 false 입니다. 뒤에 나오는 연산은 && 연산이기 때문에 앞에 나오는 연산의 결과가 false 라면 뒤에 나오는 연산의 결과에 상관없이 false이므로 뒤 연산을 하지 않는 것입니다.
• 따라서 뒤에서 a++ 연산을 해주었음에도 a의 결과값은 그대로 1이 유지됩니다.

int c = 1, d = 1;

boolean bitAnd = c > d & c++ > d;  // false

// c = 2

• & (비트 AND 연산), |(비트 OR 연산) 으로 같은 작업을 수행하면 false라는 결과값은 동일하지만 단축 평가를 수행하지 않고 무조건 뒤의 연산도 수행하기 때문에 c의 값이 변화되어 있는 것이죠!
• boolean 결과에 상관없이 추가 연산이 필요할 때 사용할 수 있을 것 같네요!

 

비트 연산을 활용하는 방법

홀수, 짝수 판별(비트 & 연산자)

int a = 3;      // 0 0 1 1
int b = 10;     // 1 0 1 0

int one = 1;    // 0 0 0 1

for (int i : new int[] {a, b}) {
    if (i % 2 == 1) {
        System.out.println(i + " = 홀수");
    }

    if ((i & 1) == 1) {
        System.out.println(i + " = 홀수");
    }
}

• 기본적으로 짝수와 홀수를 판별할 때 2로 나눈 나머지의 값을 보고 판별하는데요.
• &와 함께 1로 연산하는 방법도 있습니다.
• 이진법에서 모든 홀수는 첫 자리가 1이고 짝수는 0이 나옵니다. 이것을 1(0 0 0 1)로 & 연산을 해주면 홀수는 1이 나올 것이고 짝수는 0이 나오는 것이죠!
• & 연산은 대응하는 자리가 모두 1이어야만 1을 반환하는데, 0 0 0 1 의 경우는 맨 뒷자리를 제외하고 0이므로 기준값의 비트에 상관없이 0이 반환되고 마지막 자리만 바뀌게 되는 원리입니다.

 

변수 스와핑(XOR 연산자)

int a = 5;
int b = 19;

int temp = a;
a = b;
b = temp;

• 어떤 변수의 값을 서로 스왑하려고 할 때 일반적으로 임시 변수에 하나의 값을 담아두고 스왑하는 방식을 많이 사용하는데요.

int a = 5;      // 0 0 1 0 1
int b = 19;     // 1 0 0 1 1

a ^= b;         // 1 0 1 1 0 (a)
b ^= a;         // 0 0 1 0 1 (b)
a ^= b;         // 1 0 0 1 1 (a)

• 위와 같은 방법으로 XOR 연산을 함으로써 스왑할 수도 있습니다.

 

비트마스킹

• 비트마스크란 이진수를 사용하는 컴퓨터의 연산 방식을 이용해서 정수의 이진수 표현을 자료 구조로 사용하는 기법입니다.

int PIZZA = 1;            // 0 0 0 1
int CHICKEN = 1 << 1;     // 0 0 1 0
int HAMBURGER = 1 << 2;   // 0 1 0 0
int SALAD = 1 << 3;       // 1 0 0 0

• 좋아하는 음식의 선호도를 조사한다고 해봅시다.
• 왼쪽 쉬프트 연산자를 통해 값을 지정해두고 해당 자리수가 1이 나오면 해당 음식을 선호하는 것으로 가정합니다.

int A = PIZZA | SALAD;    // 1 0 0 1
int B = PIZZA | CHICKEN;  // 0 0 1 1

• 지정을 해줄 때는 비트 OR 연산, 즉 어느 하나라도 1이면 1을 반환하도록 해서 자리수를 채워넣습니다.

 

조회

boolean isLikeSalad = (A & SALAD) > 0;
boolean isLikeHamburger = (B & HAMBURGER) > 0;

// true
// false

• 이후에 해당 음식을 선호하는지 여부를 조회할 때는 비트 & 연산자를 통해 해당 값이 0보다 큰 지를 확인하면 됩니다.
• A의 경우 1 0 0 1 이었는데 1 0 0 0 인 샐러드와 & 연산이 되므로 1 0 0 0 이 반환되고, 이는 0보다 큰 값이니 true가 반환되는 것이고
• B의 경우 0 0 1 1 에서 0 1 0 0 이 & 연산이 되면 대응하는 자리가 모두 1인 경우가 없으므로 0 0 0 0, 즉 0이 반환되어 false가 되는 것이죠!

 

추가

• 대입 비트 연산자를 사용한다면 값을 수정하는 것도 가능합니다.

A |= HAMBURGER;

// A: 1 0 0 1
// H: 0 1 0 0
// A = 1 1 0 1

• A의 선호에 햄버거도 추가하고 싶다면 이처럼 대입 비트 OR 연산을 합니다. 그러면 기존에 1이던 값은 그대로 1이 될 것이고 햄버거의 값 또한 추가가 되겠네요!

 

삭제

A &= ~PIZZA;

// A: 1 1 0 1
// P: 0 0 0 1 => 1 1 1 0
// A = 1 1 0 0

• 만약 삭제하고 싶은 선호가 있다면 대입 비트 AND 연산과 함께 NOT 연산을 합니다.
• 원리는 변경하고 싶은 것 외 부분은 1로 바꾸어서 A의 값이 그대로 내려오도록 하고(A의 값이 1이라면 1 & 1 => 1, 0이라면 0 & 1 => 0 이 되므로) 변경하려는 부분을 0이 될 수 밖에 없도록 하는 것이죠!

 

토글

A ^= SALAD;
// A: 1 1 0 0
// S: 1 0 0 0
// A = 0 1 0 0

boolean isLikeSalad = (A & SALAD) > 0;
// A = 0 1 0 0
// S = 1 0 0 0
// false (0 0 0 0)

A ^= SALAD;
// A: 0 1 0 0
// S: 1 0 0 0
// A = 1 1 0 0
boolean isLikeSalad = (A & SALAD) > 0;
// A = 1 1 0 0
// S = 1 0 0 0
// true (1 0 0 0)

• 값이 토글되도록 하는 것은 대입 XOR 연산으로 할 수 있습니다.
• 한 번 대입하면 값이 반대로 바뀌고 다시 대입하면 원래의 값으로 돌아오는 것을 볼 수 있습니다!

 

그 외

두 집합 연산

A | B    // A와 B의 합집합
A & B    // A와 B의 교집합
A & (~B) // A에서 B를 뺀 차집합
A ^ B    // A와 B중 하나에만 포함된 원소들의 집합

 

집합의 크기 구하기

int bitCount(int A){
  if(A == 0) return 0;
  return A % 2 + bitCount(A / 2);
}

• 집합에 포함된 원소의 크기를 구하려고 한다면, 1인 bit의 수를 세어주면 됩니다.
• 자바에서는 Integer.bitCount() 비트에서 1의 개수를 세어주는 내장 API도 제공하고 있습니다.

 

최소 원소 찾기

int min = A & (-A);

• 집합에 포함된 가장 작은 원소(index가 가장 작은 원소)를 찾는 연산입니다. 켜져있는 bit 중 가장 오른쪽에 있는 bit를 찾게 됩니다.
• A = 0 0 1 0 1 0 0 이고, 1인 4번 인덱스를 k라고 가정합니다.
• 그러면 0 ~ k-1 까지는 모든 bit가 0입니다.(마지막 두 자리)
• 여기서 ~A+1 혹은 (-A) 연산을 해주면 1 1 0 1 1 0 0 이 되죠!
• 이 값을 A와 & 연산을 해준다면
• 0 0 1 0 1 0 0
• 1 1 0 1 1 0 0
• min = 0 0 0 0 1 0 0 으로 k만 켜진 상태가 됩니다!

 

최소 원소 지우기

A &= (A - 1);

• 가장 오른쪽에 켜져 있는 bit를 지우는 연산입니다.
• A에서 1을 빼게 되면 가장 오른쪽에 있는 bit는 0이 되고 그보다 오른쪽 bit들은 모두 1이 됩니다.
• A = 1 0 1 0
• A-1 = 1 0 0 1
• A & (A-1) = 1 0 0 0

---

참고 자료

• 비트 마스크
• 비트와 비트마스크
• 얄코 - 비트 연산자들을 알아보자