양의 정수를 비트로 표현하는 방법, 이진법

김재만·2022년 2월 12일

CS

목록 보기

2/13

수를 표현하는 아이디어

우리는 일상에서 수를 언어로 표현해야할 경우가 많다. 일반적으로는 열 손가락으로부터 비롯된 표현법을 활용한다. 하지만, 컴퓨터는 한 손에 한 손가락이 있다. 전기가 흐르냐, 먀나라는 것을 판단하면서 수를 세기 때문이다. 점차 더 많은 수를 표현하기 위한 아이디어를 찾아 떠나야하지만, 일단은 전기가 흐르냐와 마냐로 모든 양의 정수를 표현해보자.

비트를 표현하는 가장 직관적인 방법인 0과 1을 가지고 모든 양의 정수를 표현해보자. 0은 실제 0을 의미하고, 1은 실제 정수 1으로 해석하자.

bit(0) == 0
bit(1) == 1

그러면 2는 도저히 하나의 비트로만은 표현하기 어려울 것이다. 0을 2로 해석하거나, 1을 2로 해석하거나 어쨌든 한 가지의 해석을 포기해야하기 때문이다. 따라서 비트 하나를 더 불러와서 2를 표현해보자.

00과 01과 10과 11의 네 가지 표현을 할 수 있을것이다. 우리가 만약 0은 0, 1은 1로 해석하고 00부터는 2를 가리키려고 한다면, 수를 표현하는 데이터의 크기가 유동적이게 된다. 또한 연속적으로 데이터를 전송하려고 할 때, 해당 신호를 끊어서 보내야하는 불편함이 있다. 그러한 이유로 표현하고자 하는 모든 자릿수는 비트 수를 맞춰주기로 하자. 그러면 다시 돌아가서 가장 직관적으로 0을 모든 전기신호가 꺼져있는 00으로, 00에서 하나의 전기신호만 더해진 01을 가지고 1을 표현하자. 해당 01은 10으로 치환될 수 있다. 어쨌든 왼쪽부터 신호를 추가하거나, 오른쪽부터 추가하거나 일정한 규칙만 따르면 된다.

다음의 2는 어떻게 표현할까. 가장 직관적인 방식은 그대로 전기 신호를 하나 더 추가하는 방법이다. 그러면 2는 11이 될 것이다.

비트의 개수가 3개가 된다면, 0은 000, 1은 001, 2는 011, 3은 111으로 표현될 것이다. 그러면 n이라는 수를 표현하기 위해서는 n개의 비트가 필요한 표현방법인 것이다. 이는 우리가 손가락으로 수를 세는 방식과 매우 유사하다. 이러한 방식으로는 최소한 천문학을 컴퓨터로 다룰 수는 없을 거라는 것이 느껴진다. 정수를 전기신호로 표현하는 가장 비효율적인 방식인 셈이다. 왜냐하면 실질적으로 기호의 순서라는 언어적 표현방법이 반영되지 않은 방식이기 때문이다. 그러면 순서가 포함된 표현방식과 효율을 생각해보자.

이진법

다시 비트 두 개를 가지고 수를 표현해보자. 우리는 00으로 0을, 01로 1을 표현하기로 했다. 그리고 01이나 10이나 일정한 순서만 지킨다면 01이나 10이나 상관 없다는 표현을 했다. 사실 이 얘기는 우리가 전기 신호를 오른쪽부터 추가하기로 했다면, 10은 자연스럽지 않은 표기가 된다. 10은 1이 아닌 다른 무언가를 나타낼 수 있다는 것이다. 때문에 각 자릿수가 의미하는 바가 정해져야 효과적으로 해석할 수 있다. 또 하나, 기존에 2를 가리키던 11이라는 표기까지, 비트 두 개를 가지고 네 가지 수를 표현할 수 있다. 순서대로 0을 포함하여 모든 양의 정수를 표현하려고 한다면 0, 1, 2, 3을 표현하는 것이 가장 직관적일 것이며, 가장 작은 0을 00으로 가장 큰 3을 11로 표현하는 것이 직관적이다. 01은 1을 가리키기로 하였으니 10은 2를 가리키도록 생각해보자.

bit(00) = 0
bit(01) = 1
bit(10) = 2
bit(11) = 3

이렇게 수를 표기하면 가장 오른쪽(뒤) 자리는 20을 더할지 말지를, 왼쪽 자리는 21을 더할 지 말지를 표시하는 형태가 된다.

bit(00) = 0 x 21 + 0 x 20 = 0 + 0 = 0
bit(01) = 0 x 21 + 1 x 20 = 0 + 1 = 1
bit(10) = 1 x 21 + 0 x 20 = 2 + 0 = 2
bit(11) = 1 x 21 + 1 x 20 = 2 + 1 = 3

해당 방법은 n번째 비트를 늘려갈 때마다 2n-1을 더할지 말지 판단하는 자릿수로 활용한다. n-1번째 비트로는 2n-2 + 2n-3 + ... + 21 + 20 까지 표현할 수 있고, 이는 등비수열의 합이므로 2n-1 - 1까지 표현할 수 있다. 따라서 이진법을 활용하면 비트로 모든 양의정수와 0을 표기할 수 있다.

비트연산과 2진수 덧셈

비트는 앞서 얘기한 것 처럼 전기가 흐르냐, 마냐라는 것을 저장하는 것으로 0과 1은 단순히 기호에 불과하다. 1을 표시하는 비트 두 개를 더한다고 해서 2를 표현할 방법은 없다. 01과 01을 더해서 10을 표기할 수 있는 규칙이 필요한 것이다. 때문에 덧셈을 표현하기 위해 비트간의 관계를 비교하여 원하는 값을 도출하는 과정을 설계해야한다.

비트연산의 종류

비트연산은 현재 가지고 있는 비트에 표현된 값을 바탕으로 새로운 비트의 저장값을 도출하는 연산을 의미한다. 이는 연산의 종류에 따라 하나의 비트를 대상으로 할 수도 있고, 다수의 비트를 비교하여 새로운 비트를 반환하기도 한다.

NOT연산 : 기존 비트가 1을 가리키고 있으면 0을, 0을 가리키고 있으면 1을 반환하는 연산

bit(0) Not => bit(1)
bit(1) Not => bit(0)

AND연산 : 두 비트의 저장값을 비교하여 둘 다 1을 나타내고 있으면 1을, 하나라도 0을 나타내면 0을 반환하는 연산

bit(0) AND bit(0) => bit(0)
bit(0) AND bit(1) => bit(0)
bit(1) AND bit(0) => bit(0)
bit(1) AND bit(1) => bit(1)

OR연산 : 두 비트의 저장값을 비교하여 둘 중 하나라도 1을 나타내고 있으면 1을, 둘 다 0을 나타내면 0을 반환하는 연산.

bit(0) OR bit(0) => bit(0)
bit(0) OR bit(1) => bit(1)
bit(1) OR bit(0) => bit(1)
bit(1) OR bit(1) => bit(1)

XOR연산 : 두 비트의 저장값을 비교하여 둘 중 하나만 1을 나타내고 있을 때 1을, 둘 다 0 혹은 1을 나타내면 0을 반환하는 연산.

bit(0) XOR bit(0) => bit(0)
bit(0) XOR bit(1) => bit(1)
bit(1) XOR bit(0) => bit(1)
bit(1) XOR bit(1) => bit(0)

2진수의 덧셈

위의 연산을 바탕으로 어떻게 2진수의 덧셈을 구현할 수 있을까? 일단, 각 수를 세 개의 비트로 표현하여 0과 0의 덧셈부터 진행해보자.

000 + 000 = 000

우리가 원하는 결과는 위와 같다. 0과 0을 연산하여 0이 도출되는 세 개의 연산을 각 자릿수에 대해서 진행한 형태다. 사실 NOT 연산을 제외하고는 두 개의 비트를 비교하는 세 연산은 0과 0에 대해서 진행한 결과값이 모두 0이라 어느 연산으로 진행하더라도 000이 도출된다. 그러면 0과 1의 덧셈은 어떨까?

000 + 001 = 001

20 자릿수가 0과 1에 대해 연산을 진행한 결과 1을 도출하고 있다. AND연산의 경우 0과 1을 대상으로 비트연산을 하면 0이 반환되므로, 같은 자릿수를 비교할 때는 AND연산으론 해결되지 않음을 확인했다. 다음은 1과 1의 덧셈을 확인해보자

001 + 001 = 010

20 자릿수의 결과와 21 자릿수의 결과를 복합적으로 생각해야 한다. 하지만 21의 자리는 0과 0의 연산이므로, 사실은 20자릿수 연산의 결과물로 20자리에는 0이 21자리에는 1이 반환되었음을 알 수 있다.

20자리수는 1과 1의 연산으로 0이 반환되려면 오직 XOR연산으로만 가능하다. 다른 복잡한 어떤 연산을 가지고 오지 않았다면, 같은 자릿수의 값을 도출하는 방법은 XOR연산일 것이다. 하지만 1과 1을 연산하여 값을 단순히 0으로 바꿔주면, 우리가 원하는 연산이 아니므로, 해당 연산에 앞서 한 가지 연산이 더 필요하다. 1과 1을 비교하여 바로 옆의 비트로 1을 추가하는 형태의 연산이다. 때문에 이는 0과 1일 때는 작동하면 안 되는 연산이므로 AND연산으로 진행할 수 있다.