Trovare l'ordine più alto 1 in un primitivo Java

Question

Ho bisogno di trovare l'ordine più alto 1 in alcuni long, ints e short in Java. Ad esempio, se avessi un carattere simile a 00110101, ho bisogno di un metodo che restituirà 2 (indice del più alto ordine 1).

Ora, so che si può fare questo usando un ciclo for come:

for(int i=0; i<8; i++) 
    if((x & 1<<i) != 0) return i; 
return -1; 

, ma questo è il modo più lento di quello che voglio fare. So che le moderne CPU hanno istruzioni che lo fanno su chip, quindi voglio sapere come posso effettuare una chiamata a questo piuttosto che avere un ciclo esplicito.

MODIFICA: punti bonus se è possibile restituire gli indici di tutti quelli nella primitiva.

Grazie.

Answer 1

Integer.numberOfLeadingZeros(i) + 1

Questo metodo utilizza un bel approccio divide et impera, copiato qui per la tua opinione:

public static int numberOfLeadingZeros(int i) { 
    // HD, Figure 5-6 
    if (i == 0) 
     return 32; 
    int n = 1; 
    if (i >>> 16 == 0) { n += 16; i <<= 16; } 
    if (i >>> 24 == 0) { n += 8; i <<= 8; } 
    if (i >>> 28 == 0) { n += 4; i <<= 4; } 
    if (i >>> 30 == 0) { n += 2; i <<= 2; } 
    n -= i >>> 31; 
    return n; 
} 

Answer 2

Non so se si preme un'istruzione della CPU, ma so che sarà molto più veloce se si srotola il ciclo e si utilizza il mascheramento di bit esplicito.

Inoltre, un char non è 8 bit ... Penso che potresti aver inteso un byte.

Answer 3

La pagina "Bit Twiddling Hacks" contiene molti hack di bit. Uno è come trovare il index of the highest order bit.

Answer 4

Per quanto posso dire, il Pentium e gli amici non hanno un'istruzione già pronta per questo. Quindi la cosa da fare è usare un algoritmo decente.

La chiave per ottenere rapidamente la risposta è utilizzare una ricerca binaria. Stai guardando un long con 64 bit? 6 confronti ti daranno il tuo bit più alto, ogni volta.

Il codice funziona su un grosso albero brutto di 64 se istruzioni, ma solo una frazione di quelle verrà mai eseguita, quindi il runtime è buono.

Se è necessario codice di esempio, posso farlo. Ma preferirei di no.

Answer 5

Non ho idea se questo è più veloce. Ma non ha loop.

if(i==0) return -1; 

highest=0; 
if (i & 0xffff0000) 
{ 
    highest+=16; 
    i>>=16; 
} 
if (i & 0xff00) 
{ 
    highest+=8; 
    i>>=8; 
} 
if (i & 0xf0) 
{ 
    highest+=4; 
    i>>=4; 
} 
if (i & 0xC) 
{ 
    highest+=2; 
    i>>=2; 
} 
if (i & 0x2) 
{ 
    highest+=1; 
} 

return highest; 

Answer 6

Java viene compilato in bytecode indipendente dalla piattaforma, non si può pretendere il supporto per le istruzioni della CPU. Altrimenti il ​​tuo codice o Integer.highestOneBit() dovrebbe essere il più veloce possibile.

Answer 7

E 'qualcosa del genere che cerchi?

System.out.println("00110101".indexOf("1"));