1. Die Speichermethode für negative Zahlen in Python
Beispiel
print(a)
a = bin(3)
print(a)
b = bin(-3 & 0xffffffff)
print(b)
c = bin(0xfffffffd)
print(c)
// Ausgabe
//-0b11
//0b11
//0b11111111111111111111111111111101
//0b11111111111111111111111111111101
- Ganzzahlen in Python werden in Zweierkomplementform gespeichert
- In Python gibt bin einer negativen Zahl (Dezimaldarstellung) ihre Vorzeichen-Betrag-Binärdarstellung plus ein negatives Vorzeichenaus, zur bequemen Ansicht (als ob das bequem wäre!)
- In Python gibt bin einer negativen Zahl (Hexadezimaldarstellung) die entsprechende Binärdarstellung aus. (Beachten Sie dies jetzt)
Um also das Zweierkomplement einer negativen Zahl (Dezimaldarstellung) zu erhalten, müssen Sie manuell eine bitweise UND-Verknüpfung mit der Hexadezimalzahl 0xfffffffd durchführen. Das Ergebnis ist ebenfalls eine Hexadezimalzahl; übergeben Sie es dann an bin() zur Ausgabe, und Sie erhalten die gewünschte Zweierkomplementdarstellung.
2. In C/C++/Java werden negative Zahlen jedoch in der Zweierkomplementform gespeichert. „Computer Principles“ besagt, dass der Computer intern das Zweierkomplement verwendet, um negative Zahlen darzustellen.
3. Dies führt dazu, dass in Python eine UND-Verknüpfung zwischen der negativen Zahl und 0xffffffff durchgeführt werden muss, um das führende negative Vorzeichen zu entfernen. Man kann es so verstehen, dass alles jenseits von 32 Bits nicht berücksichtigt wird. Die konkreten Schritte dieser UND-Verknüpfung sind: Wenn es eine positive Zahl ist, direkt die UND-Verknüpfung durchführen; wenn es eine negative Zahl ist, zuerst das führende negative Vorzeichen entfernen, dann invertieren, dann 1 addieren, dann die UND-Verknüpfung durchführen. So erhält man das Zweierkomplement der negativen Zahl.
Deshalb müssen wir für die Ausgabe a ebenfalls abschneiden, aber wir können nicht einfach und direkt &0xffffffff verwenden, denn wenn wir das tun, ist -1+1 korrekt, und positive Ergebnisse sind auch in Ordnung, aber wenn das ursprüngliche Ergebnis negativ ist, erscheinen wieder seltsame Ergebnisse. Die endgültige tatsächliche Lösung ist wie folgt:
Beispiel
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
Das Prinzip besteht darin, zunächst anhand des 32. Vorzeichenbits zu bestimmen, ob es negativ ist. Wenn es negativ ist, zuerst invertieren, 1 addieren, dann abschneiden und schließlich ein negatives Vorzeichen hinzufügen; wenn es positiv ist, direkt abschneiden. Infolgedessen ist die sogenannte prägnante und einfache Python-Version so geworden, was wirklich bizarr ist.
4. Sie können sich also Ihre eigene Lösung für „Die Anzahl der Einsen in Binär“ in „Sword Finger Offer“ ansehen. Für den Unterschied zwischen C++-Programmen und Python-Programmen (den Unterschied beim Zweierkomplement negativer Zahlen).
Außerdem musst du in diesem Problem auch auf die Berechnungsmethode achten, bei der 1 subtrahiert und dann eine AND-Operation ausgeführt wird, um die Anzahl zu ermitteln.
5. Um die Anzahl der Einsen in Binär zu ermitteln, sieht es in Python geschrieben so aus:
Beispiel
def NumberOf1(self, n):
# Hier Code schreiben
if n<0:
n=n&0xffffffff # Dies ist in Python, und das Format der Speicherung negativer Zahlen in Python unterscheidet sich etwas von anderen Sprachen
temp=0x00000001
count=0
for i in range(64):
if n&temp:
count=count+1
temp=temp<<1
return count
6. (Ein anderes Problem, aber ebenfalls eine Bitoperation) In Binär (64-Bit) gibt es genau eine 1 (der Schlüssel zur Erreichung geringer Zeitkomplexität). Bestimme, welches Bit dieser Zahl diese 1 ist. Zum Beispiel: Eingabe 8, Ausgabe 4.
Methode 1: O(n) Zeitkomplexität
Beispiel
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
Methode 2: O(logn), hauptsächlich unter Verwendung der binären Suchmethode gelöst, aber der entscheidende Punkt ist, die Größenordnung seines Wertes zu beurteilen. Tatsächlich kann man sie auch mit math.log(input_n, 2) lösen (aber die Zeitkomplexität dieser Bibliotheksfunktion ist nicht ganz klar).
Originaladresse: https://blog.csdn.net/qinglv1/article/details/90580013