Java Language
Manipulacja bitami

Uwagi

Pakowanie / rozpakowywanie wartości w postaci fragmentów bitów

Wydajność pamięci często kompresuje wiele wartości w jedną pierwotną wartość. Może to być przydatne do przekazania różnych informacji do jednej zmiennej.

Na przykład, można spakować 3 bajty - takie jak kod koloru w RGB - w jedną int.

Pakowanie wartości

// Raw bytes as input
byte[] b = {(byte)0x65, (byte)0xFF, (byte)0x31};

// Packed in big endian: x == 0x65FF31
int x = (b[0] & 0xFF) << 16  // Red
      | (b[1] & 0xFF) <<  8  // Green
      | (b[2] & 0xFF) <<  0; // Blue

// Packed in little endian: y == 0x31FF65
int y = (b[0] & 0xFF) <<  0
      | (b[1] & 0xFF) <<  8
      | (b[2] & 0xFF) << 16;

Rozpakowywanie wartości

// Raw int32 as input
int x = 0x31FF65;

// Unpacked in big endian: {0x65, 0xFF, 0x31}
byte[] c = {
    (byte)(x >> 16),
    (byte)(x >>  8),
    (byte)(x & 0xFF)
};

// Unpacked in little endian: {0x31, 0xFF, 0x65}
byte[] d = {
    (byte)(x & 0xFF),
    (byte)(x >>  8),
    (byte)(x >> 16)
};

Sprawdzanie, ustawianie, czyszczenie i przełączanie poszczególnych bitów. Używanie długiej maski bitowej

Zakładając, że chcemy zmodyfikować bit n pierwotnej liczby całkowitej, i (bajt, krótki, char, int lub długi):

(i & 1 << n) != 0 // checks bit 'n'
i |= 1 << n;      // sets bit 'n' to 1
i &= ~(1 << n);   // sets bit 'n' to 0
i ^= 1 << n;      // toggles the value of bit 'n'

Używanie długiej / int / krótkiej / bajtu jako maski bitowej:

public class BitMaskExample {
    private static final long FIRST_BIT = 1L << 0;
    private static final long SECOND_BIT = 1L << 1;
    private static final long THIRD_BIT = 1L << 2;
    private static final long FOURTH_BIT = 1L << 3;
    private static final long FIFTH_BIT = 1L << 4;
    private static final long BIT_55 = 1L << 54;

    public static void main(String[] args) {
        checkBitMask(FIRST_BIT | THIRD_BIT | FIFTH_BIT | BIT_55);
    }

    private static void checkBitMask(long bitmask) {
        System.out.println("FIRST_BIT: " + ((bitmask & FIRST_BIT) != 0));
        System.out.println("SECOND_BIT: " + ((bitmask & SECOND_BIT) != 0));
        System.out.println("THIRD_BIT: " + ((bitmask & THIRD_BIT) != 0));
        System.out.println("FOURTh_BIT: " + ((bitmask & FOURTH_BIT) != 0));
        System.out.println("FIFTH_BIT: " + ((bitmask & FIFTH_BIT) != 0));
        System.out.println("BIT_55: " + ((bitmask & BIT_55) != 0));
    }
}

Wydruki

FIRST_BIT: true
SECOND_BIT: false
THIRD_BIT: true
FOURTh_BIT: false
FIFTH_BIT: true
BIT_55: true

który zapałki, które maskować mijaliśmy jak checkBitMask parametru: FIRST_BIT | THIRD_BIT | FIFTH_BIT | BIT_55 .

Wyrażając moc 2

Aby wyrazić potęgę 2 (2 ^ n) liczb całkowitych, można użyć operacji przesunięcia bitów, która pozwala jawnie określić n .

Składnia jest w zasadzie:

int pow2 = 1<<n;

Przykłady:

int twoExp4 = 1<<4; //2^4
int twoExp5 = 1<<5; //2^5
int twoExp6 = 1<<6; //2^6
...
int twoExp31 = 1<<31; //2^31

Jest to szczególnie przydatne przy definiowaniu stałych wartości, które powinny uwidocznić, że używana jest potęga 2 zamiast wartości szesnastkowych lub dziesiętnych.

int twoExp4 = 0x10; //hexadecimal
int twoExp5 = 0x20; //hexadecimal
int twoExp6 = 64; //decimal
...
int twoExp31 = -2147483648; //is that a power of 2?

Prostą metodą do obliczenia mocy int 2 będzie

int pow2(int exp){
    return 1<<exp;
}

Sprawdzanie, czy liczba jest potęgą 2

Jeśli liczba całkowita x jest potęgą 2, ustawiany jest tylko jeden bit, podczas gdy x-1 ma ustawione wszystkie bity później. Na przykład: 4 to 100 a 3 to 011 jako liczba binarna, która spełnia wyżej wymieniony warunek. Zero nie jest potęgą 2 i musi zostać wyraźnie sprawdzone.

boolean isPowerOfTwo(int x)
{
    return (x != 0) && ((x & (x - 1)) == 0);
}

Zastosowanie do przesunięcia w lewo i w prawo

Załóżmy, że mamy trzy rodzaje uprawnień: CZYTAĆ , PISAĆ i WYKONAĆ . Każde uprawnienie może wynosić od 0 do 7. (Załóżmy, że system liczb 4-bitowych)

ZASOBY = CZYTAJ WYKONAJ ZAPIS (12-bitowa liczba)

ZASOBY = 0100 0110 0101 = 4 6 5 (liczba 12 bitów)

Jak uzyskać uprawnienia (liczba 12 bitów), ustawione powyżej (liczba 12 bitów)?

0100 0110 0101

0000 0000 0111 (i)

0000 0000 0101 = 5

W ten sposób możemy uzyskać uprawnienia WYKONANIA ZASOBU . Teraz, co zrobić, jeśli chcemy uzyskać uprawnienia do odczytu zasobu?

0100 0110 0101

0111 0000 0000 (i)

0100 0000 0000 = 1024

Dobrze? Prawdopodobnie zakładasz to? Ale uprawnienia wynikają z 1024. Chcemy uzyskać tylko uprawnienia do odczytu zasobu. Nie martw się, dlatego mieliśmy operatorów zmiany biegów. Jeśli zobaczymy, uprawnienia do odczytu są 8 bitów za faktycznym wynikiem, więc jeśli zastosujemy jakiegoś operatora shift, który przeniesie uprawnienia do odczytu po prawej stronie wyniku? Co jeśli zrobimy:

0100 0000 0000 >> 8 => 0000 0000 0100 (Ponieważ jest to liczba dodatnia, więc zastąpiono je zerami, jeśli nie obchodzi cię znak, po prostu użyj niepodpisanego operatora prawej zmiany)

Teraz rzeczywiście mają uprawnienia do odczytu, która wynosi 4.

Teraz, na przykład, daje nam czytać, pisać, uprawnienia EXECUTE do zasobu, co możemy zrobić, aby uprawnienia do tego zasobu?

Weźmy najpierw przykład uprawnień binarnych. (Nadal zakładając 4-bitowy system liczbowy)

CZYTAJ = 0001

ZAPIS = 0100

WYKONANIE = 0110

Jeśli myślisz, że zrobimy po prostu:

READ | WRITE | EXECUTE , masz rację, ale nie do końca. Zobacz, co się stanie, jeśli wykonamy CZYTAJ | NAPISZ | WYKONAĆ

0001 | 0100 | 0110 => 0111

Ale uprawnienia są w rzeczywistości reprezentowane (w naszym przykładzie) jako 0001 0100 0110

Aby to zrobić, wiemy, że ODCZYT jest umieszczany 8 bitów za, WRITE jest umieszczany 4 bit za, a ZEZWOLENIA są umieszczane na końcu. System liczbowy używany dla uprawnień RESOURCE jest w rzeczywistości 12-bitowy (w naszym przykładzie). Może (będzie) być różny w różnych systemach.

(CZYTAJ << 8) | (NAPISZ << 4) | (WYKONAĆ)

0000 0000 0001 << 8 (CZYTAJ)

0001 0000 0000 (Przesunięcie w lewo o 8 bitów)

0000 0000 0100 << 4 (NAPISZ)

0000 0100 0000 (Przesunięcie w lewo o 4 bity)

0000 0000 0001 (WYKONAJ)

Teraz, jeśli dodamy wyniki powyższego przesunięcia, będzie to coś w rodzaju;

0001 0000 0000 (CZYTAJ)

0000 0100 0000 (NAPISZ)

0000 0000 0001 (WYKONAJ)

0001 0100 0001 (POZWOLENIA)

klasa java.util.BitSet

Od wersji 1.7 istnieje klasa java.util.BitSet, która zapewnia prosty i przyjazny dla użytkownika interfejs do przechowywania i manipulacji bitami:

final BitSet bitSet = new BitSet(8); // by default all bits are unset

IntStream.range(0, 8).filter(i -> i % 2 == 0).forEach(bitSet::set); // {0, 2, 4, 6}

bitSet.set(3); // {0, 2, 3, 4, 6}

bitSet.set(3, false); // {0, 2, 4, 6}

final boolean b = bitSet.get(3); // b = false

bitSet.flip(6); // {0, 2, 4}

bitSet.set(100); // {0, 2, 4, 100} - expands automatically

BitSet implementuje Clonable i Serializable , a pod maską wszystkie wartości bitów są przechowywane w polu long[] words , które rozwija się automatycznie.

Obsługuje także operacje logiczne na całym zestawie and , or , xor andNot :

bitSet.and(new BitSet(8));
bitSet.or(new BitSet(8));
bitSet.xor(new BitSet(8));
bitSet.andNot(new BitSet(8));

Zmiana podpisana vs niepodpisana

W Javie wszystkie prymitywy liczbowe są podpisane. Na przykład int zawsze reprezentuje wartości z [-2 ^ 31 - 1, 2 ^ 31], zachowując pierwszy bit do podpisania wartości - 1 dla wartości ujemnej, 0 dla wartości dodatniej.

Podstawowe operatory zmiany >> i << są operatorami podpisanymi. Zachowają znak wartości.

Ale programiści często używają liczb do przechowywania niepodpisanych wartości . W przypadku int oznacza to przesunięcie zakresu do [0, 2 ^ 32 - 1], aby mieć dwukrotnie większą wartość niż w przypadku int.

Dla tych zaawansowanych użytkowników bit znaku nie ma znaczenia. Dlatego Java dodał >>> , lewy klawisz shift, ignorując ten bit znaku.

                initial value:               4 (                                100)
     signed left-shift: 4 << 1               8 (                               1000)
    signed right-shift: 4 >> 1               2 (                                 10)
 unsigned right-shift: 4 >>> 1               2 (                                 10)
                initial value:              -4 (   11111111111111111111111111111100)
    signed left-shift: -4 << 1              -8 (   11111111111111111111111111111000)
   signed right-shift: -4 >> 1              -2 (   11111111111111111111111111111110)
unsigned right-shift: -4 >>> 1      2147483646 (    1111111111111111111111111111110)

Dlaczego nie ma <<< ?

Wynika to z zamierzonej definicji przesunięcia w prawo. Gdy wypełnia puste miejsca po lewej stronie, nie trzeba podejmować żadnej decyzji dotyczącej odrobiny znaku. W rezultacie nie ma potrzeby 2 różnych operatorów.

Zobacz to pytanie, aby uzyskać bardziej szczegółową odpowiedź.