¿Encontrar la cantidad de bits necesarios para representar un entero positivo en binario?

Question

Esto es probablemente bastante básico, pero para ahorrarme una hora más o menos de dolor ¿alguien puede decirme cómo se puede calcular la cantidad de bits necesarios para representar un entero positivo dado en Java?

p. Ej. Obtengo un decimal 11, (1011). Necesito obtener la respuesta, 4.

Pensé que si pudiera encontrar la manera de establecer todos los bits que no sean el más significativo en 0, y luego >>>, obtendría mi respuesta. Pero ... no puedo.

Answer 1

Bueno, sólo puede contar el número de veces que se desplaza a la derecha antes de que uno se queda con sólo cero:

int value = 11; 
int count = 0; 
while (value > 0) { 
    count++; 
    value = value >> 1; 
} 

Answer 2

Mi Java es un poco oxidado, pero la respuesta independiente del idioma (si hay una función "log 2" y una función de "piso" disponible) serían:

numberOfBits = floor(log2(decimalNumber))+1 

Suponiendo que "decimalNumber" es mayor que 0. Si es 0, sólo necesita 1 bit.

Answer 3

Integer.toBinaryString (número) .length();

Buen dolor ... ¿por qué los votos a la baja?

public class Main 
{ 
    public static void main(final String[] argv) 
    { 
     System.out.println(Integer.toBinaryString(0).length()); 
     System.out.println(Integer.toBinaryString(1).length()); 
     System.out.println(Integer.toBinaryString(2).length()); 
     System.out.println(Integer.toBinaryString(3).length()); 
     System.out.println(Integer.toBinaryString(4).length()); 
     System.out.println(Integer.toBinaryString(5).length()); 
     System.out.println(Integer.toBinaryString(6).length()); 
     System.out.println(Integer.toBinaryString(7).length()); 
     System.out.println(Integer.toBinaryString(8).length()); 
     System.out.println(Integer.toBinaryString(9).length()); 
    } 
} 

Salida:

1 
1 
2 
2 
3 
3 
3 
3 
4 
4 

Aquí está una prueba simple para la velocidad de las diversas soluciones:

public class Tester 
{ 
    public static void main(final String[] argv) 
    { 
     final int size; 
     final long totalA; 
     final long totalB; 
     final long totalC; 
     final long totalD; 

     size = 100000000; 

     totalA = test(new A(), size); 
     totalB = test(new B(), size); 
     totalC = test(new C(), size); 
     totalD = test(new D(), size); 

     System.out.println(); 
     System.out.println("Total D = " + totalD + " ms"); 
     System.out.println("Total B = " + totalB + " ms"); 
     System.out.println("Total C = " + totalC + " ms"); 
     System.out.println("Total A = " + totalA + " ms"); 

     System.out.println(); 
     System.out.println("Total B = " + (totalB/totalD) + " times slower"); 
     System.out.println("Total C = " + (totalC/totalD) + " times slower"); 
     System.out.println("Total A = " + (totalA/totalD) + " times slower"); 
    } 

    private static long test(final Testable tester, 
          final int  size) 
    { 
     final long start; 
     final long end; 
     final long total; 

     start = System.nanoTime(); 
     tester.test(size); 
     end = System.nanoTime(); 
     total = end - start; 

     return (total/1000000); 
    } 

    private static interface Testable 
    { 
     void test(int size); 
    } 

    private static class A 
     implements Testable 
    { 
     @Override 
     public void test(final int size) 
     { 
      int value; 

      value = 0; 

      for(int i = 1; i < size; i++) 
      { 
       value += Integer.toBinaryString(i).length(); 
      } 

      System.out.println("value = " + value); 
     }  
    } 

    private static class B 
     implements Testable 
    { 
     @Override 
     public void test(final int size) 
     { 
      int total; 

      total = 0; 

      for(int i = 1; i < size; i++) 
      { 
       int value = i; 
       int count = 0; 

       while (value > 0) 
       { 
        count++; 
        value >>= 1; 
       } 

       total += count; 
      } 

      System.out.println("total = " + total); 
     }  
    } 

    private static class C 
     implements Testable 
    { 
     @Override 
     public void test(final int size) 
     { 
      int total; 
      final double log2; 

      total = 0; 
      log2 = Math.log(2); 

      for(int i = 1; i < size; i++) 
      { 
       final double logX; 
       final double temp; 

       logX = Math.log(i); 
       temp = logX/log2;     
       total += (int)Math.floor(temp) + 1; 
      } 

      System.out.println("total = " + total); 
     }  
    } 

    private static class D 
     implements Testable 
    { 
     @Override 
     public void test(final int size) 
     { 
      int total; 

      total = 0; 

      for(int i = 1; i < size; i++) 
      { 
       total += 32-Integer.numberOfLeadingZeros(i); 
      } 

      System.out.println("total = " + total); 
     }  
    } 
} 

salida en mi máquina es:

value = -1729185023 
total = -1729185023 
total = -1729185023 
total = -1729185023 

Total D = 118 ms 
Total B = 1722 ms 
Total C = 4462 ms 
Total A = 5704 ms 

Total B = 14 times slower 
Total C = 37 times slower 
Total A = 48 times slower 

Para aquellos de ustedes quejándose de spee d ... https://en.wikipedia.org/wiki/Program_optimization#Quotes.

Primero, escribe el programa para que sea legible, luego averigua dónde está lento y luego hazlo más rápido. Antes y después de optimizar, pruebe el cambio. Si el cambio no fue lo suficientemente grande como para hacer que el código sea menos legible, no se moleste con el cambio.

Answer 4

Tomar los dos registros basados ​​en el número informará el número de bits necesarios para almacenarlo.

Answer 5

Bueno, la respuesta es bastante simple. Si usted tiene un valor int:

int log2(int value) { 
    return Integer.SIZE-Integer.numberOfLeadingZeros(value); 
} 

El mismo existe para largo ...

[Editar] Si el afeitado milisegundos es un problema aquí, Integer.numberOfLeadingZeros (int) es razonablemente eficiente, pero todavía realiza 15 operaciones ... Al expandir una cantidad razonable de memoria (300 bytes, estática) puede afeitar eso a entre 1 y 8 operaciones, dependiendo del rango de sus enteros.

Answer 6

Esto está en C, pero sospecho que podría convertir a Java con bastante facilidad:

Find the log base 2 of an N-bit integer in O(lg(N)) operations

Answer 7

Si usted está tratando de evitar un bucle y se preocupan por la velocidad, se puede utilizar un método como esto:

int value = ...; 
int count = 0; 
if(value < 0) { value = 0; count = 32; } 
if(value >= 0x7FFF) { value >>= 16; count += 16; } 
if(value >= 0x7F) { value >>= 8; count += 8; } 
if(value >= 0x7) { value >>= 4; count += 4; } 
if(value >= 0x3) { value >>= 2; count += 2; } 
if(value >= 0x1) { value >>= 1; count += 1; } 

Java no tiene enteros sin signo, de modo que en primer lugar si (valor < 0) es un poco cuestionable. Los números negativos siempre establecen el bit más significativo, por lo que podría requerirse la palabra completa para representarlos. Adapta ese comportamiento si te importa.

Por cierto, para manejar un número entero de 64 bits, reemplace la línea si (valor < 0) con estos dos:

if(value < 0) { value = 0; count = 64; } 
if(value >= 0x7FFFFFFF) { value >>= 32; count += 32; } 

Answer 8

(int) Math.ceil((Math.log(n)/Math.log(2)) 

Por supuesto esto sólo funciona para números enteros positivos.

Answer 9

Para valores no negativos, probablemente la respuesta más directa es:

java.math.BigDecimal.valueOf(value).bitLength() 

(Para los números negativos se le dará la longitud de bit de uno menos que el valor absoluto, en lugar de infinito que cabría esperar de . de dos notación de complemento)

Answer 10

me gustaría añadir algunas otras alternativas, por el simple hecho de exhaustividad:

BigInteger.valueOf(i).bitLength()

No muy rápido. Además, BigInteger.bitLength() está dañado y no confiable (fijado en Java7), ya que cuando se necesitan más de Integer.MAX_VALUE bits (se necesita un número de entrada anormalmente alto [como 1 Integer.MAX_VALUE veces desplazado a la izquierda], el resultado se desborda y aparecen números negativos para los siguientes números 2^(2*Integer.MAX_VALUE)-2^Integer.MAX_VALUE, que es un número tan alto que podría explotar tu cabeza. Tenga en cuenta que se estima que el universo contiene unos 10^80 átomos; ese número es 2^4G (G como en Giga, 1024*1024*1024).

static int neededBits(int i) 
{ 
    assert i > 0; 
    int res; 
    int sh; 
    res = ((i > 0xFFFF) ? 1 : 0) << 4; 
    i >>= res; 
    sh = ((i > 0xFF) ? 1 : 0) << 3; 
    i >>= sh; 
    res |= sh; 
    sh = ((i > 0xF) ? 1 : 0) << 2; 
    i >>= sh; 
    res |= sh; 
    sh = ((i > 0x3) ? 1 : 0) << 1; 
    i >>= sh; 
    res |= sh; 
    res |= (i >> 1); 
    return res + 1; 
} 

Una solución muy rápida, pero aún así medio tan rápido como Ye Olde 32 - Integer.numberOfLeadingZeros(i);.

Answer 11

¿Qué pasa algo como esto:

public static int getNumberOfBits(int N) { 
    int bits = 0; 
     while(Math.pow(2, bits) <= N){ 
      bits++; 
     } 
     return bits; 
} 

sé que busca una manera de no utilizar bucles, pero siento que esto es bastante estrecho hacia adelante de lo contrario ya los bits son sólo dos a la potencia de un número.