Come posso controllare il peso di Hamming senza convertirlo in binario?

Question

Come posso ottenere il numero di " 1 " s nella rappresentazione binaria di un numero senza effettivamente convertire e contare?

per es.

  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

IMO, un buon approccio sarebbe quello di utilizzare una tabella di ricerca: creare un dizionario che converte i byte in numero di 1 (è possibile utilizzare il codice pubblicato per generarlo, dovrebbe essere eseguito solo una volta) e quindi usa qualcosa del genere:

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

Credo che questo sia un compromesso abbastanza buono tra spazio e tempo di esecuzione.

Answer 2

Non sono un programmatore di Python, ma spero che ti basti seguire.

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

return c

Anche se un po 'oscuro, il suo vantaggio principale è la velocità e la semplicità. Il ciclo while viene ripetuto una sola volta per ogni bit impostato su 1 in n.

Answer 3

Non puoi renderlo meno complesso dal punto di vista computazionale. Sarà O (n) il numero di bit o, come risposta con l'amplificatore &; il trucco ha mostrato, O (n) il numero di bit impostato su 1; ma a meno che tutti i numeri che stai utilizzando non siano un caso speciale, quest'ultimo dovrebbe essere in media n / 2, quindi entrambi i numeri O (n) sono uguali.

E il trucco della tabella di ricerca, ovviamente, in realtà non sta facendo nulla per la complessità computazionale; sta solo pagando il tempo con lo spazio ma senza cambiare l'economia di fondo, che è che devi esaminare ogni bit una volta in qualche modo e non c'è modo di aggirarlo. Non puoi, logicamente, rispondere a una domanda sui bit nel numero senza ispezionare ciascuno di essi.

Ora, suppongo di essere un po 'sciatto poiché molti di questi esempi sono in realtà O (n ^ 2) poiché in Python devi esaminare l'intero numero contemporaneamente, quindi con un intero lungo di Python di, diciamo , 100 byte, un + o un & Amp; o un'operazione / guarderà ogni byte almeno una volta, e ciò accadrà ripetutamente fino a quando il numero non sarà ridotto a zero (negli schemi sopra descritti), quindi queste, ancora, sono in realtà operazioni O (n ^ 2). Non sono sicuro che Python consentirà una vera soluzione O (n) qui.

Comunque: se stavi davvero chiedendo della complessità computazionale , che significa specificamente analisi big-O, questa è la tua risposta. : -)

Answer 4

Se vuoi farlo in una sola riga, puoi usare:

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

Answer 5

Se sei davvero preoccupato per la velocità, codificalo in C (vedi questa domanda per come) e interfacciarsi con l'implementazione C usando qualcosa come ctypes .

Answer 6

Qui:

def bitCount (int_no):

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

Questo potrebbe essere un modo vecchio ed efficiente per farlo ... originariamente implementato in C (Algo ha un nome che non ricordo). Funziona bene per me spero che lo faccia per qualsiasi altra persona

Answer 7

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

Questo utilizza il corto circuito e la ricorsione, quando n è maggiore di 0, passa a calcolare 1 + p (n & amp; (n-1)) dove p (n & amp; (n- 1)) viene chiamato e così via, quando n è 0 restituisce 0. La complessità è O (n) poiché esegue il numero di volte che il numero di quelli esiste nel file binario.

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