수의 비트 표현

수의 비트 표현

저자 Сергей Слотин
수정 2021년 8월 21일
모든 정수는 이진법으로 나타낼 수 있습니다: $$ \begin{aligned} 5_{10} &= 101_2 = 4 + 1 \\ 42_{10} &= 101010_2 = 32 + 8 + 2 \\ 256_{10} &= 100000000_2 = 2^8 \end{aligned} $$

회로 수준에서는 거의 모든 논리가 이진이므로, 컴퓨터에서 수를 저장할 때도 바로 이러한 표현이 사용됩니다. 각 정수 변수는 8(char), 16(short), 32(int) 또는 64(long long)비트 크기의 어떤 셀을 가리킵니다.

#엔디언

이러한 형식에서 유일하게 모호함이 생기는 부분은 비트의 저장 순서이며, 이를 엔디언이라고도 합니다. 아키텍처에 따라 이 순서는 다를 수 있습니다:

  • little-endian 방식에서는 하위 비트가 먼저 옵니다. 예를 들어, 수 $42_{10}$은 다음과 같이 저장됩니다: $010101$.
  • big-endian 형식으로 기록할 때는 상위 비트가 먼저 옵니다. 이 글의 앞부분에 나온 모든 예시는 big-endian 형식으로 표기되었습니다.

big-endian이 이해하기에 더 자연스럽지만(종이에 이진수를 쓸 때 보통 바로 이 방식으로 씁니다), 여러 가지 이유로 대부분의 현대 프로세서는 기본적으로 little endian을 사용합니다.

다시 말해, “$i$번째 비트"는 “$i$번째 하위 비트” 또는 “오른쪽에서 $i$번째 비트"를 의미하지만, 종이에 쓸 때는 아무것도 뒤집지 않고 이진수를 표준적인 방식으로 적습니다.

#비트 연산

산술 연산 외에도 숫자에는 비트 연산을 적용할 수 있으며, 비트 연산은 숫자를 단순히 비트의 나열로 해석합니다.

#시프트

수의 비트 표현은 왼쪽(x << y)이나 오른쪽(x >> y)으로 「시프트」할 수 있으며, 이는 2의 거듭제곱을 곱하거나 2의 거듭제곱으로 나눈 뒤 내림하는 것과 같습니다.

일반적인 곱셈과 나눗셈은 가장 빠른 연산이 아니지만, 모든 비트 시프트는 항상 정확히 한 클럭 사이클에 수행됩니다. 그 결과, 어떤 고정된 2의 거듭제곱으로 곱셈과 나눗셈을 하는 것은 항상 빠르게 동작합니다. 시프트를 명시적으로 사용하지 않더라도 컴파일러가 이와 같은 최적화를 수행할 가능성이 높습니다.

#비트 연산

&&, ||, ! 외에도 이들의 비트 버전인 &, |, ~가 있으며, 이들은 해당 논리 연산을 비트 시퀀스 전체에 적용합니다.

또한 이들 외에도 배타적 “또는”(XOR) 연산이 있으며, 이는 ^로 표기합니다.

예를 들면 다음과 같습니다.

  • $13$ & $7$ = $1101_2$ & $0111_2$ = $0101_2$ = $5$
  • $17$ | $10$ = $10001_2$ | $01010_2$ = $11011_2$ = $27$
  • $17$ ^ $9$ = $10001_2$ ^ $01001_2$ = $11000_2$ = $24$

모든 비트 연산 역시 데이터 타입과 관계없이 한 클럭 사이클에 수행됩니다. 하나의 레지스터에 들어가지 않는 큰 비트 시퀀스를 위해서는 비트셋이 있습니다.

#마스크

이진 수열은 어떤 고정된 집합의 부분집합에 대응시킬 수 있습니다. $i$번째 위치에 1이 있으면 $i$번째 원소가 집합에 포함된다는 뜻이고, 그렇지 않으면 포함되지 않는다는 뜻입니다.

따라서 비트 연산은 비트 마스크로 표현되는 집합에 대한 연산에 자주 사용됩니다. 예를 들어 완전 탐색이나 동적 계획법 문제에서 그렇습니다.

#수의 i번째 비트 추출하기

(x >> i) & 1 또는 x & (1 << i)입니다. 두 번째 경우 결과는 0 또는 $2^i$입니다.

이는 $i$번째 원소가 집합에 속하는지 확인할 때 자주 사용됩니다:

if ((num >> i) & 1)
    cout << "YES";
else
    cout << "NO";

비트 번호는 하위 비트부터 매기며 0부터 시작한다는 점을 다시 상기합시다.

#k개의 1로 이루어진 수 얻기

(1 << k) - 1입니다. $(2^k-1)$로도 알려져 있으며, 전체 집합의 마스크에 해당합니다.

#수의 모든 비트 반전

x = ~x

#집합에 i번째 원소 추가

x |= (1 << i)

#집합에서 $i$번째 원소 제거

x &= ~(1 << i)

#집합에 i번째 원소가 있으면 제거하기

x ^= (1 << i)

또한 이 원소가 없으면 추가합니다.

#부호 있는 정수

정수 변수는 부호 있는(signed) 변수와 부호 없는(unsigned) 변수의 두 가지 유형으로 나뉩니다.

합이 $2^{32}$를 넘는 두 unsigned int 변수를 더하면 오버플로가 발생합니다. 합을 정확하게 표현할 수 없으므로 그 대신 하위 32비트만 결과로 남습니다. 부호 없는 수에 대한 모든 연산은 말하자면 어떤 2의 거듭제곱을 법으로 하여 수행되는 셈입니다.

반면 부호 있는 타입은 음수일 수도 있는 값을 저장하는 데 필요합니다. 이를 위해서는 부호, 즉 수가 음수인지 아닌지를 저장하는 데 비트 하나를 할당해야 하며, 그 대가로 표현 가능한 수의 상한을 약간 희생하게 됩니다. 이제 표현 가능한 가장 큰 수는 $2^{32}-1$이 아니라 $2^{31}-1$입니다.

프로세서를 만드는 엔지니어들은 프로그래머보다 훨씬 더 게으릅니다. 이는 단순화하려는 욕구뿐 아니라 트랜지스터를 절약하려는 목적에서 비롯된 것입니다. 그래서 signed 타입에서 오버플로가 발생하면, 비트 표현상의 결과는 unsigned 수의 경우와 똑같은 방식으로 계산됩니다. unsigned 수가 동작하는 방식을 전혀 바꾸고 싶지 않다면, 음수의 표현은 수 $-x$가 큰 2의 거듭제곱에서 빼지는 것처럼 되어야 합니다:

$$ \begin{aligned} -x = 2^{32} - x \end{aligned} $$

몇 가지 결과는 다음과 같습니다:

  • 모든 음이 아닌 수는 이전과 정확히 같은 방식으로 표기됩니다.
  • 모든 음수는 최상위 비트가 1입니다.
  • $2^{31}-1$에 1을 더하면 결과는 $-2^{31}$이 되며, 이는 10000000으로 표현됩니다(설명의 편의를 위해 8비트로 표기하겠지만, int에는 32비트가 있습니다).
  • 양수 x의 이진 표현을 알면 -x의 표현은 ~x + 1로 구할 수 있습니다.
  • -1은 ~1 + 1 = 11111110 + 00000001 = 11111111로 표기됩니다.
  • -42는 ~42 + 1 = 11010101 + 00000001 = 11010110으로 표기합니다.
  • -1 = 11111111 다음에는 0 = -1 + 1 = 11111111 + 00000001 = 00000000이 옵니다.

연습 문제. 양수와 음수 중 어느 쪽이 더 많습니까?

주의. C/C++ 표준에는 부호 있는 변수의 오버플로가 undefined behavior를 일으킨다고 명시되어 있으므로, 실제로는 대부분 그렇게 동작하더라도 위에서 설명한 오버플로 동작에 의존해서는 안 됩니다.

#128비트 정수

프로세서에는 크기가 64보다 큰 범용 레지스터가 없지만, 곱셈과 몇몇 관련 명령어는 연속된 두 레지스터를 하나의 큰 레지스터처럼 사용할 수 있습니다. 이를 통해 두 64비트 수를 빠르게 곱하여 하위 비트와 상위 비트로 나뉜 128비트 결과를 얻을 수 있습니다.

이는 상당히 특수한 연산이므로, 프로그래밍 언어에는 128비트 변수에 대한 완전한 지원이 없습니다. 하지만 C++에는 일종의 「임시방편」인 __int128_t 타입이 있는데, 이 타입은 사실상 두 개의 64비트 레지스터 쌍을 감싸기만 하며 이들에 대한 산술 연산을 지원합니다.

__int128_t x = 1;
int64_t hi = x >> 64; // получить верхние 64 бит
int64_t lo = (int64_t) x; // получить нижние 64 бит

이 타입의 기본 산술 연산은 약간 더 느리고, 직접 출력할 수 없으며, 나눗셈을 비롯한 복잡한 연산은 별도의 라이브러리를 호출하기 때문에 매우 오래 걸리지만, 어떤 상황에서는 매우 유용합니다.