1、Pythonにおける負数の格納方式
例
print(a)
a = bin(3)
print(a)
b = bin(-3 & 0xffffffff)
print(b)
c = bin(0xfffffffd)
print(c)
//出力
//-0b11
//0b11
//0b11111111111111111111111111111101
//0b11111111111111111111111111111101
- Pythonの整数型は2の補数形式で格納されます
- Pythonで負数(10進数表記)をbin()に入力すると、その原符号の2進数表現にマイナス記号を付けたものが出力されます、確認しやすいように(便利なわけないけど)
- Pythonで負数(16進数表記)をbin()に入力すると、対応する2進数表現が出力されます。(このときに注意)
したがって、負数(10進数表記)の2の補数を取得するには、手動で16進数の0xfffffffdとビットごとのAND演算を行い、結果も16進数になるので、それをbin()に渡して出力すると、ようやく目的の2の補数表現が得られます。
2、しかしc/c++/javaでは負数はすべて2の補数形式で格納されます。『コンピュータの原理』によれば、コンピュータ内部では負数を2の補数(Two's Complement)で表現します。
3、これによりPythonでは負数と0xffffffffとのAND演算を行い、負数の前のマイナス記号を取り除く必要があります。32ビットを超える部分は考慮しないと理解できます。このAND演算の具体的な手順は次のとおりです。正数の場合はそのままAND演算し、負数の場合は先頭のマイナス記号を取り除き、反転して、1を加えてからAND演算を行います。これで負数の2の補数が得られます。
したがって、出力されるaも切り詰める必要がありますが、単純に&0xffffffffを使うわけにはいきません。そうすると-1に1を加えた場合は正しいし、結果が正数の場合も問題ありませんが、元の結果が負数の場合は、またおかしな結果になってしまいます。最終的な本当の解決策は次のとおりです。
例
while b!=0:
ta = a
a = a^b
b = ((ta&b)<<1)&0xffffffff
hibit = (a&0x80000000)>>31
if hibit==1:
return -(((~a)+1)&0xffffffff)
else:
return a&0xffffffff
その原理は、まず第32ビットの符号ビットで負数かどうかを判断し、負数の場合は反転して1を加えてから切り詰め、最後にマイナス記号を付けます。正数の場合はそのまま切り詰めます。簡潔だと謳われた簡単なPythonバージョンがこのようになってしまい、本当に奇妙です。
4、したがって、自分が書いた『剣指Offer』の「2進数中の1の個数を求める」を確認してみてください。c++プログラムとpythonプログラムの違い(負数の2の補数の違い)について。
さらにこの問題では、1を減算してAND演算を行う計算方法で個数を求めることも注意が必要です。
5、2進数中の1の個数を求めるには、Pythonで書くと次のようになります。
例
def NumberOf1(self, n):
# write code here
if n<0:
n=n&0xffffffff #これはPythonの場合。Pythonと他の言語では負数の格納形式が少し異なります
temp=0x00000001
count=0
for i in range(64):
if n&temp:
count=count+1
temp=temp<<1
return count
6、(別の問題ですが、これもビット演算です)2進数(64ビット)の中に1がただ1つだけある場合(時間計算量を低く抑えるためのポイント)、この数字の何ビット目がその1なのかを求めます。たとえば、入力が8なら出力は4です。
方法1:O(n)の時間計算量
例
if input_n<0:
input_n=input_n&0xffffffff
temp=0x00000001
for i in range(64):
if input_n&temp:
return i+1
temp=temp<<1
return 0
方法2:O(logn)。主に二分法を使用して解きますが、重要な点はその値の大小を判断する必要があることです。実はmath.log(input_n, 2)を使用して解くこともできます(ただし、このライブラリ関数の時間計算量はあまり明確ではありません)
原文アドレス:https://blog.csdn.net/qinglv1/article/details/90580013