Quale bit è avanti per un intero in Java

Question

Ho scritto questo codice per controllare che i bit sono su di un numero intero (se rappresentati in binario) in Java:

public static List<String> list(int val) 
{ 
    List<String> dummyList = new ArrayList<String>(); 

    int bit = 1; 
    int x; 

    for(int i=0; i<32; i++) 
    { 
     x = bit; 
     if((x&val)!=0) 
      dummyList.add(String.valueOf(i+1)); 
     bit = bit << 1; 
    } 

    return dummyList; 
} 

Il codice sopra scritto funzioni. Ma ha un ciclo che gira 32 volte (nel numero intero Java è lungo 32 bit). Voglio minimizzare questa complessità. Si prega di condividere la soluzione migliore. Grazie in anticipo.

Answer 1

La complessità è O (1), quindi non c'è molto da "minimizzare" lì.

Il tuo codice è ok .. qui viene leggermente rifattorizzato.

public static List<String> list(int val) { 
    List<String> dummyList = new ArrayList<String>(); 
    for (int i = 0; i < 32; i++) 
     if ((1 << i & val) != 0) 
      dummyList.add("" + (i+1)); 
    return dummyList; 
} 

Btw, avete considerato utilizzando un BitSet?

Answer 2

32 loop validi per questa applicazione. Puoi usare un StringBuffer invece di List se vuoi raccogliere più velocemente le cifre.

public static String list(int val) 
{ 
    StringBuffer dummyList = new StringBuffer(); 

    int bit = 1; 
    int x; 

    for(int i=0; i<32; i++) 
    { 
     x = bit; 
     dummyList.append((x&val) ? '1' : '0'); 
     bit = bit << 1; 
    } 

    return dummyList.toString(); 
} 

Answer 3

Migliorare O(1) codice sembra banale, ma questo codice è un leggero miglioramento:

public static List<String> list(int val) { 
    List<String> dummyList = new ArrayList<String>(); 
    for (int i=0; val!=0 && i<32; ++i){ 
     if ((1 << i & val) != 0) { 
      dummyList.add("" + (i+1)); 
      val &= val -1; // unset the last set bit (current bit) 
     }     // causes loop to end early when all bits are counted 
    } 
    return dummyList; 

Piuttosto che fare tutti i 32 confronti di bit, questo codice si concluderà non appena è stato contato l'ultimo bit. È molto più efficiente per i numeri interi che sono scarsamente popolati con 1 se non meno efficienti per i numeri interi che sono altamente popolati.

Answer 4

Poiché si conosce la lunghezza esatta del numero intero, si consiglia di utilizzare un bool[]. Non c'è molto che tu possa fare per la complessità. È veloce come si può ottenere e il JIT probabilmente sta per srotolare il ciclo di questo codice comunque.

public static bool[] list(int val) 
{ 
    bool[] a = new bool[32]; 
    for(int i=0; i<32; i++) 
    { 
     a[i] = ((1 << i) & val) != 0; 
    } 
    return a; 
} 

Answer 5

È possibile utilizzare una maschera di bit per cercare di ridurre i tempi attraverso il ciclo. Si aggiunge un paio di operazioni, ma potenzialmente fare la metà del looping:.

public static List<String> list(int val) { 
    List<String> dummyList = new ArrayList<String>(); 
    int loop = 32; 

    // Mask the 16 MSB if all are zero only loop on the 16 LSB 
    if((val & 0xFFFF0000) == 0){ 
     loop = 16; 
    } 

    int bit = 1; 
    int x; 

    for (int i = 0; i < loop; i++) { 
     x = bit; 
     if ((x & val) != 0) { 
      dummyList.add(String.valueOf(i + 1)); 
     } 
     bit <<= 1; 
    } 

    return dummyList; 
} 

Questo potenzialmente potrebbe aumentare il tempo a seconda dei dati in arrivo

Si può anche ridurre il ciclo a metà facendo due bit alla volta:

public static List<String> list(int val) { 
    List<String> dummyList = new ArrayList<String>(); 

    int bit = 3; 
    int x; 

    for (int i = 0; i < 32; i += 2) { 
     x = (bit & val); 
     switch (x) { 
      case 1: 
       dummyList.add(String.valueOf(i + 1)); 
       break; 
      case 2: 
       dummyList.add(String.valueOf(i+2)); 
       break; 
      case 3: 
       dummyList.add(String.valueOf(i+1)); 
       dummyList.add(String.valueOf(i+2)); 
       break; 
      default: 
     } 
     val >>= 2; 
    } 

    return dummyList; 
}