¿Cómo puedo verificar Hamming Weight sin convertirlo en binario?

Question

¿Cómo puedo obtener el número de " 1 " s en la representación binaria de un número sin convertir y contar realmente?

por ejemplo

  def number_of_ones(n):
      # do something
      # I want to MAKE this FASTER (computationally less complex).
      c = 0
      while n:
        c += n%2
        n /= 2
      return c


>>> number_of_ones(5)
    2
>>> number_of_ones(4)
    1

Answer 1

En mi opinión, un buen enfoque sería usar una tabla de búsqueda: crear un diccionario que convierta los bytes en un número de 1 (puede usar el código que publicó para generarlo, solo necesitaría ejecutarse una vez), y luego usa algo como esto:

def number_of_ones(n):
    sum = 0
    while n != 0:
        sum += lookup_table[n & 0xff]
        n >>= 8
    return sum

Creo que esta es una compensación bastante buena entre el espacio y el tiempo de ejecución.

Answer 2

No soy un programador de Python, pero espero que sea suficiente para que me sigas.

c = 0
while n:
    c += 1
    n &= n - 1

return c

Si bien es un poco oscuro, su principal ventaja es la velocidad y la simplicidad. El ciclo while solo se repite una vez por cada bit establecido en 1 en n.

Answer 3

No puede hacer esto computacionalmente menos complejo. Será O (n) el número de bits, o, como la respuesta con el amplificador &; truco mostró, O (n) el número de bits establecido en 1; pero a menos que todos los números que esté utilizando sean un caso especial, este último debería ser en promedio n / 2, por lo que ambos números O (n) son iguales.

Y el truco de la tabla de búsqueda, por supuesto, no está haciendo nada por la complejidad computacional; solo está pagando por el tiempo con espacio pero sin cambiar la economía subyacente, que es que debe examinar cada bit una vez de alguna manera y no hay forma de evitarlo. No puede, lógicamente, responder una pregunta sobre los bits en el número sin inspeccionar cada uno de ellos.

Ahora, supongo que estoy siendo un poco descuidado ya que muchos de estos ejemplos son en realidad O (n ^ 2) ya que en Python tienes que examinar el número entero de una vez, así que con un entero largo de Python de, digamos , 100 bytes, un amplificador + o &; o una operación / mirará cada byte al menos una vez, y eso sucederá una y otra vez hasta que el número se reduzca a cero (en los esquemas descritos anteriormente), por lo que, de nuevo, estas son realmente operaciones O (n ^ 2). No estoy seguro de que Python permita una verdadera solución O (n) aquí.

De todos modos: si realmente estaba preguntando acerca de la complejidad computacional , lo que específicamente significa análisis big-O, esa es su respuesta. :-)

Answer 4

Si desea hacerlo en una sola línea, puede usar:

sum( [x&(1<<i)>0 for i in range(32)] )

Answer 5

Si realmente le preocupa la velocidad, codifíquela en C (consulte esta pregunta sobre cómo), e interactuar con la implementación de C usando algo como ctypes .

Answer 6

Aquí:

def bitCount (int_no):

c = 0
while(int_no):
    int_no &= (int_no - 1)
    c += 1
return c

Esta podría ser una forma antigua y eficiente de hacer esto ... implementado originalmente en C (Algo tiene un nombre que no recuerdo). Funciona bien para mí, espero que lo haga para cualquier otra persona

Answer 7

p = lambda n: ny 1 + p (n & amp; (n-1))

Esto utiliza cortocircuito y recursividad, cuando n es mayor que 0, cambia para calcular 1 + p (n & amp; (n-1)) donde p (n & amp; (n- 1)) se llama y así sucesivamente, cuando n es 0 devuelve 0. La complejidad es O (n) ya que se ejecuta el número de veces que existe el número de unos en el binario.

Ejemplo: p (9) = 1 + p (8) = 1 + 1 + p (0) = 1 + 1 + 0 = 2