Pythhon3의 2의 부호화와 ~ 연산자 (비트 반전)

LeetCode 371 Sum of Two Integers를 해결하기 위해 파이썬 3의 음정수의 비트 표시와 ~연산자의 연산 결과와 2의 보수의 관계를 이해하기 어려워 정리했다.

2의 보너스

부호화(기수의 부호화)는 원시 숫자를 더할 때 수위가 상승하는'최소'수를 가리킨다.
10진수의 경우 10의 부호는 6에 비해 4, 66이 34이다.
2진법의 경우 2의 부호는 1, 110에 비해 10이다.
또 2의 부호화는 2진법으로 음수를 표시할 때 사용하는 방법이다.시작 비트(왼쪽)가 "1"인 경우 음수를 나타냅니다.
이진수에 대해 한 자리 한 자리를 반전시키고 1을 더하면 원시수를 더할 때 자릿수를 늘리는 '최소' 수를 계산할 수 있다.4자리 이진수의 경우 0100(10진수 4)의 2의 보충수 반전위가 1011 증가하고, 1을 더하면 1100(10진수 -4)이 된다.
보수표현은 마이너스를 사용하지 않아도 된다. 즉, 덧셈으로 뺄셈을 나타낼 수 있다.
2의 보너스도 다음과 같이 계산할 수 있다.보수는 원시수를 더할 때 자릿수를 늘리는'최소'의 수량이기 때문에 4위의 보수를 고려한 상황에서 자릿수를 올린 결과의 최소치인 2^4(이진법 표시에서 10000)와의 차이를 구하면 2의 보수가 된다.
10000 - 0100 = 1100
반대로 2의 부호를 원시수와 더하면
0100 + 1100 = 10000
결과 10000의 4위가 넘쳐나는 5위의 1위에서 0000으로 바뀌었다.
십진법으로 계산하다
4 + (-4) = 0
... 과 같다.
예: 7-4 = 3
2진수로 보통 빼기
0111 - 0100 = 0011
하면, 만약, 만약...
0111 + 1100 = 10011
이 결과의 4위가 넘쳐흐르는 앞머리의 1을 취하여 0011이 되고 10진법은 3이 된다.
아래와 같이 공식의 변형은 이해하기 쉽다.
0111 + 1100 = 10011
여기, - 4 의 2 의 보충 표시 1100 원래 1100 = 1000-0100
0111 + (10000 - 0100) = 10011
0111 + (10000 - 0100) - 10000 = 10011 - 10000
0111 - 0100 = 0011
5비트 중 1을 뽑는 것은 양쪽에 10000을 넣었기 때문에 양쪽에서 10000을 뺀다고 할 수 있다.
다음 표는 4자리 이진수, 기호가 있는 정수 및 기호가 없는 정수의 표입니다.
이진수
십진수
십진수
4비트
기호가 있는 정수
기호 없는 정수
0000
0
0
0001
1
1
0010
2
2
0011
3
3
0100
4
4
0101
5
5
0110
6
6
0111
7
7
1000
-8
8
1001
-7
9
1010
-6
10
1011
-5
11
1100
-4
12
1101
-3
13
1110
-2
14
1111
-1
15

~ 연산자(비트 반전)

~ 연산자(비트 반전)는 정수의 각 비트를 반전시킨다.예를 들어 위 표에 기호가 있는 정수는 4(0100)의 비트가 -5(1011)로 반전됩니다.
파이thhon3에서 ~산자로 반전할 때 조작수가 정수일 경우 값의 시작은 무한 개수 비트'0'(...00000010)[1]로 채워진다고 생각하기 때문에 반전된 결과의 값의 시작은 모두 반전된 무한 개수 비트'1'으로 채워진 값(...111111111)으로 간주된다.연산 결과 부호 위치를'1'의 음수 -5 출력으로 한다.

print(~4)
#　-5

또한 비트 반전 결과는 원시 수량의 1의 부호화(감기수의 부호화)와 같다.1의 보너스는 원시수를 더해서 자릿수 상승을 일으키지 않는 최대 수량이다.4위로 자릿수 상승을 하지 않기 위해 원수의 여러분 수가 1이면 0, 0이면 1로 반전하기 때문에 결과는 비트 반전과 같다.
0100 + 1011 = 1111
이 경우 1011보다 1이 많으면 자릿수가 10000으로 올라가기 때문에 0100을 더하면 자릿수 상승을 일으키지 않는 최대 수는 1011이다.또 1011보다 1이 많은 1100은 1위 상승의 최소 수이기 때문에 0100의 2 보충수다.
이렇게 하면 1의 보너스는 2의 보너스보다 1이 적다.따라서 원시값을 x로 설정하면 x의 2의 보수는 -x이기 때문에 1의 보수는 1보다 적은 -x-1이다x와 x의 1의 부호가 같기 때문에 ~x도 -x-1=-(x+1)의 값으로 되돌아간다.[2]
x=4시, ~x는 -(x+1)=-5.

음수 비트 표시

Python 3에서 10진수 음수를 bin () 로 2진수 문자열로 변환하면 2진수 대신 음수로 절대값을 되돌려줍니다.bin(-5)은 0b 1011이 되지 않고 -0b 101로 출력됩니다.

print(bin(-5))
#　-0b101

파이톤3의 int형은 상한, 하한, 위의 비트가 무한 비트(0 또는 1)[1:1]로 가정하기 때문에 음수의 이진수는 변하지 않는 상황에서 무한 비트 1이 출력되기 때문에 표시할 수 없다.따라서 마이너스를 더 짧은 표현으로 표현하기 위해 마이너스의 2의 보수에 -1의 값(기호반전)을 곱하여 표현한다.이런 상황에서 마이너스의 2의 부호는 이 마이너스의 절대값과 같다.1011(-5)의 2의 부호는 0101(5)이고 -1과 -101(-5)을 곱하여 출력한다.이렇게 2의 보너스 표현이 아니라 마이너스로 마이너스를 표현한다.

음수 2의 부호화 문자열

음수 2의 부호화 표시 문자열을 얻으려면 표현할 위치를 한정해야 한다.4비트의 경우 필요한 비트 수의 최대치를 취하는 논리적 적(AND), 예를 들어 0xf(0b11111), 8비트의 경우 0xff(0b1111111), 16비트의 경우 0xfff(0b111111111111111111)를 취한다.

print(bin(-5 & 0b1111))
# 0b1011
print(bin(-5 & 0b11111111))
# 0b11111011

2의 부호화 숫자 상수

또 파이톤3에서 수치 소양으로 2의 보수를 주어도 2의 보수로 보지 않고 정수로 본다.예를 들어 4위의 수치 소양이 있는 상황에서 0b1011의 10진법은 출력이 11이고 -5가 아니다.

x = 0b1011
print(x)
# 11

수치 소양의 4위 이상 위치가 모두 0으로 간주되어 정수가 되기 때문이다.(기호가 없는 이전 테이블의 정수 열 참조)
이 경우 다음은 2의 부호로 해석되기 때문에 마이너스로 간주한다.

~(x ^ 0b1111)

1011과 1111의 배타 논리와 반전 1011의 비트로 0100이 되었다.그리고 연산자가 다시 비트반전을 하여 원시 1011로 바뀌었기 때문에 단순히 원상태로 회복된 것으로 보인다.
그러나 ~산자가 반전할 때 조작수 0100의 4자리 이상 위치가 무한 개수'0'으로 채워졌다(...00000010)[1:2]. 그래서 반전된 결과의 1011 상위도 반전되어 모두'1'(...1111111111111), 인코딩 위치가'1'의 2의 보충수가 되어 음수-5 출력으로 한다.

print(~(x ^ 0b1111))
#　-5

주어진 수치 소양의 위치를 늘려도 마찬가지다.
각주
정수형의 비트 단위 연산 ↩︎ ↩︎ ↩︎
6.6. 산술 연산과 비트 단위 연산 ↩︎