Java | 비트 연산자

최근 코딩테스트를 공부하며 DP 문제를 푸는데,, 아무리 생각해도 이걸 어떻게 풀어야할지 감도 잡히지 않아서 풀이를 참고하려고 검색했다

근데 웬걸? 비트마스킹... 을 써야한다는 것이었다...
문제 : 백준 2098번 외판원 순회

나는 비트연산자도 비트마스킹도 모르는데... 쩝... 🤯
비트연산자를 모르니까 전혀 무슨 풀이인지 이해가 가지 않아서, 언젠가는 꼬옥 비트연산자를 정리해야지! 생각하다가 이제서야 정리해본다 💦

비트 연산자란?

데이터를 비트 단위로 연산할 수 있도록 하는 연산자이다.
0과 1로 표현이 가능한 정수 타입이나 정수형 으로 캐스팅이 가능한 자료형만 비트 연산이 가능하다!

1. AND 연산 (&)

두 비트의 각 자리수에 대해 둘 다 1일 경우 1로 반환한다

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

int x_and_y = 5 & 9;	// 0 0 0 0 1 | 십진수 : 1

2. OR 연산 (|)

두 비트의 각 자리수에 대해 하나라도 1일 경우 1로 반환한다

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

int x_or_y = 5 | 19		//1 0 1 1 1 | 십진수 : 23

3. XOR 연산 (^)

두 비트의 각 자리수에 대해 하나는 1이고 다른 하나가 0일 경우 1로 반환한다

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

int x_xor_y = 5 ^ 19	//1 0 1 1 0 | 십진수 : 22

4. NOT 연산 (~)

단항 연산자로, 비트를 반전시켜 준다 (보수)
양수 정수의 경우 +1을 하고 -를 곱한 결과가 나온다

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

int notX = ~5			//1 1 0 1 0 | 십진수 : -6
int notY = ~19			//0 1 1 0 0 | 십진수 : -20

5. Shift 연산자 ( <<, >> )

피연산자의 각 자리(2진수로 표현했을 때)를 오른쪽 >> 또는 왼쪽 <<으로 이동시킨다

<< 왼쪽 쉬프트

피연산자에 2를 곱한 결과가 나온다

int a = 5;				//0 0 1 0 1 
int a_L_1 = 5 << 1;		//0 1 0 1 0	 | 십진수 : 10

int b = 19;				//1 0 0 1 1
int b_L_1 = 19 << 1;	//0 1 0 0 1 | 십진수 : 38

>> 오른쪽 쉬프트

피연산자를 2로 나눈 다음 소수점 이하를 버린 결과가 나온다

int a = 5;				//0 0 1 0 1 
int a_R_1 = 5 >> 1;		//0 0 0 1 0 | 십진수 : 2

int b = 19;				//1 0 0 1 1
int b_R_1 = 19 >> 1;	//0 1 0 0 1 | 십진수 : 9

그래서 이걸 어디에 쓰나요?

&, | 경우

int a = 1, b = 1;
int c = 1, d = 1;

boolean bool1 = a > b && a++ > b;	//false
boolean bool2 = c == d || c++ == d; //true

// a = 1, b = 1
// c = 1, d = 1

그냥 &&, || 연산의 경우, 단축평가가 일어나 bool1의 뒤에 있는 a++ 연산과 bool2 뒤에 있는 c++ 연산이 일어나지 않는다

하지만 &, | 연산자를 사용한다면 단축평가가 일어나지 않게 할 수 있다

int a = 1, b = 1;
int c = 1, d = 1;

boolean bool1 = a > b & a++ > b;	//false
boolean bool2 = c == d | c++ == d; //true

// a = 2, b = 1
// c = 2, d = 1

^ 의 경우

temp로 새로운 변수를 만들지 않고 값을 swap 할 수 있다

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

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

비트마스킹... 🔥

이놈이 바로 내가 코테를 풀다가 살-짝 미쳐버리게 한 놈이다

비트마스킹은 해당 각 자리별로 0, 1을 통해 자신이 표시하고 싶은 내용을 표시하는 것이다.

int WIFI 	= 1;			//0 0 0 1
int PEN 	= 1 << 1;		//0 0 1 0
int CAMERA 	= 1 << 2;		//0 1 0 0
int SDCARD 	= 1 << 3;		//1 0 0 0

각 자리마다 1이면 해당 기준을 가진 것, 0이면 없는 것으로 나타낸 것

int tablet_1
= PEN | SDCARD;				//1 0 1 0

int tablet_2
- WIFI | CAMERA | SDCARD; 	//1 1 0 1

boolean t1_HasPen 	= 	(tablet_1 & PEN);	//true
boolean t2_HasWifi 	= 	(tablet_2 & WIFI); 	//true
boolean t2_HasPen 	=	(tablet_2 & PEN); 	//false

삽입하기

tablet_1 |= CAMERA;
tablet_2|= PEN;

삭제하기

tablet_1 &= ~PEN;
tablet_2 &= ~CAMERA;