¿Puedo crear una máscara de bits de 1 a 64 bits sin condicional en Java?

Question

Quiero escribir una función que toma un int entre 1 y 64, y devuelve una "máscara de bits" apropiada, con tantos 1 bits como la entrada.

empecé así:

/** Computes a bitmaks */ 
private static long mask(final int bitsPerValue) { 
    return (1L << bitsPerValue) - 1L; 
} 

pero se dio cuenta que le da el valor incorrecto para el 64:

(1L << 64) - 1L == 1L - 1L == 0 

Ahora tengo unas pocas cosas:

/** Computes a bitmaks */ 
private static long mask(final int bitsPerValue) { 
    return (bitsPerValue == 64) ? -1 : ((1L << bitsPerValue) - 1L); 
} 

Es bastante feo. Y los condicionales pueden cambiar el flujo de control, por lo que son más caros que las operaciones aritméticas simples. Podría precomputar las máscaras y ponerlas en una matriz estática, pero el acceso a la matriz también es más costoso que las simples operaciones aritméticas, probablemente incluso más costoso que el condicional.

¿Hay alguna manera razonable de escribir esto sin un condicional? Este código va a correr por billones de tiempo por segundo, así que tiene que ser rápido.

Answer 1

me trataron:

long value = 0xffffffffffffffffl >>> (64 - i); // that's ef ef ef... el. 

pero esto parece dar un problema con i = 0. Mi queja con Java no tener enteros sin signo de nuevo. Lo anterior funciona en c. Tal vez lo anterior funcionará en Java 7, dado que 'valor' no está firmado.

Sin embargo, puesto que no es necesario cero, lo anterior va a funcionar bien para usted, es decir, valores de 1 a 64.

Answer 2

Aquí es una manera de hacerlo sin condicionales:

private static long mask(final int bitsPerValue) { 
    return ((1L << bitsPerValue) - (bitsPerValue >> 6)) - 1L; 
} 

En Java, 1L << bitsPerValueonly uses the six lowest-order bits de bitsPerValue, lo que significa que llamar a su función original con bitsPerValue=64 es lo mismo que llamar con bitsPerValue=0. La versión que presento anteriormente se encarga de que: cuando bitsPerValue=64, la expresión se reduce a

(1L - 1L) - 1L == -1L 

Ahora, si lo que realmente va a estar llamando a esto "millones y millones de veces por segundo", creo que la mejor estrategia es a benchmark todas las variantes del código, incluyendo el que tiene condicionales y el que tiene la tabla de búsqueda.

Answer 3

en mi humilde opinión, la adición de un requisito de tener un valor de 65 bits no es lo suficientemente bueno. Solo usaría la operación OR para generar valor, no debería tomar mucho. De esta manera:

private static long mask(final int bitsPerValue) { 
    long mask = 1; 
    long value = 0; 
    for (int i=0; i<bitsPerValue; i++) { 
    value = value | mask; 
    mask = mask << 1; 
    } 
    return value; 
} 

veo que usted no desea utilizar matrices estáticas, pero sería la forma más rápida, que sólo utiliza la memoria 64 * 8 bytes. Además, no creo que sea fácil lograr una huella de memoria pequeña y una velocidad suficientemente buena simultáneamente. Así que, por si acaso, el enfoque más rápido sería:

long valarray[] = new long[64]; 

private static long[] generateValues() { 
    long mask = 1; 
    long value = 0; 
    for (int i=0; i<64; i++) { 
    value = value | mask; 
    mask = mask << 1; 

    valarray[i] = value; 
    } 
    return valarray; 
} 

private static long[] mask(final int bitsPerValue) { 
    return valarray[bitsPerValue-1]; 
} 

Otra posibilidad es utilizar BigInteger para la última, 64 'de 1 bit, caso. Pero no creo que sea rápido y no feo.