비트 연산자 유즈 케이스 모음

실제 코딩을 할 때나 코딩 인터뷰에서 사용해도 괜찮을법한 비트 연산자 유즈 케이스를 알아보자.

 

n/2, n*2, 2^n

n / 2

n >>> 1

n >>> 1 연산은 Java의 경우 n / 2 사용할 경우 발생할 수 있는 overflow를 원천적으로 봉쇄할 수 있다는 장점이 있다.

n >> 1를 사용하는 경우 overflow가 발생할 수 있음에 주의.

 

n * 2

n << 1

n << 1는 속도의 측면보다는 2의 배수씩 곱한다는 의미를 명시적으로 나타내기 위해 주로 사용된다.

 

2^n

1 << n

1 << n은 해당 값이 2의 배수(2, 4, 8, 16 ...)의 형태를 가진다는 것을 명시적으로 하기 위해 주로 사용된다.

 

 

짝수, 홀수 판별

n % 2 == 1 

n & 1

 1101
&0001
-----
 0001

n을 binary로 나타내면 가장 마지막 자리수(MSB)가 홀수일 경우 1, 짝수일 경우 0인 점을 1과 AND 연산자로 계산하여 홀짝을 판별하는 방법이다.

 

Pair 제거

아래와 같이 배열에 하나의 값을 제외하고 전부 1쌍의 값을 가지고 있는 경우에 하나의 값을 찾아야 되는 경우를 생각해보자.

var arr = new int[]{1,2,4,5,1,4,2};
var sum = 0;
for (var i : arr) {
    sum ^= i;
}

XOR 연산자인 ^로 같은 값을 2번 계산하는 경우 값이 제거되는 점을 이용한다. 

위 계산의 결과 5가 sum에 담기게 된다.

 

n번째 자리의 bit가 켜져있는지 확인

비트마스킹을 이용하는 경우 x의 n번째 자리가 1인지(켜져있는지) 0인지를 확인하는 방법은 다음과 같다.

x >> n & 1
//혹은
x & (1 << n)
//둘 다 같은 표현식

x >> n & 1의 경우 x를 >>로 먼저 n자리만큼 0으로 밀어낸 후 & 연산자를 이용하여 해당값이 1인지 판별하는 방법이며

x & (1 << n)의 경우 1을 <<로 n자리만큼 올린 후 & 연산자로 판별하는 방법이다. 

둘중에 본인에게 편한 방법으로 사용하면 됨.

 

---

이 밑으로는 범용적으로 사용하기보다 특정 상황에서 사용할 수 있을법한 비트연산자 사용법을 다룬다.

 

해싱

int a = 1230123;
int b = 1234555;
int c = 5865683;
int hash = a ^ b ^ c;
System.out.println(hash); //5870467

hash ^= a;
hash ^= b;
System.out.println(hash); //5865683

Encryption에서 XOR 연산자가 많이 사용되는데 이를 매우 간단하게 표현하면 위와 같이 사용할 수 있다.

 

특정 자리 추출

어떤 이미지 픽셀에서 RED 색상만 추출하고 싶은 경우를 생각해보자.

이미지 픽셀은 0xCCDDEE (0xRRGGBB)처럼 표현될 수 있고 여기서 RR만 추출하는 과정은 다음과 같다.

int imagePixel = 0xCCDDEE;
int redColour = (imagePixel & 0xFF0000) >> (1 << 4);
System.out.println(Integer.toHexString(redColour)); //cc

0xCCDDEE를 0xFF0000과 AND 연산자를 통해 0xCC0000로 추출 후 

4자리라는 의미를 표현하기 위해 (1 << 4)로 명시적으로 표기한 값을 이용하여 4자리만큼 밀어내고

마지막으로 CC라는 RED 색상만 추출할 수 있게 되었다.

 

bit마다 특정값 할당

int Local = 1 << 0,
External = 1 << 1,
CallerIDMissing = 1 << 2,
Chargeable = 1 << 3;

int flags = 0;

위와 같이 특정 bit마다 특정 값을 가질 수 있게 할당한 이후에 이를 비트 연산을 통해 flag를 값이 아닌 bit의 개념으로 이용할 수 있다.

 

만약 Chargeable 값을 flag에 설정하고 싶다면 아래와 같이 설정.

flags |= Chargeable;

 

CallerIDMissing이라는 설정을 flag에서 제거하고 싶다면 아래와 같이 설정.

해당 값이 flag에 적용되어 있든 되어있지 않든 flag에서 제거된다.

flags &= ~CallerIDMissing;

 

이렇게 bit마다 특정값을 할당하고 flag에 할당된 bit값을 주는 방식으로 사용할 수 있다.

 

레퍼런스

https://stackoverflow.com/questions/2096916/real-world-use-cases-of-bitwise-operators

Real world use cases of bitwise operators