Sto cercando un metodo per avere il numero di 1 nel numero 32 bit senza utilizzare un ciclo intermedio. qualsiasi organismo può aiutarmi e fornirmi il codice o l'algoritmo per farlo. Grazie in anticipo.numero di 1 in 32 bit numero
vedere il riferimento canonica: Bit Twiddling Hacks
Basta ricordare che gli input Java sono * sempre * firmati e modificabili di conseguenza. – erickson
Split il numero a 32 bit in quattro 8 numeri di bit (vedere il bit spostamento operatore, colata ecc)
Quindi, tramite una ricerca con 256 voci che converte il bit 8 numero in un conteggio di bit impostati. Aggiungi i quattro risultati, presto!
Inoltre, vedere quello che ha detto Mitch Wheat - po giocherellare può essere molto divertente;)
Vedi Integer.bitCount(int). È possibile fare riferimento al codice sorgente, se si vuole vedere come funziona; molti di routine po girarsi della classe Integer sono presi da Hacker's Delight.
Sì! Perché usare un bit esotici, quando c'è un metodo già disponibile. – Buhb
L'uso di built-in renderà inoltre più semplice per le versioni future di JVM la possibilità di utilizzare l'istruzione POPCNT SSE4.2. –
+1 per il metodo JRE. –
È possibile definire in modo ricorsivo:
int bitcount(int x) {
return (x==0) ? 0 : (x & 1 + bitcount(x/2));
}
Il codice di cui sopra non è testato, e probabilmente funziona solo per x> = 0. Si spera, si otterrà l'idea comunque ...
-1 per l'utilizzo della ricorsione quando è stato richiesto "no looping". Certo, non sta usando un costrutto di loop, ma funziona ancora in tempo non-O (1). – unwind
Siamo spiacenti. La domanda mi sembrava un problema di compiti a casa e volevo fornire una visione diversa. Per qualsiasi applicazione critica dal punto di vista delle prestazioni e per la maggior parte delle applicazioni non teoriche, scegli le soluzioni che ti permettono di dare una mano! – SteinNorheim
quello classico è: ritorno (x == 0)? 0: (1 + bitcount (x & (x - 1))); – Olexiy
Il mio preferito, direttamente da Bit Twiddling Hacks:
v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
NB: Questo non funzionerà correttamente con il tipo int firmato Java, ma l'idea di base è quella utilizzata dalla libreria. – erickson
Penso che tu voglia >>> invece di >>. – finnw
@finnw: Suppongo che tu intenda in Java (dal momento che nessun operatore di questo tipo esiste in C, dove ho visto/usato il trucco), in tal caso hai ragione, mantenere il segno è sbagliato. –
breve, la risposta oscenamente ottimizzato (in C):
int pop(unsigned x) {
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}
Per capire perché questa magia funziona, vedi La ricerca di un conteggio di popolazione accelerato di Henry S. Warren, Jr. capitolo 10 in Codice bello.
Ma la domanda era su Java e in Java non c'è un tipo int a 32 bit senza segno, e questo non funziona con l'int firmato a 32 bit di Java . – Jesper
Per quanto posso vedere, Java non è menzionato nella domanda. E forse ho sbagliato, ma i tag non dovrebbero essere usati per limitare una domanda ad una determinata lingua. – lindelof
IMO ti stai sbagliando. Se una domanda è codificata in Java, che altro significa, a parte che la domanda riguarda Java? Forse l'interlocutore dovrebbe anche menzionare nel testo che stanno parlando di Java, ma se non lo fanno, non penso che ne consegue che dovremmo fingere di non essere etichettato come Java. Se si può supporre che una risposta C sia accettabile, allora posso presumere che una risposta C con solo GCC sia accettabile e che dica di usare __builtin_popcount. Ma questo non aiuta molto il questionario ;-) –
seguito è JDK 1.5 attuazione di Integer.bitCount
public static int bitCount(int i) {
// HD, Figure 5-2
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
esempio vuoi piacere dal 2344 al 2,3,4,4? si prega di chiarire con il vostro input e l'output richiesto –