Come posso ottenere il numero di "1" nella rappresentazione binaria di un numero senza effettivamente convertirlo e contare?Come posso controllare Hamming Weight senza convertire in binario?
ad 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
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 che è stato postato per generarlo, sarà necessario solo eseguire una volta), e quindi usare qualcosa come questo:
def number_of_ones(n):
sum = 0
while n != 0:
sum += lookup_table[n & 0xff]
n >>= 8
return sum
credo che questo sia un discreto compromesso tra lo spazio e il tempo di rodaggio.
Non sono un programmatore Python, ma spero che sia sufficiente per voi da seguire.
c = 0
while n:
c += 1
n &= n - 1
return c
Mentre un po 'oscuro, il vantaggio principale è la velocità e la semplicità. Il ciclo while viene ripetuto una volta per ogni bit impostato su 1 in n.
Se si è effettivamente preoccupati per la velocità, codificarlo in C (vedere this question per come) e interfaccia con l'implementazione C utilizzando qualcosa come ctypes.
Mi preoccupo della complessità computazionale non della velocità o del linguaggio effettivi. –
Se si vuole fare in una sola riga, è possibile utilizzare:
sum([x&(1<<i)>0 for i in range(32)])
Non si può fare questo computazionalmente meno complessa. Sarà O (n) il numero di bit o, come la risposta con il trucco &, O (n) il numero di bit impostato su 1; ma a meno che tutti i numeri che stai usando siano un caso speciale, quest'ultimo dovrebbe essere in media n/2, quindi entrambi i numeri di O (n) sono gli stessi.
E il trucco della tabella di ricerca, ovviamente, in realtà non fa nulla per la complessità computazionale; sta pagando solo il tempo con lo spazio ma senza cambiare l'economia sottostante, che è che devi esaminare ogni bit una volta in qualche modo e non c'è modo di aggirare questo. Non è possibile, logicamente, rispondere a una domanda sui bit del numero senza ispezionarli.
Ora, suppongo di essere un po 'sciatto dal momento che molti di questi esempi sono in realtà O (n^2) poiché in Python è necessario esaminare l'intero numero in una volta, quindi con un intero lungo di Python di, diciamo, 100 byte, un + o uno & o una operazione/esaminerà ogni byte almeno una volta e ciò accadrà più e più volte fino a quando il numero sarà ridotto a zero (negli schemi descritti sopra), quindi questi, ancora, sono in realtà operazioni O (n^2). Non sono sicuro che Python consentirà una vera soluzione O (n) qui.
In ogni caso: se ti chiedessi davvero della complessità computazionale, che in particolare significa analisi big-O, questa è la tua risposta. :-)
p = lambda n: n e 1 + p (n & (n-1))
Questo utilizza corto circuito e ricorsione, quando n è maggiore di 0, si passa per calcolare 1 + p (n & (n-1)) dove viene chiamato p (n & (n-1)) e così via, quando n è 0 restituisce 0. La complessità è O (n) poiché esegue il numero di volte il numero di quelli esistenti nel binario.
Esempio: p (9) = 1 + p (8) = 1 + 1 + p (0) = 1 + 1 + 0 = 2
Se questa è una risposta valida, sarebbe più valida con qualche spiegazione. –
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 efficace per fare questo ... originariamente implementated in C (Algo ha un nome non ricordo). Funziona bene per me spero che lo faccia per qualsiasi altra persona
Si tratta di un duplicato di http://stackoverflow.com/questions/843737/count-bits-in-the-number-closed – ChrisW
@ ChrisW- python ec sono due diverse lanaghe – TStamper
Non è un duplicato esatto. le operazioni bit a bit in python sono molto più costose che c. –