[실전 압축 알고리즘] - 비트 연산

본 게시글은 실전 기술을 정리해 놓은 '실전 압축' 입니다. 

---

 

Bitwise Operators

연산자	예시	계산	쉬프트 과정 (2진법)	결과	활용
<< (Left Shift)	1<<1 5<<2	1 * 2^1 5 * 2^2	00001 -> 00010 00101 -> 10100	1 20	2의 n승
>> (Right Shift)	2>>1 5>>2 12 >> 2	2 * 2^-1 5 * 2^-2 12 * 2^-3	00010 -> 00001 00101 -> 00001  01100 -> 00011	1 1 3	2의 -n승
& (AND)	2 & 1 3 & 1		10 & 01 -> 00 11 & 01 -> 01	0 1	짝수 = 0 홀수 = 1
| (OR)	1 | 1 2 | 1 3 | 1		01 | 01 -> 01 10 | 01 -> 11 11 | 01 -> 11	1 3 3	방문 check
^ (XOR)	5 ^ 6 1 ^ 1 2 ^ 1		00101 ^ 00110 -> 00011 01 ^ 01 -> 00 10 ^ 01 -> 11	3 0 3	토글
~ (NOT)	~162		1010 0010 -> 0101 1101	93	비트 반전

 

조심해야 되는 부분 !!!

 

부호의 유무에 따라 쉬프트 연산의 차이가 있음

음수의 경우 첫 번째 비트가 1이다.

 

 

(signed) char

메모리 크기	1Byte ( = 8Bit )
비트 표현	0000 0000 ~ 1111 1111 까지 표현 가능 (-127 ~ 127) 첫 번째 비트를 부호 비트로 사용한다.
양수	0000 0001 ~ 0111 1111 ( 1 ~ 127 )
음수	1000 0000 되는 순간 음수가 되므로 -128, 128이 1000 0000 1000 0000 ~ 1111 1111 ( -128 ~ -1 ) -1 : 1111 1111 -2 : 1111 1110 ... -128 : 1000 0000 2의 보수를 취하고 -1을 곱하면 10진법으로 변환 가능
0	0은 0000 0000 이다. -256, 256 또한 0000 0000 으로 찍힌다. 추가로 -128은 1000 0000 으로 출력 됨 -129은 0111 1111
-125 >> 5	1000 0011 -> 1111 1100 (-125 -> -4) 오른쪽으로 밀어버릴 때 마다 1로 채워짐
113 << 2	0111 0001 -> 1100 0100 (113 -> -60)

 

 

Bitwise Assignment Operators

Symbol	Form
<<=	x <<= y
>>=	x >>= y
!=	x != y
&=	x &= y
^=	x ^= y

 

 

기타

연산자	활용	문제
&, | (AND, OR)	그래프 문제에서 방문 확인, 표시 방문됨 : 1, 방문 안됨 : 0 & 연산으로 방문을 확인  |   연산으로 방문을 저장	ex) 외판원 순회  https://www.acmicpc.net/problem/2098