1、Pythonにおける負数の格納方式

例

a = bin(-3)
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を加えた場合は正しいし、結果が正数の場合も問題ありませんが、元の結果が負数の場合は、またおかしな結果になってしまいます。最終的な本当の解決策は次のとおりです。

例

def getSum(a,b):
     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で書くと次のようになります。

例

class Solution:
    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)の時間計算量

例

def search_1(input_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