Java Language
Bitmanipulation

Anmärkningar

Packning / packning av värden som bitfragment

Det är vanligt att minnesprestanda komprimerar flera värden till ett enda primitivt värde. Detta kan vara användbart för att skicka olika information till en enda variabel.

Till exempel kan man packa 3 byte - till exempel färgkod i RGB - i en enda int.

Packa värdena

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

Packa upp värdena

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

Kontrollera, ställa in, rensa och växla enskilda bitar. Med en lång bitmask

Förutsatt att vi vill modifiera bit n av ett heltal primitivt, i (byte, kort, char, int eller lång):

(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'

Använda lång / int / kort / byte som en bitmask:

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

Grafik

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

som matchar den masken som vi passerade som checkBitMask parameter: FIRST_BIT | THIRD_BIT | FIFTH_BIT | BIT_55 .

Uttrycker kraften i 2

För att uttrycka kraften i 2 (2 ^ n) heltal kan man använda en bitshift-operation som gör det möjligt att uttryckligen specificera n .

Syntaxen är i princip:

int pow2 = 1<<n;

Exempel:

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

Detta är särskilt användbart när man definierar konstanta värden som ska göra det uppenbart att en effekt på 2 används istället för att använda hexadecimala eller decimalvärden.

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

En enkel metod för att beräkna int-kraften på 2 skulle vara

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

Kontrollera om ett tal är en effekt på 2

Om ett heltal x är en effekt på 2 ställs endast en bit in, medan x-1 har alla bitar inställda efter det. Till exempel: 4 är 100 och 3 är 011 som binärt tal, vilket uppfyller ovannämnda villkor. Noll är inte en kraft på 2 och måste kontrolleras uttryckligen.

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

Användning för vänster- och högerväxling

Låt oss anta att vi har tre slags behörigheter, LÄS , SKRIFTLÄGG och UTFÖR . Varje tillstånd kan variera från 0 till 7. (Låt oss anta 4-bitarssystem)

KONSEKVENS = LÄS SKRIFT UTFÖR (12 bitars nummer)

RÅDGIVNING = 0100 0110 0101 = 4 6 5 (12 bitars nummer)

Hur kan vi få (12 bitars antal) behörigheter, inställda ovan (12 bitars nummer)?

0100 0110 0101

0000 0000 0111 (&)

0000 0000 0101 = 5

Så det är så vi kan få EXECUTE- behörigheterna till HÄLSNINGEN . Vad händer nu om vi vill få LÄS- behörigheter för HÄLSNINGEN ?

0100 0110 0101

0111 0000 0000 (&)

0100 0000 0000 = 1024

Rätt? Antar du förmodligen detta? Men behörigheterna resulterade i 1024. Vi vill bara få LÄS-behörigheter för resursen. Oroa dig inte, det var därför vi hade skiftoperatörerna. Om vi ser, är LÄS-behörigheterna 8 bitar efter det faktiska resultatet, så om du använder någon skiftoperatör, vilket kommer att få LÄS-behörigheterna till höger om resultatet? Tänk om vi gör:

0100 0000 0000 >> 8 => 0000 0000 0100 (Eftersom det är ett positivt nummer så ersatt med 0: er, om du inte bryr dig om skylt, använd bara osignerad högerskiftoperatör)

Vi har nu faktiskt LÄS- behörigheterna som är 4.

Nu får vi till exempel LÄS , SKRIFT , UTFÖR behörigheter för en HÄLSNING , vad kan vi göra för att göra behörigheter för denna HÄLSNING ?

Låt oss först ta exemplet med binära behörigheter. (Antar fortfarande 4-bitarssystem)

LÄS = 0001

SKRIFT = 0100

EXECUTE = 0110

Om du tänker att vi helt enkelt kommer att göra:

READ | WRITE | EXECUTE , du har något rätt men inte exakt. Se vad som kommer att hända om vi kommer att utföra LÄS | SKRIVA | KÖR

0001 | 0100 | 0110 => 0111

Men behörigheterna representeras faktiskt (i vårt exempel) som 0001 0100 0110

Så för att göra detta, vet vi att READ är placerat 8 bitar bakom, WRITE är placerat 4 bitar bakom och PERMISSIONS placeras till sist. Talssystemet som används för RÄTTSA- behörigheter är faktiskt 12 bitar (i vårt exempel). Det kan (kommer) vara annorlunda i olika system.

(LÄS << 8) | (SKRIV << <<) | (KÖR)

0000 0000 0001 << 8 (LÄS)

0001 0000 0000 (vänster skift med 8 bitar)

0000 0000 0100 << 4 (SKRIFT)

0000 0100 0000 (vänster skift med 4 bitar)

0000 0000 0001 (EXECUTE)

Om vi nu lägger till resultaten av ovanstående förskjutning, kommer det att vara något liknande;

0001 0000 0000 (LÄS)

0000 0100 0000 (SKRIFT)

0000 0000 0001 (EXECUTE)

0001 0100 0001 (PERMISSIONS)

java.util.BitSet klass

Sedan 1.7 finns det en java.util.BitSet- klass som ger enkel och användarvänlig bitlagrings- och manipuleringsgränssnitt:

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 implementerar Clonable och Serializable , och under huven lagras alla bitvärden i long[] words som expanderar automatiskt.

Den stöder också heluppsatta logiska operationer and , or , xor och och andNot :

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

Signerad vs osignerad skift

I Java är alla numret primitiva signerade. Till exempel representerar en int alltid värden från [-2 ^ 31 - 1, 2 ^ 31] och håller den första biten för att underteckna värdet - 1 för negativt värde, 0 för positivt.

Grundläggande skiftoperatörer >> och << är signerade operatörer. De kommer att bevara värdet.

Men det är vanligt att programmerare använder siffror för att lagra osignerade värden . För en int betyder det att flytta intervallet till [0, 2 ^ 32 - 1] för att ha dubbelt så mycket värde som med ett signerat int.

För dessa kraftanvändare har biten för tecken ingen mening. Därför lägger Java till >>> , en vänsterförskjutningsoperatör, utan att bortse från den skyltbiten.

                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)

Varför finns det ingen <<< ?

Detta kommer från den avsedda definitionen av högerförskjutning. När det fyller de tomma platserna till vänster, finns det inget beslut att fatta när det gäller skyltbiten. Som en följd av detta finns det inget behov av två olika operatörer.

Se den här frågan för ett mer detaljerat svar.