32비트 워드단위의 프로세서를 위주로 설명하면

각 자리의 비트를 오른쪽부터 b0, b1, b2, ...., b31이라는 미지수로 대응시켜 보자. 물론 모든 i에 대해 bi는 0이나 1을 갖겠져.

그럼 1 워드는 다음과 같은 나열이 되겠져.
b31 b30 b29 b28 b27 ........ b3 b2 b1 b0

너님들이 아는 2진법->10진법 변환은 어떻게 하지? 각 자리마다 2의 n승을 곱해서 다 더하면 되지.
그럼 위의 1워드 표현은 다음과 같이 A라는 10진법의 수가 되겠져.

A = (2^31)*b31 + (2^30)*b30 + (2^29)*b29 + ... + (2^3)*b3 + (2^2)*b2 + (2^1)*b1 + (2^0)*b0

자 여기서 <<1만큼 우측으로 시프트연산을 했다고 생각해 보자.

b30 b29 b28 b27 ........ b3 b2 b1 b0  0

시프트했으니까 제일 좌측이었던 b31은 없어지고 제일 우측 b0이 있던 자리는 0으로 채워질 거예여.
그럼 표현식이 어떻게 변할까여?

B = (2^31)*b30 + (2^30)*b29 ... + (2^5)*b4 + (2^4)*b3 + (2^3)*b2 + (2^2)*b1 + (2^1)*b0 + (2^0)*0
이 되겠지?

b31은 오버플로우 나서 없어진다는건 당연히 알거야. 32비트짜리 컴퓨터잖아.
왼쪽 시프트하면 제일 왼쪽 비트는 없어지고 제일 오른쪽 비트는 0으로 채워지지.

(아 물론 언사인드냐 사인드냐 사용하는 시프터가 뭐냐에 따라서 존니 다르긴 합니다.)

시프트한 연산 B가 2A와 같다는 걸 증명하기 위해 A에 2를 양변에 곱해보자.

2A = 2((2^31)*b31 + (2^30)*b30 + (2^29)*b29 + ... + (2^3)*b3 + (2^2)*b2 + (2^1)*b1 + (2^0)*b0)
    = 2((2^31)*b31 + (2^30)*b30 + (2^29)*b29 + ... + (2^3)*b3 + (2^2)*b2 + (2^1)*b1 + (2^0)*b0)
    = (2^32)*b31 + (2^31)*b30 + (2^30)*b29 + ... + (2^4)*b3 + (2^3)*b2 + (2^2)*b1 + (2^1)*b0

근데 32비트 컴퓨터에서는 0부터 2^32-1까지의 숫자밖에 표현 못한다는건 알져?
이 현상을 두고 오버플로우라고 이야기하는데 정확히 말하면 오버플로우가 아니예여. 나눗셈 연산이져.
이건 한마디로 그보다 큰 숫자가 있으면 나누기 (2^32)를 해서 나머지만 표현한다는걸 말함
그럼 젤 앞쪽의 (2^32)*b31은 2^32의 배수니까 나누기 연산하면 절대 나머지가 안되겠져? 무조건 2^32로 나눠지니까여.
물론 그보다 더 큰 자릿수도 마찬가지예여. 1000000이 10으로 나눠진다는 말하고 똑같아여. 물론 여기선 (2^(n+1)) % (2^n)으로 말해야 되지만.
따라서 2A는 컴퓨터에서 이렇게 변환되여.

2A = (2^31)*b30 + (2^30)*b29 + ... + (2^4)*b3 + (2^3)*b2 + (2^2)*b1 + (2^1)*b0 + (2^0)*0

근데 이 식 어디서 많이 보던거져?

B = (2^31)*b30 + (2^30)*b29 + ... + (2^4)*b3 + (2^3)*b2 + (2^2)*b1 + (2^1)*b0 + (2^0)*0

따라서 
 2A = B
따라서 좌측 시프트는 정확히 다음과 같이 정의할 수 있어여.
A << 1 == (A*2) % (2^32)

이걸 연장하면
A << n == (A*n) % (2^32)
라고 생각할 수 있겠져.

우측 시프트는 반대로 2를 나눠서 몫을 가진다고 생각하면 되여. 나머지는? 걍 버려지는거져.


참고로 32비트 워드 컴퓨터의 int형으로 가지고 하는 모든 연산 (사칙연산, exp 등등)은
기본적으로 결과물을 2^32로 나눈 나머지를 갖고오는 거예여.


오늘의 산수공부 끝.