Czy można utworzyć maskę bitową od 1 do 64 bitów bez warunku w języku Java?

Question

Chcę napisać funkcję, która przyjmuje wartość z zakresu od 1 do 64, i zwraca odpowiednią "maskę bitową", z tak dużą liczbą bitów, ile wynosi wejście.

zacząłem tak:

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

Ale sobie sprawę, że daje zły stosunek wartości do 64:

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

Teraz mam to:

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

To raczej brzydki. Warianty mogą zmieniać przepływ sterowania, więc są droższe niż proste operacje arytmetyczne. Mógłbym po prostu wstępnie obliczyć maski i umieścić je w tablicy statycznej, ale dostęp do tablicy jest również droższy niż proste operacje arytmetyczne, prawdopodobnie nawet droższe niż warunkowe.

Czy istnieje rozsądny sposób zapisania tego bez warunku? Ten kod będzie działał z milionami czasu na sekundę, więc musi być szybki.

Answer 1

Próbowałem:

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

ale to wydaje się dać problem i = 0. Mój zastrzeżenie z Java nie posiadające ponownie niepodpisanych ints. Powyższe działa w c. Może powyższe działa w Javie 7, ponieważ "wartość" jest niepodpisana.

Jednakże, ponieważ nie trzeba zero, powyżej będzie działać dobrze dla ciebie, to znaczy wartości od 1 do 64.

Answer 2

Oto sposób to zrobić bez warunkowych:

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

W Javie 1L << bitsPerValueonly uses the six lowest-order bits z bitsPerValue, co oznacza, że ​​nazywając swoją pierwotną funkcję z bitsPerValue=64 jest taka sama jak nazywając go bitsPerValue=0. Wersja przedstawiam powyżej dba o to: kiedy bitsPerValue=64 wyrażenie zmniejsza się

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

Teraz, jeśli naprawdę będzie nazywając to „zillions razy na sekundę”, myślę, że najlepszą strategią jest do benchmark wszystkie warianty kodu, łącznie z tym z warunkami i tym z tabelą odnośników.

Answer 3

IMHO, dodając wymóg posiadania wartości 65-bitowe nie jest wystarczająco dobre. Po prostu użyłbym operacji OR do wygenerowania wartości, nie powinno to za bardzo zabrać. Tak:

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

widzę, że nie chcesz korzystać z tablic statycznych, ale byłoby to najszybszy sposób, który tylko wykorzystuje pamięć 64 * 8 bajtów. Co więcej, nie wydaje mi się, aby łatwo było uzyskać mały ślad pamięci i wystarczająco dobrą prędkość równą jednocześnie. Tak, na wszelki wypadek, najszybszym rozwiązaniem byłoby:

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

Innym możliwym rozwiązaniem jest użycie BigInteger na najnowszy, 64 „1 za bit, przypadek. Ale nie sądzę, że jest szybki i nie brzydki.