[TIL] 비트연산자, 비트마스킹, 외판원 순회

0.  Today I Learned

안녕하세요! FlyDuck Dev🦢입니다.

오늘은 비트마스킹을 활용해야 하는 DP 문제(외판원 순회)를 풀기 위해서, 비트연산에 대해서 알아보는 시간을 가졌습니다. TIL 목적상, 문어체로 작성하게 됨을 미리 밝힙니다!

 

🔭오늘의 공부 자료

(1) 큰돌의터전님의 블로그 및 강좌

(2) 주니온 연구소님의 강좌

 

 

 

 

 

1.  비트 연산자

&	비트단위로 AND 연산을 한다.
|	비트단위로 OR 연산을 한다.
^	비트단위로 XOR 연산을 한다.
~	피연산자의 모든 비트를 반전시킨다.
<<	피연산자의 비트 열을 왼쪽으로 이동시킨다.
>>	피연산자의 비트 열을 오른쪽으로 이동시킨다.

 

 

비트연산자 기초 &, |

&는 true & true = true (1 & 1 = 1)고 나머지는 모두 false를 반환한다.

0 & 0	0
0 & 1	0
1 & 0	0
1 & 1	1

만약 1001 & 1000을 1000이 된다.

|는 하나라도 true면 모두 true가 된다.

0 | 0	0
0 | 1	1
1 | 0	1
1 | 1	1

만약 1001 | 1000을 하면 1001이 되고,

1001과 0110을 하면 11111이 된다.

비트연산자 기초 <<, >>

왼쪽 시프트 연산자 << , 오른쪽 시프트 연산자 >>

a << b는 a라는 비트를 b만큼 왼쪽으로 옮긴다는 의미이다.

예를 들어 111(7) << 1 한다면 1110(14)이 되고

111(7) << 2를 하면 11100(28)이 된다.

즉, a << b 는 a * 2 ^ b와도 같은 의미이다. 

비트마스킹할 때는 (1 << value)꼴로 많이 쓰인다.

1 << 3은 1000(8)

1 << 4은 10000(16)

​

오른쪽 시프트 연산자 >> 는 다음과 같이 비트를 오른쪽으로 옮기는 것을 말한다.

a >> b는 a라는 비트를 b만큼 오른쪽으로 옮긴다는 의미이다.

101(5) >> 1을 하면 010(2)

1111(15) >> 2는 0011(3)

​

비트연산자 기초 ^, ~

 

XOR연산자, ^

true ^ true = false, false ^ false = false 이며 나머지는 다 true를 반환한다.

같으면 싫어한다고 외워도 좋다.

0 ^ 0	0
0 ^ 1	1
1 ^ 0	1
1 ^ 1	0

1001(9)^ 1000(8)은 0001

1010(10) ^ 1000(8) 0010

​

1의 보수연산자이며 이는 해당 수의 모든 비트를 반전하는 연산자이다.

~value = -(value + 1)

~value + 1 = -value 

 

 

 

2.  백준 외판원 문제

https://youtu.be/XaXsJJh-Q5Y