1. En Python, la forma de almacenar números negativos

Ejemplo

a = bin(-3)
print(a)
 
a = bin(3)
print(a)
 
b = bin(-3 & 0xffffffff)
print(b)
 
c = bin(0xfffffffd)
print(c)
 
// Salida
//-0b11
//0b11
//0b11111111111111111111111111111101
//0b11111111111111111111111111111101
Es decir:
  • En Python, los enteros se almacenan en forma de complemento a dos.
  • En Python, al aplicar bin a un número negativo (representado en decimal), se obtiene la representación binaria de su código original con un signo negativo delante., para facilitar la visualización (¡vaya comodidad!)
  • En Python, al aplicar bin a un número negativo (representado en hexadecimal), se obtiene su representación binaria correspondiente. (Nota: en este caso)

Por lo tanto, para obtener el complemento a dos de un número negativo (representado en decimal), debes realizar manualmente una operación AND bit a bit con el número hexadecimal 0xfffffffd; el resultado también es un número hexadecimal, y luego pasarlo a bin() para obtener la representación en complemento a dos que deseas.

2. Sin embargo, en C/C++/Java los números negativos se almacenan en forma de complemento a dos. Según "Principios de Computación", internamente la computadora utiliza el complemento a dos (Two's Complement) para representar los números negativos.

3. Esto hace que en Python sea necesario realizar una operación AND entre el número negativo y 0xffffffff para quitar el signo negativo delante del número. Se puede entender que lo que exceda de 32 bits no se tiene en cuenta. Los pasos concretos de esta operación AND son: si es positivo, se hace la operación directamente; si es negativo, primero se quita el signo negativo delante, luego se invierten los bits, se suma 1 y finalmente se realiza la operación AND. De este modo se obtiene el complemento a dos del número negativo.

Por lo tanto, también tenemos que truncar la salida de a, pero no podemos aplicar directamente &0xffffffff de forma simple y brusca, porque si lo hacemos así, -1 + 1 daría el resultado correcto, y si el resultado es positivo tampoco habría problema; pero si el resultado original es negativo, se obtendría un resultado extraño. Finalmente, la solución real es la siguiente:

Ejemplo

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

El principio es primero usar el bit de signo en la posición 32 para determinar si es negativo. Si es negativo, se invierten los bits, se suma 1, luego se trunca y finalmente se añade el signo negativo; si es positivo, se trunca directamente. El resultado, que se supone sencillo y fácil, en la versión de Python queda así; es realmente extraño.

4. Así que puedes consultar mi propia solución en "Oferta de la Espada": el cálculo del número de unos en binario. En cuanto a la diferencia entre el programa en C++ y el programa en Python (diferencia del complemento a dos para negativos).

Además, en este problema, también hay que prestar atención al método de cálculo que consiste en restar 1 y luego realizar la operación AND para resolver el número de unos.

5. Para resolver el número de unos en binario, escrito en Python, sería así:

Ejemplo

class Solution:
    def NumberOf1(self, n):
        # write code here
        if n<0:
            n=n&0xffffffff # Esto es en Python; Python tiene una pequeña diferencia con otros lenguajes en el formato de almacenamiento de números negativos.
        temp=0x00000001
        count=0
        for i in range(64):
            if n&temp:
                count=count+1
            temp=temp<<1
        return count

6. (Otro problema, pero también de operaciones bit a bit) En un número binario de 64 bits hay exactamente un solo 1 (esta es la clave para lograr una baja complejidad temporal). Determina en qué posición está ese 1. Por ejemplo, si la entrada es 8, la salida es 4.

Método 1: complejidad temporal O(n)

Ejemplo

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

Método 2: O(logn), principalmente se utiliza el método de búsqueda binaria, pero un punto clave es que hay que determinar el tamaño de su valor. En realidad, también se puede usar math.log(input_n, 2) para resolverlo (aunque la complejidad temporal de esta función de biblioteca no está muy clara).

Dirección del artículo original: https://blog.csdn.net/qinglv1/article/details/90580013