[Python] 파이썬에서 2의 보수 체계 적용기

---

01. 문제점

파이썬에서 정수의 저장

02. 해결방법

비트 마스크(Bit Mask)

파이썬 내장 메소드 to_bytes, from_bytes

 

 

---

01. 문제점

 

 컴퓨터 과학 총론을 공부하면서 컴퓨터가 2의 보수 체계를 어떻게 적용하는지 공부했다(여기를 참조) . 이를 파이썬에서 직접 적용시켜 보기로 했는데 난관에 부딪혔다. 파이썬에서 정수를 표현하는 bit 수는 할당된 메모리 크기에 의해 제한되는 것이 아니라 정수의 크기에 따라 유동적으로 변화할 수 있었다. 즉 저장할 메모리의 크기를 직접 할당해 줘야 하는 C언어나 여타 저수준 프로그래밍 언어와 달리, 파이썬에서는 int형를 사용할 때 overflow나 memory leak 같은 memory 관련 문제에 신경 끄고 온전히 프로그래밍에만 집중할 수 있도록 해주고 있었다.

 

 저장할 정수에 할당된 메모리의 크기가 1byte, 2byte 딱 지정되어 있어야 2의 보수 체계를 이용해 msd(most significant digit)를 sign bit로 사용해 양수와 음수를  서로 변환해 볼 수 있는데 파이썬에서는 그럴 수가 없었다. 구체적으로 아래의 코드를 보자.

 

# q를 입력하기 전까지 반복
while True:
    # 정수 입력
    num = input("정수를 입력해주세요 (종료는 q를 입력): ")

    # q를 입력하면 함수 종료
    if num == "q":
        break

    binary_number = bin(int(num))  # 입력받은 문자열 num을 정수형으로 변환한 뒤 이진수로 변환
    print(binary_number)

input: 5
>> 0b101

input: 20
>> 0b10100

input: -30
>> -0b11110

 

 보다시피 정수값 5와 20을 입력하고 이진수로 변환해 출력하면 해당하는 이진수의 msd(most significant digit) 이상의 비트는 자동적으로 생략시키고 출력된다. 또한 -30의 경우에는 음수를 표현하기 위해 2의 보수가 적용되는 것이 아니라 양수 30에 -부호를 붙인 채로 출력된다. 그래서 단순히 정수를 입력받고 이진수로 변환한 뒤 0은 1로, 1은 0으로 전부 바꿔 주고 +1 한다고 해서 부호가 바뀐 정수값을 얻을 수 없었고 해당 이진수의 양수값 밖에 얻을 수 없었다. 

 

🎃 참고

요약

 

 정수 저장에 대해 C언어로 프로그래밍된 파이썬의 동작 방식이 궁금해서 관련 자료를 찾아봤다. 참조

 

  C언어 까막눈이라 python의 대표적인 인터프리터인 cpython 코드의 해당 부분을 아무리 이해해 보려고 해도 이해할 수 없었기 때문에 잘 정리된 블로그와 기타 여러 글을 참고했다. C/C++에서 정수는 int형식으로 저장하고 int의 크기는 64bit OS 기준으로 4bytes이다. 하지만 파이썬에서는 그보다 7배나 큰 28 bytes를 차지한다. 이유는 정수값 자체를 표현하는 데이터 뿐만 아니라 int객체에 대한 Metadata도 함께 포함하고 있기 때문이다. 

 

 cpython 코드에 따르면 파이썬의 모든 정수는 PyLongObject 객체로 구현되는데, 해당 부분이 구현된 pytypedefs.h를 찾아가보면 _longobject 구조체(struct)를 PyLongObject로 재정의했다. 여기서 다시 _longobject가 정의되어 있는 longintrepr.h를 찾아가니 각각 PyObject_HEAD와 _PyLongValue로 구성되어 있었다. 

 

 PyObject_HEAD는 PyObject타입이고 PyObject타입은 다시 파이썬의 모든 객체를 구성하는 _object 구조체(/Include/object.h)를 재정의한 것이다. _object의 구조는 각각 다음으로 구성되어 있다.

 

 

1. _PyObject_HEAD_EXTRA - 디버깅에 사용

2. ob_refcnt - Python이 자동으로 메모리 할당 및 할당 해제를 처리하는 GC(Garbage Colletor)의 레퍼런스 카운팅 기법에 사용되는 참조 횟수 (8 bytes)

3. *ob_type - 객체의 타입 정보를 인코딩해 주소에 저장(포인터) (64bit OS기준 8bytes)

 

 

 따라서 PyObject_HEAD는 ob_refcnt (8bytes) + *ob_type (8bytes) = 16bytes로 구성되어 있는 것을 확인할 수 있다.

 

다음으로 _PyLongValue(/Include/cpython/longintrepr.h)는 다음으로 구성되어 있다.

 

 

1. ob_size - 아래 ob_digit 배열의 크기(digit의 개수)를 저장, 부호도 여기에 저장 (long long type, 8 bytes)

2. ob_digit[1] - digit 배열 1개를 할당, array로 관리되는 실제 int값 (uint32_t, 4 bytes)

 

 

 따라서 _PyLongValue는 ob_digit (8bytes) + ob_digit[1] (4bytes) = 12bytes로 구성되어 있는 것을 확인할 수 있다.

 

 이제 각각의 값을 더해보자. 실제 int값인 ob_digit[1]에 할당된 4bytes에 더해서 Metadata에 해당하는 ob_refcnt + *ob_type + ob_size가 24bytes를 차지해 파이썬의 int객체는 28bytes(32bit OS의 경우 24bytes)의 메모리를 할당받는 것을 알 수 있다. 그렇다면 왜 굳이 4bytes로 표현될 걸 28bytes까지 늘려서 메모리 낭비를 하는지 궁금해진다.

 

 결론적으로 overflow를 막고 효율적인 메모리 할당 및 해제를 하기 위해서다. 파이썬은 2^30을 기준으로 더 큰 값이 할당됐을 때 overflow가 발생하지 않고 array의 크기가 가변적으로 증가한다. 즉, 28bytes로 표현할 수 있는 최대값 2^30 - 1 = 1073741823 이상인 2^30 = 1073741824가 주어지면 ob_size에 +1이 되고 ob_digit 배열에 추가적인 값을 할당할 수 있다. 이때 원래 배열에 1073741823, 새로운 배열에 1이란 값이 할당되는 게 아니라 A * 2^(30*0) + B * 2^(30*1) + ... 이런 식의 파이썬 자체 알고리즘으로 각 배열에 분배되어 할당된다.

 

 각설하고 1073741824란 값을 저장할 때 파이썬은 원래 int 객체의 크기인 28bytes에서 4bytes가 추가로 늘어난 32bytes를 가변적으로 할당한다.

 

 

---

02. 해결방법

 

비트 마스크(Bit Mask)

기본적으로 모든 자료를 이진수를 표현하는 컴퓨터의 특성을 이용해서 이진수 표현을 자료구조로 사용하는 기법이다. 더 빠른 수행 시간, 더 간결한 코드, 더 적은 메모리로 같은 효과를 얻을 수 있다.

 

# 1
print(bin(10))
print(bin(10 & 0b1001))

# 2
print(bin(-5))
print(bin(-5 & 0b1111))

# 1
0b1010
0b1000

# 2
-0b101
0b1011

 # 1

정수 10을 bin()함수를 이용해 이진수로 변환하면 0b1010이 된다. 그리고 &는 bit 단위의 AND연산을 수행하므로 각 bit에서 AND가 참인 값만 1로 반환된다. 즉 bin(10 & 0b1001)은 0b1000을 출력하게 된다. 실제로 10 & 0b1001을 출력하면 8이 출력될 것이다.

 

# 2

비트 마스킹을 이용해 0b1111로 목표하는 값을 bit단위 AND연산을 수행하면 2의 보수 체계로 된 -5의 이진수가 얻어진다.

 

 이를 일반화한 코드는 다음과 같다.

 

def bindigits(n, bits):
    s = bin(n & int("1"*bits, 2))[2:]
    return ("{0:0>%s}" % (bits)).format(s)
    
print(bindigits(-30, 8))
print(bindigits(124, 8))

11100010
01111100

 n은 변환하고자 하는 정수, bits는 할당된 bit 길이다. n을 bits길이만큼의 1에 해당하는 값으로 비트 마스킹한 뒤 이진수로 변환한 값을 s에 저장하고 return에서 bits의 길이 만큼 s를 출력하고 부족한 부분은 0으로 채운다. 실제로 124와 같은 양수의 경우 위 코드의 n & int(...)부분에서 두 파이썬 정수 객체끼리 bit 단위 AND연산을 하므로 자릿수가 8개가 되지 않는다. 따라서 앞쪽의 부족한 자릿수에 0을 채운다.

 

 

내장메소드

 파이썬 3.2버전부터 정수값에 해당하는 바이트 배열을 반환하는 to_bytes 메소드와 바이트 배열로부터 정수값을 반환하는 from_bytes 메소드가 추가되었다. signed 파라미터를 통해 2의 보수가 적용되는지 안 되는지 결정할 수 있다.

def twos(val_str, bytes):
    import sys
    val = int(val_str, 2)
    b = val.to_bytes(bytes, byteorder=sys.byteorder, signed=False)
    return int.from_bytes(b, byteorder=sys.byteorder, signed=True)


print(twos("11011100", 1))

-36

변환하고자 하는 이진수를 정수형으로 변환하고 to_bytes를 이용해 바이트 객체로 변환하고 다시 바이트 객체 b로부터 부호가 있는 int객체로 변환한다.