비트 연산과 2의 보수: 고정 비트폭·마스크·Python 음수 표현

비트 연산과 2의 보수를 이해할 때 가장 먼저 정할 값은 bit width다. 1011은 4-bit signed two's complement라면 -5지만, unsigned라면 11이다. Python int는 고정 폭 정수가 아니므로 ~5를 4-bit 반전 결과처럼 해석해서도 안 된다.

비트 연산자는 무엇을 계산하나

5 = 0b0101, 3 = 0b0011을 4-bit로 나란히 놓으면 연산별 차이가 보인다.

연산	Python	결과	의미
AND	5 & 3	1 (0001)	둘 다 1인 bit만 1
OR	5 | 3	7 (0111)	하나라도 1이면 1
XOR	5 ^ 3	6 (0110)	서로 다르면 1
left shift	5 << 1	10 (1010)	bit를 왼쪽으로 이동
right shift	5 >> 1	2 (0010)	bit를 오른쪽으로 이동
NOT	~5	-6	Python의 무한 sign bit 모델에서 반전

Python integer bitwise 문서에 따르면 left shift x << n은 x * 2**n, right shift x >> n은 x // 2**n과 같다. 음수 right shift도 floor division semantics를 따르므로 -5 >> 1은 -3이다.

2의 보수는 왜 bit width가 필요한가

w-bit signed two's complement가 표현하는 범위는 다음과 같다.

-2^(w-1) <= x <= 2^(w-1) - 1

4-bit라면 -8부터 7까지다. 가장 왼쪽 bit의 place value를 -2^(w-1)로 읽고 나머지 bit는 일반 binary place value로 더할 수 있다.

1011₂ = -8 + 0 + 2 + 1 = -5

같은 결과를 “양수 bit를 모두 뒤집고 1을 더한다”는 규칙으로도 얻는다.

 5  = 0101
invert 1010
+ 1    1011  -> -5

이 과정에는 반드시 4-bit라는 경계가 있다. 폭을 8-bit로 바꾸면 -5는 11111011이다. Cornell CS 3410의 integer 표현 자료도 n-bit two's complement의 MSB가 -2^(n-1) 값을 갖는다고 설명한다.

encode와 decode를 분리해 구현한다

negative integer를 bit pattern으로 바꾸는 일과, bit pattern을 signed value로 읽는 일은 반대 방향의 연산이다. 두 함수를 분리하면 반환값이 “정수 값”인지 “unsigned pattern”인지 헷갈리지 않는다.

def encode_twos_complement(value: int, bits: int) -> int:
    if bits < 1:
        raise ValueError("bits는 1 이상이어야 합니다.")

    minimum = -(1 << (bits - 1))
    maximum = (1 << (bits - 1)) - 1
    if not minimum <= value <= maximum:
        raise OverflowError(f"{value}는 {bits}-bit signed 범위를 벗어납니다.")

    mask = (1 << bits) - 1
    return value & mask


def decode_twos_complement(pattern: int, bits: int) -> int:
    if bits < 1:
        raise ValueError("bits는 1 이상이어야 합니다.")
    if not 0 <= pattern < (1 << bits):
        raise OverflowError(f"pattern은 {bits} bits 안에 들어와야 합니다.")

    sign_bit = 1 << (bits - 1)
    return pattern - (1 << bits) if pattern & sign_bit else pattern


encoded = encode_twos_complement(-5, 8)
print(f"{encoded:08b}")                   # 11111011
print(decode_twos_complement(encoded, 8))  # -5

encoding 식 value & ((1 << bits) - 1)은 결국 value mod 2**bits에 해당하는 하위 bit pattern을 얻는다. 하지만 함수가 range check를 먼저 하는 이유는 8-bit signed에 들어가지 않는 값을 조용히 wrap하여 다른 수로 바꾸지 않기 위해서다. protocol이나 file format이 의도적으로 modulo wrapping을 요구한다면 별도 함수로 그 정책을 드러내는 편이 낫다.

Python에서 ~5가 10이 아닌 이유

고정 4-bit만 뒤집으면 0101 -> 1010, 즉 unsigned 10이 된다. 그러나 Python int는 arbitrary precision이며 bitwise 연산을 무한한 sign extension을 가진 two's complement처럼 계산한다.

~x == -x - 1
~5 == -6

정해진 폭 안에서만 반전하려면 mask를 적용한다.

bits = 4
mask = (1 << bits) - 1
inverted = (~5) & mask

print(f"{inverted:04b}")  # 1010
print(inverted)            # 10, unsigned pattern
print(decode_twos_complement(inverted, bits))  # -6

같은 1010이 unsigned로는 10, 4-bit signed로는 -6이다. bit string만 출력하고 signedness를 생략하면 해석이 달라진다.

shift와 overflow는 언어마다 같은가

Python integer는 필요에 따라 크기가 늘어나므로 1 << 1000도 fixed-width overflow를 일으키지 않는다. 반면 machine integer나 protocol field는 폭이 고정되어 상위 bit가 잘리거나 예외가 발생하거나, 언어 규칙에 따라 undefined behavior가 될 수 있다.

특히 다음을 language와 type별로 확인해야 한다.

• signed·unsigned 여부와 bit width
• overflow 때 wrap, trap, exception, undefined behavior 중 무엇인지
• negative value의 right shift 규칙
• byte order와 serialization의 signed option

Python에서도 byte로 직렬화할 때는 폭과 signedness가 다시 명시된다.

payload = (-5).to_bytes(length=1, byteorder="big", signed=True)
restored = int.from_bytes(payload, byteorder="big", signed=True)

print(payload.hex())  # fb
print(restored)       # -5

비트 문제를 풀 때 확인할 순서

1. bit width와 signedness를 먼저 적는다.
2. 표현 가능한 최소·최대값을 계산한다.
3. 값과 bit pattern을 별도 변수로 구분한다.
4. NOT이나 shift 뒤에는 필요한 mask를 적용한다.
5. overflow를 의도한 wrap인지 입력 오류인지 결정한다.
6. byte 변환에서는 byte order와 signed를 명시한다.

Python의 큰 정수 계산과 문자열 기반 접근의 차이는 무한히 큰 수의 사칙연산, bit pattern이 실제 CPU와 memory에서 처리되는 배경은 CPU와 메모리 기본 개념에서 이어서 볼 수 있다.

정리

2의 보수는 bit width가 정해져야 해석할 수 있다. w-bit signed 범위는 -2^(w-1)부터 2^(w-1)-1까지이며, negative value의 pattern은 하위 w bits로 encode한다. Python int는 arbitrary precision이므로 고정 폭 연산을 재현하려면 range, mask, signed decode를 코드에 명시해야 한다.

참고 자료

• Python: Bitwise Operations on Integer Types
• Python: int.to_bytes and int.from_bytes
• Cornell CS 3410: Numbers
• RISC-V Unprivileged ISA: Introduction