파이썬에서 2의 보수
이진 문자열 (예 : '111111111111')을 2의 보수 정수 -1 로 변환하는 내장 함수가 파이썬에 있습니까?
2의 보수 (1<<bits)는 가장 높은 비트가 1이면 뺍니다 . 예를 들어 8 비트를 취하면 범위는 127에서 -128까지입니다.
정수의 2의 보수에 대한 함수 ...
def twos_comp(val, bits):
"""compute the 2's complement of int value val"""
if (val & (1 << (bits - 1))) != 0: # if sign bit is set e.g., 8bit: 128-255
val = val - (1 << bits) # compute negative value
return val # return positive value as is
이진 문자열에서 이동하는 것은 특히 쉽습니다.
binary_string = '1111' # or whatever... no '0b' prefix
out = twos_comp(int(binary_string,2), len(binary_string))
나에게 좀 더 유용한 것은 16 진수 값 (이 예에서는 32 비트)에서 가져 오는 것입니다.
hex_string = '0xFFFFFFFF' # or whatever... '0x' prefix doesn't matter
out = twos_comp(int(hex_string,16), 32)
내장되어 있지는 않지만 비정상적인 길이 숫자를 원한다면 bitstring 모듈을 사용할 수 있습니다 .
>>> from bitstring import Bits
>>> a = Bits(bin='111111111111')
>>> a.int
-1
동일한 객체를 다음과 같은 여러 방법으로 동등하게 만들 수 있습니다.
>>> b = Bits(int=-1, length=12)
임의의 길이의 비트 문자열처럼 동작하고 속성을 사용하여 다른 해석을 얻습니다.
>>> print a.int, a.uint, a.bin, a.hex, a.oct
-1 4095 111111111111 fff 7777
Python 3.2부터는 바이트 조작을위한 내장 함수가 있습니다 : https://docs.python.org/3.4/library/stdtypes.html#int.to_bytes .
to_bytes와 from_bytes를 결합하면
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)
검사:
twos('11111111', 1) # gives -1
twos('01111111', 1) # gives 127
이전 버전의 Python의 경우 travc의 대답은 좋지만 문자열 대신 정수로 작업하려는 경우 음수 값에는 작동하지 않습니다. f (f (val)) == val이 각 val에 대해 참인 2의 보수 함수는 다음과 같습니다.
def twos_complement(val, nbits):
"""Compute the 2's complement of int value val"""
if val < 0:
val = (1 << nbits) + val
else:
if (val & (1 << (nbits - 1))) != 0:
# If sign bit is set.
# compute negative value.
val = val - (1 << nbits)
return val
>>> bits_in_word=12
>>> int('111111111111',2)-(1<<bits_in_word)
-1
이것은 다음과 같은 이유로 작동합니다.
이진수의 2의 보수는 2의 큰 거듭 제곱에서 숫자를 뺀 값으로 정의됩니다 (특히 N 비트 2의 보수의 경우 2 ^ N에서). 그런 다음 숫자의 2의 보수는 대부분의 산술에서 원래 숫자의 음수처럼 작동하며 자연스러운 방식으로 양수와 공존 할 수 있습니다.
이렇게하면 비트 논리를 사용하여 효율적으로 두 가지의 보수를 얻을 수 있습니다.
def twos_complement(value, bitWidth):
if value >= 2**bitWidth:
# This catches when someone tries to give a value that is out of range
raise ValueError("Value: {} out of range of {}-bit value.".format(value, bitWidth))
else:
return value - int((value << 1) & 2**bitWidth)
작동 원리 :
먼저 사용자가 제공된 비트 범위 내에있는 값을 전달했는지 확인합니다 (예 : 누군가가 0xFFFF를 제공하고 8 비트를 지정 함).이 문제에 대한 또 다른 해결책은 다음과 같이 값을 비트 AND (&)하는 것입니다. (2 ** bitWidth) -1
결과를 얻기 위해 값이 왼쪽으로 1 비트 이동됩니다. 그러면 값 (부호 비트)의 MSB가와 함께 anded 될 위치로 이동합니다 2**bitWidth. 부호 비트가 '0'이면 감수는 0이되고 결과는 value - 0입니다. 부호 비트가 '1'이면 감수성이 2**bitWidth되고 결과는 다음과 같습니다.value - 2**bitWidth
예 1 : 매개 변수가 value = 0xFF (255d, b11111111) 및 bitWidth = 8 인 경우
- 0xFF-정수 ((0xFF << 1) & 2 ** 8)
- 0xFF-정수 ((0x1FE) 및 0x100)
- 0xFF-정수 (0x100)
- 255 ~ 256
- -1
예 2 : 매개 변수가 value = 0x1F (31d, b11111) 및 bitWidth = 6 인 경우
- 0x1F-int ((0x1F << 1) & 2 ** 6)
- 0x1F-int ((0x3E) 및 0x40)
- 0x1F-정수 (0x00)
- 31-0
- 31
예 3 : 값 = 0x80, bitWidth = 7
ValueError: Value: 128 out of range of 7-bit value.
예 4 : 값 = 0x80, bitWitdh = 8
- 0x80-정수 ((0x80 << 1) & 2 ** 8)
- 0x80-정수 ((0x100) 및 0x100)
- 0x80-정수 (0x100)
- 128 ~ 256
- -128
이제 다른 사람들이 이미 게시 한 것을 사용하여 비트 문자열을 int (bitstring, 2)에 전달하고 twos_complement 메서드의 값 매개 변수에 전달합니다.
몇 가지 구현 (사용할 의도가 아닌 예시 일뿐) :
def to_int(bin):
x = int(bin, 2)
if bin[0] == '1': # "sign bit", big-endian
x -= 2**len(bin)
return x
def to_int(bin): # from definition
n = 0
for i, b in enumerate(reversed(bin)):
if b == '1':
if i != (len(bin)-1):
n += 2**i
else: # MSB
n -= 2**i
return n
누군가 역방향이 필요한 경우 :
def num_to_bin(num, wordsize):
if num < 0:
num = 2**wordsize+num
base = bin(num)[2:]
padding_size = wordsize - len(base)
return '0' * padding_size + base
for i in range(7, -9, -1):
print num_to_bin(i, 4)
다음을 출력해야합니다 : 0111 0110 0101 0100 0011 0010 0001 0000 1111 1110 1101 1100 1011 1010 1001 1000
아니요, 2의 보수 이진 문자열을 십진수 로 변환하는 내장 함수는 없습니다 .
이를 수행하는 간단한 사용자 정의 함수 :
def two2dec(s):
if s[0] == '1':
return -1 * (int(''.join('1' if x == '0' else '0' for x in s), 2) + 1)
else:
return int(s, 2)
이 함수는 비트 너비를 매개 변수로 사용하지 않고 대신 양의 입력 값을 하나 이상의 선행 0 비트로 지정해야합니다.
예 :
In [2]: two2dec('1111')
Out[2]: -1
In [3]: two2dec('111111111111')
Out[3]: -1
In [4]: two2dec('0101')
Out[4]: 5
In [5]: two2dec('10000000')
Out[5]: -128
In [6]: two2dec('11111110')
Out[6]: -2
In [7]: two2dec('01111111')
Out[7]: 127
erikb85가 성능을 가져 왔기 때문에 Scott Griffiths 에 대한 travc의 대답은 다음 과 같습니다.
In [534]: a = [0b111111111111, 0b100000000000, 0b1, 0] * 1000
In [535]: %timeit [twos_comp(x, 12) for x in a]
100 loops, best of 3: 8.8 ms per loop
In [536]: %timeit [bitstring.Bits(uint=x, length=12).int for x in a]
10 loops, best of 3: 55.9 ms per loop
그래서 bitstring에서 발견된다 다른 질문 보다 느린, 크기의 거의 순서 int. 그러나 반면에 단순함을이기는 것은 어렵습니다. 저는 a uint를 비트 문자열로 변환 한 다음 int; 이것을 이해 하지 못 하거나 버그를 도입 할 곳을 찾으려면 열심히 노력해야 합니다. Scott Griffiths의 답변에서 알 수 있듯이 동일한 앱에 유용 할 수있는 클래스에 훨씬 더 많은 유연성이 있습니다. 그러나 세 번째로 travc의 대답은 실제로 무슨 일이 일어나고 있는지 명확하게 보여줍니다. 초보자도 unsigned int에서 2s 보완 signed int 로의 변환이 단지 2 줄의 코드를 읽는 것에서 의미하는 바를 이해할 수 있어야합니다.
어쨌든 비트를 직접 조작하는 다른 질문과는 달리,이 질문은 고정 길이 int에 대해 산술을 수행하는 것에 관한 것입니다. 따라서 성능이 필요하다면 아마도 이러한 것들이 많이 있기 때문에 아마도 벡터화되기를 원할 것입니다. numpy에 대한 travc의 답변 수정 :
def twos_comp_np(vals, bits):
"""compute the 2's compliment of array of int values vals"""
vals[vals & (1<<(bits-1)) != 0] -= (1<<bits)
return vals
지금:
In [543]: a = np.array(a)
In [544]: %timeit twos_comp_np(a.copy(), 12)
10000 loops, best of 3: 63.5 µs per loop
사용자 지정 C 코드로 이길 수 있지만 그럴 필요는 없습니다.
Python 3.4.0을 사용하고 있습니다.
Python 3에서는 데이터 유형 변환에 몇 가지 문제가 있습니다.
그래서 ... 여기에서 16 진 문자열로 많이 작동하는 (나와 같은) 사람들에게 팁을 알려 드리겠습니다.
16 진수 데이터를 가져와 보완 할 것입니다.
a = b'acad0109'
compl = int(a,16)-pow(2,32)
result=hex(compl)
print(result)
print(int(result,16))
print(bin(int(result,16)))
결과 = -1397948151 또는 -0x5352fef7 또는 '-0b1010011010100101111111011110111'
불행히도 부호없는 정수를 2의 보수 부호 값으로 캐스트하는 내장 함수는 없지만 비트 연산을 사용하여 그렇게하는 함수를 정의 할 수 있습니다.
def s12(value):
return -(value & 0b100000000000) | (value & 0b011111111111)
첫 번째 비트 및 연산은 음수를 부호 확장하는 데 사용되며 (최상위 비트가 설정 됨) 두 번째는 나머지 11 비트를 가져 오는 데 사용됩니다. 이것은 파이썬의 정수가 임의 정밀도 2의 보수 값으로 취급되기 때문에 작동합니다.
그런 다음 이것을 int함수 와 결합하여 이진수 문자열을 부호없는 정수 형식으로 변환 한 다음 12 비트 부호있는 값으로 해석 할 수 있습니다.
>>> s12(int('111111111111', 2))
-1
>>> s12(int('011111111111', 2))
2047
>>> s12(int('100000000000', 2))
-2048
이 함수의 좋은 속성 중 하나는 멱등 성이기 때문에 이미 서명 된 값의 값이 변경되지 않는다는 것입니다.
>>> s12(-1)
-1
이것은 3 바이트에서 작동합니다. 라이브 코드는 여기
def twos_compliment(byte_arr):
a = byte_arr[0]; b = byte_arr[1]; c = byte_arr[2]
out = ((a<<16)&0xff0000) | ((b<<8)&0xff00) | (c&0xff)
neg = (a & (1<<7) != 0) # first bit of a is the "signed bit." if it's a 1, then the value is negative
if neg: out -= (1 << 24)
print(hex(a), hex(b), hex(c), neg, out)
return out
twos_compliment([0x00, 0x00, 0x01])
>>> 1
twos_compliment([0xff,0xff,0xff])
>>> -1
twos_compliment([0b00010010, 0b11010110, 0b10000111])
>>> 1234567
twos_compliment([0b11101101, 0b00101001, 0b01111001])
>>> -1234567
twos_compliment([0b01110100, 0b11001011, 0b10110001])
>>> 7654321
twos_compliment([0b10001011, 0b00110100, 0b01001111])
>>> -7654321
Ok i had this issue with uLaw compression algorithm with PCM wav file type. And what i've found out is that two's complement is kinda making a negative value of some binary number as can be seen here.And after consulting with wikipedia i deemed it true.
The guy explained it as finding least significant bit and flipping all after it. I must say that all these solutions above didn't help me much. When i tried on 0x67ff it gave me some off result instead of -26623. Now solutions may have worked if someone knew the least significant bit is scanning list of data but i didn't knew since data in PCM varies. So here is my answer:
max_data = b'\xff\x67' #maximum value i've got from uLaw data chunk to test
def twos_compliment(short_byte): # 2 bytes
short_byte = signedShort(short_byte) # converting binary string to integer from struct.unpack i've just shortened it.
valid_nibble = min([ x*4 for x in range(4) if (short_byte>>(x*4))&0xf ])
bit_shift = valid_nibble + min( [ x for x in [1,2,4,8] if ( ( short_byte>>valid_nibble )&0xf )&x ] )
return (~short_byte)^( 2**bit_shift-1 )
data = 0x67ff
bit4 = '{0:04b}'.format
bit16 = lambda x: ' '.join( map( bit4, reversed([ x&0xf, (x>>4)&0xf, (x>>8)&0xf, (x>>12)&0xf ]) ) )
# print( bit16(0x67ff) , ' : ', bit16( twos_compliment( b'\xff\x67' ) ) )
# print( bit16(0x67f0) , ' : ', bit16( twos_compliment( b'\xf0\x67' ) ) )
# print( bit16(0x6700) , ' : ', bit16( twos_compliment( b'\x00\x67' ) ) )
# print( bit16(0x6000) , ' : ', bit16( twos_compliment( b'\x00\x60' ) ) )
print( data, twos_compliment(max_data) )
Now since code is unreadable i will walk you through the idea.
## example data, for testing... in general unknown
data = 0x67ff # 26623 or 0110 0111 1111 1111
This is just any hexadecimal value, i needed test to be sure but in general it could be anything in range of int. So not to loop over whole bunch of 65535 values short integer can have i decided to split it by nibbles ( 4 bits ). It could be done like this if you haven't used bitwise operators before.
nibble_mask = 0xf # 1111
valid_nibble = []
for x in range(4): #0,1,2,3 aka places of bit value
# for individual bits you could go 1<<x as you will see later
# x*4 is because we are shifting bit places , so 0xFA>>4 = 0xF
# so 0x67ff>>0*4 = 0x67ff
# so 0x67ff>>1*4 = 0x67f
# so 0x67ff>>2*4 = 0x67
# so 0x67ff>>3*4 = 0x6
# and nibble mask just makes it confided to 1 nibble so 0xFA&0xF=0xA
if (data>>(x*4))&nibble_mask: valid_nibble.append(x*4) # to avoid multiplying it with 4 later
So we are searching for least significant bit so here the min(valid_nibble ) will suffice. Here we've gotten the place where first active (with setted bit) nibble is. Now we just need is to find where in desired nibble is our first setted bit.
bit_shift = min(valid_nibble)
for x in range(4):
# in my example above [1,2,4,8] i did this to spare python calculating
ver_data = data>>min(bit_shift ) # shifting from 0xFABA to lets say 0xFA
ver_data &= nibble_mask # from 0xFA to 0xA
if ver_data&(1<<x):
bit_shift += (1<<x)
break
Now here i need to clarify somethings since seeing ~ and ^ can confuse people who aren't used to this:
XOR: ^: 2 numbers are necesery
This operation is kinda illogical, for each 2 bits it scans if both are either 1 or 0 it will be 0, for everything else 1.
0b10110
^0b11100
---------
0b01010
And another example:
0b10110
^0b11111
---------
0b01001
1's complement : ~ - doesn't need any other number
This operation flips every bit in a number. It is very similar to what we are after but it doesn't leave the least significant bit.
0b10110
~
0b01001
And as we can see here 1's compliment is same as number XOR full set bits.
Now that we've understood each other, we will getting two's complement by restoring all bites to least significant bit in one's complement.
data = ~data # one's complement of data
This unfortunately flipped all bits in our number, so we just need to find a way to flip back the numbers we want. We can do that with bit_shift since it is bit position of our bit we need to keep. So when calculating number of data some number of bits can hold we can do that with 2**n and for nibble we get 16 since we are calculating 0 in values of bits.
2**4 = 16 # in binary 1 0000
But we need the bytes after the 1 so we can use that to diminish the value by 1 and we can get.
2**4 -1 = 15 # in binary 0 1111
So lets see the logic in concrete example:
0b110110
lsb = 2 # binary 10
~0b110110
----------
0b001001 # here is that 01 we don't like
0b001001
^0b000011 # 2**2 = 4 ; 4-1 = 3 in binary 0b11
---------
0b001010
I hope this help'd you or any newbie that had this same problem and researched their a** off finding the solution. Have in mind this code i wrote is frankenstein code , that i why i had to explain it. It could be done more prettier, if anyone wants to make my code pretty please be my guest.
Here's a version to convert each value in a hex string to it's two's complement version.
In [5159]: twoscomplement('f0079debdd9abe0fdb8adca9dbc89a807b707f')
Out[5159]: '10097325337652013586346735487680959091'
def twoscomplement(hm):
twoscomplement=''
for x in range(0,len(hm)):
value = int(hm[x],16)
if value % 2 == 1:
twoscomplement+=hex(value ^ 14)[2:]
else:
twoscomplement+=hex(((value-1)^15)&0xf)[2:]
return twoscomplement
It's much easier than all that...
for X on N bits: Comp = (-X) & (2**N - 1)
def twoComplement(number, nBits):
return (-number) & (2**nBits - 1)
ReferenceURL : https://stackoverflow.com/questions/1604464/twos-complement-in-python
'Development Tip' 카테고리의 다른 글
| Java의 파일 이름이 공용 클래스 이름과 동일한 이유는 무엇입니까? (0) | 2020.12.25 |
|---|---|
| try {} catch {}와 if {} else {}의 장점은 무엇입니까? (0) | 2020.12.15 |
| Linux에서 getch () 및 getche ()에 해당하는 것은 무엇입니까? (0) | 2020.12.15 |
| Pylint의 파일 수준에서 "missing docstring"경고를 비활성화하려면 어떻게해야합니까? (0) | 2020.12.15 |
| Node.js를 사용하여 파일 시스템의 디렉토리 구조를 JSON으로 변환 (0) | 2020.12.15 |