representarse - signo magnitud java

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

Question

Probablemente esto sea bastante básico, pero para ahorrarme aproximadamente una hora, ¿alguien puede decirme cómo puede calcular la cantidad de bits necesarios para representar un entero positivo dado en Java?

Por ejemplo, tengo un decimal 11, (1011). Necesito obtener la respuesta, 4.

Pensé que si pudiera averiguar cómo poner todos los bits que no sean los más significativos en 0, y luego >>>, obtendría mi respuesta. Pero ... no puedo.

Answer 1

¡Esta funciona para mí!

int numberOfBitsRequired(int n) { return (int)Math.floor(Math.log(n)/Math.log(2)) + 1; }

Para incluir números negativos también, puede agregar un bit adicional y usarlo para especificar el signo.

public static int numberOfBitsRequiredSigned(int n) { return (int)Math.floor(Math.log(Math.abs(n))/Math.log(2)) + 2; }

Answer 2

¿Qué tal algo como esto?

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

Sé que estás buscando una manera de no usar los bucles, pero creo que esto es bastante estrecho hacia delante, de lo contrario, ya que los bits son solo dos a la potencia de un número.

Answer 3

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

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

Lo mismo existe para Long ...

[Editar] Si afeitar milisegundos es un problema aquí, Integer.numberOfLeadingZeros (int) es razonablemente eficiente, pero aún así realiza 15 operaciones ... Expandiendo una cantidad razonable de memoria (300 bytes, estática) puede reducir entre 1 y 8 Operaciones, dependiendo del rango de sus enteros.

Answer 4

Bueno, puedes contar cuántas veces te desplazas a la derecha antes de quedarte con solo cero:

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

Answer 5

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

Encuentre la base de registro 2 de un entero de N bits en operaciones O (lg (N))

Answer 6

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

Buena pena ... ¿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í hay una prueba simple para la velocidad de las diferentes 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);
}
}
}

La 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 que se quejan de la velocidad ... https://en.wikipedia.org/wiki/Program_optimization#Quotes .

Escriba primero el programa para que sea legible, luego averigüe dónde es lento y luego hágalo más rápido. Antes y después de optimizar prueba el cambio. Si el cambio no fue lo suficientemente grande para el costo de hacer que el código sea menos legible, no se moleste con el cambio.

Answer 7

La búsqueda binaria sobre los exponentes de 2 es más rápida que la solución de desplazamiento de bits ( respuesta con el voto más votado ), lo que podría ser valioso si los números son grandes (miles de dígitos decimales), conoce el máximo de bits disponibles y no desea generar las mesas:

 int minExpVal = 0;
int maxExpVal = 62;
int medExpVal = maxExpVal >> 1;
long medianValue = 0l;
while (maxExpVal - minExpVal > 1) {
medianValue = 1l << medExpVal;
if (value > medianValue) {
minExpVal = medExpVal;
} else {
maxExpVal = medExpVal;
}
medExpVal = (minExpVal + maxExpVal) >> 1;
}
return value == 1l << maxExpVal ? maxExpVal + 1 : maxExpVal;

Sin embargo, la solución que usa los ceros iniciales sería aún mucho más rápida:

return Long.SIZE - Long.numberOfLeadingZeros(value);

Puntos de referencia:

Leading zeros time is: 2 ms
BinarySearch time is: 95 ms
BitShift time is: 135 ms

Answer 8

Me gustaría agregar algunas otras alternativas, solo para completar:

1 BigInteger.valueOf(i).bitLength()

No muy rapido Además, BigInteger.bitLength() tiene errores y no es confiable (se corrige en Java7), ya que cuando se necesitan más de los bits Integer.MAX_VALUE se necesita un número de entrada extrañamente alto! 2^Integer.MAX_VALUE ]) los resultados se desbordan y aparecen números negativos para los próximos 2^(2*Integer.MAX_VALUE)-2^Integer.MAX_VALUE , que es un número tan alto que su cabeza podría explotar. 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 ).

2

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í la mitad de rápido que 32 - Integer.numberOfLeadingZeros(i); .

Answer 9

Mi Java está un poco oxidado, pero la respuesta independiente del lenguaje (si hay una función "log2" y una función "floor" disponible) sería:

numberOfBits = floor(log2(decimalNumber))+1

Suponiendo que "decimalNumber" es mayor que 0. Si es 0, solo necesita 1 bit.

Answer 10

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

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

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

Answer 11

Si estás tratando de evitar un bucle y te importa la velocidad, puedes usar un método como este:

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, por lo que primero si (valor <0) es un poco cuestionable. Los números negativos siempre establecen el bit más significativo, por lo que posiblemente se requiere la palabra completa para representarlos. Adaptar ese comportamiento si te importa.

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

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

Answer 12

Tomando los dos registros basados ​​en el número, se reportará la cantidad de bits necesarios para almacenarlo.

Answer 13

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

Por supuesto, esto solo funciona para enteros positivos.