Qué bit está activado por un entero en Java

Question

He escrito este código para comprobar qué bits son el de un entero (si está representado en binario) en 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; 
} 

El código escrito anterior funciona correctamente. Pero tiene un bucle que se ejecuta 32 veces (en Java el entero tiene 32 bits de longitud). Quiero minimizar esta complejidad. Por favor comparte la mejor solución. Gracias por adelantado.

Answer 1

La complejidad es O (1), por lo que no hay mucho que "minimizar" allí.

Su código está bien ... aquí se refactoriza un poco.

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; 
} 

Por cierto, ¿ha considerado el uso de un BitSet?

Answer 2

32 bucles suena bien para esta aplicación. Puede usar un StringBuffer en lugar de una lista si desea recopilar los dígitos más rápido.

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

Mejorar O(1) código parece trivial, pero este código es una ligera mejora:

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; 

En lugar de hacer todas las comparaciones de 32 bits, este código terminará tan pronto como el último bit se ha contado. Es mucho más eficiente para enteros que están escasamente poblados con 1 sy no menos eficiente para enteros que están muy poblados.

Answer 4

Dado que conoce la longitud exacta del número entero, le recomendaría usar un bool[] en su lugar. Sin embargo, no hay mucho que puedas hacer sobre la complejidad. Es lo más rápido que puede y el JIT probablemente va a desenrollar el circuito de este código de todos modos.

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

Puede utilizar una máscara de bits para intentar reducir los tiempos a través del ciclo. Agrega algunas operaciones pero potencialmente hacer la mitad del bucle:.

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; 
} 

Potencialmente, esto podría aumentar el tiempo en función de los datos que entran

También puede reducir el bucle a la mitad para hacer dos bits a la vez:

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; 
}