비트연산과 정수정리

1. 기본적인 비트연산

a. bit 논리연산

&(and) 두 bit 다 1이어야 1임 ex) 01101001 & 01010101 = 01000001

| (or) 두 bit 중 하나라도 1이면 1임 ex) 01101001 | 01010101 = 01111101

^ (xor) 두 bit가 다르면 1임 ex) 01101001 ^ 01010101 = 00111100

~ (not) 1은 0으로 0은 1로 바꿈 ~ 01101001 = 10010110

 

b. shift연산

<< (left shift) 모든 bit를 왼쪽으로 한칸씩 밈, 대부분의 상황에서 *2가 되지만, overflow는 주의해야함.

 

>> (right shift) 모든 bit를 오른쪽으로 한칸씩 밈. 버리는 나누기 2를 사용한다고 생각하면됨. 다만 여기서 맨 왼쪽 부호bit부분에 의한 문제가 생기는데 이 부분은 나중에 설명하도록 하곘음. 

 

2. 정수의 저장방식

a. 음수의 저장방식

2의 보수 방식으로, 특정 양수x가 있다고 했을떄, (~x+1)가 음수가 된다. (이건 음수를 양수로 만들때도 동일하다)

 

여기서 특정 음수의 숫자를 빠르게 분석하는 것은 맨 왼쪽 bit (MSB 부호 결정bit 이게 1이면 무조건 음수이다) 가 -최대값(int의 경우 -2^31)이라 생각하고, 나머지는 양수와 똑같이 생각하면 비교적 빠르게 분석할 수 있다. 

 

b. unsigned 변수

int등의 자료형앞에 unsigned를 붙이거나, 일반적인 상수뒤에 U를 붙일경우, unsigned변수가 된다. 이때는 맨 왼쪽 bit (MSB 부호 결정 bit)도 그냥 일반적인 다른 bit와 같은 기능을하고, 표현 가능한 양수 범위가 2배로 늘어난다. 

 

unsigned와 signed 변환은 signed의 양수 범위까지는 완전히 같지만, (int의 경우 2^31-1) unsigned의 그보다 큰 양수에 대해서는 signed로 변환할 경우 2^비트개수를 빼야한다. (int의 경우 -2^32)

 

생각할 때 많이 실수하는 부분은, signed를 unsigned와 비교연산할경우 (부등호, ==등) signed변수를 unsigned변수처럼 생각하고 비교한다. ex) -12>1U -> true -12가 unsigned로 바뀌면서 상당히 큰 양수로 바뀌기 때문.

 

c. rightshift

아까 right shift의 맨 왼쪽 부분에 대한 설명이 필요한데, left shift와 달리 0을 가져오게 되면 음수였던 숫자가 양수로 바뀌는 문제가 발생할 수 있다. (MSB 이슈) 

 

따라서 두가지의 shift가 존재하는데 

logical shift : 그냥 무조건 0을 박음. Unsigned 변수를 right shift할경우 사용됨

 

Arithmetic shift : 원래 있던 MSB를 따라서  MSB를 바꿈. signed 변수를 right shift할 경우 사용됨.

 

d. 곱하기와 나누기의 원리

일반적으로 곱하기와 나누기는 left shift와 right shift를 사용하는데 (나누기는 정수형 나누기)

left shift 1번이 *2를 의미하고, right shift한번이 /2를 의미하는 것을 이용하면 자유롭게 계산이 가능하다. 

ex) *7 = *4+*2+*1 과 같은 방식으로 구현 가능.