1. En Python, la méthode de stockage des nombres négatifs
Exemple
print(a)
a = bin(3)
print(a)
b = bin(-3 & 0xffffffff)
print(b)
c = bin(0xfffffffd)
print(c)
// sortie
//-0b11
//0b11
//0b11111111111111111111111111111101
//0b11111111111111111111111111111101
- Les entiers en Python sont stockés sous forme de complément à deux
- En Python, bin d'un nombre négatif (représentation décimale) affiche sa représentation binaire en signe-magnitude avec un signe négatif, pour un affichage pratique (comme si c'était pratique !)
- En Python, bin d'un nombre négatif (représentation hexadécimale) affiche la représentation binaire correspondante. (Notez ceci maintenant)
Ainsi, pour obtenir le complément à deux d'un nombre négatif (représentation décimale), vous devez effectuer manuellement une opération AND bit à bit entre celui-ci et le nombre hexadécimal 0xfffffffd. Le résultat est également un nombre hexadécimal ; passez-le ensuite à bin() pour l'affichage, et vous obtenez la représentation en complément à deux souhaitée.
2. Cependant, en C/C++/Java, les nombres négatifs sont stockés sous forme de complément à deux. « Principes des ordinateurs » indique que l'ordinateur utilise en interne le complément à deux pour représenter les nombres négatifs.
3. Cela conduit, en Python, à la nécessité d'effectuer une opération AND entre le nombre négatif et 0xffffffff afin de supprimer le signe négatif devant. On peut comprendre cela comme le fait de ne rien considérer au-delà de 32 bits. Les étapes spécifiques de cette opération AND sont : s'il s'agit d'un nombre positif, effectuer directement le AND ; s'il s'agit d'un nombre négatif, retirer d'abord le signe négatif initial, puis inverser, puis ajouter 1, puis effectuer l'opération AND. Ainsi, on obtient le complément à deux du nombre négatif.
Par conséquent, pour la sortie a, nous devons également tronquer, mais nous ne pouvons pas simplement et directement faire &0xffffffff, car si nous faisons cela, -1+1 est correct, et les résultats positifs conviennent aussi, mais si le résultat d'origine est négatif, des résultats étranges réapparaîtront. La véritable solution finale est la suivante :
Exemple
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
Le principe est de déterminer d'abord s'il est négatif via le 32e bit de signe. S'il est négatif, inverser d'abord, ajouter 1, puis tronquer, et enfin ajouter un signe négatif ; s'il est positif, tronquer directement. En conséquence, la soi-disant version Python concise et facile est devenue ainsi, ce qui est vraiment bizarre.
4. Vous pouvez donc regarder votre propre solution pour « Le nombre de 1 en binaire » dans « Sword Finger Offer ». Pour la différence entre les programmes C++ et les programmes Python (la différence dans le complément à deux des nombres négatifs).
De plus, dans ce problème, vous devez également faire attention à la méthode de calcul consistant à soustraire 1 puis à effectuer une opération AND pour trouver le nombre.
5. Pour résoudre le nombre de 1 en binaire, écrit en Python, c'est comme ceci :
Exemple
def NumberOf1(self, n):
# écrire le code ici
if n<0:
n=n&0xffffffff # Ceci est en Python, et le format de stockage des nombres négatifs en Python est un peu différent de celui des autres langages
temp=0x00000001
count=0
for i in range(64):
if n&temp:
count=count+1
temp=temp<<1
return count
6. (Un autre problème, mais aussi une opération bit à bit) En binaire (64 bits), il y a exactement un 1 (la clé pour obtenir une faible complexité temporelle). Déterminez quel bit de ce nombre est ce 1. Par exemple, entrée 8, sortie 4.
Méthode 1 : complexité temporelle O(n)
Exemple
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
Méthode 2 : O(logn), principalement en utilisant la méthode de recherche binaire pour la résoudre, mais le point clé est de déterminer l'ordre de grandeur de sa valeur. En fait, vous pouvez aussi utiliser math.log(input_n, 2) pour la résoudre (mais la complexité temporelle de cette fonction de bibliothèque n'est pas très claire).
Adresse d'origine : https://blog.csdn.net/qinglv1/article/details/90580013