Java Language
Bitmanipulatie

Opmerkingen

Waarden inpakken / uitpakken als bitfragmenten

Het is gebruikelijk dat geheugenprestaties meerdere waarden comprimeren tot een enkele primitieve waarde. Dit kan handig zijn om verschillende informatie door te geven aan een enkele variabele.

Men kan bijvoorbeeld 3 bytes - zoals kleurcode in RGB - in een enkele int verpakken.

De waarden verpakken

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

De waarden uitpakken

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

Individuele bits controleren, instellen, wissen en schakelen. Lang als bitmasker gebruiken

Ervan uitgaande dat we bit n van een geheel getal primitief, i (byte, kort, char, int of lang) willen wijzigen:

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

Long / int / short / byte gebruiken als bitmasker:

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

prints

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

die wedstrijden maskeren we doorgegeven als checkBitMask parameter: FIRST_BIT | THIRD_BIT | FIFTH_BIT | BIT_55 .

De kracht van 2 uitdrukken

Voor het uitdrukken van de kracht van 2 (2 ^ n) gehele getallen, kan men een bitshift-bewerking gebruiken waarmee de n expliciet kan worden gespecificeerd.

De syntaxis is in principe:

int pow2 = 1<<n;

Voorbeelden:

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

Dit is vooral handig bij het definiëren van constante waarden die duidelijk moeten maken dat een macht van 2 wordt gebruikt in plaats van hexadecimale of decimale waarden te gebruiken.

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

Een eenvoudige methode om de int power van 2 te berekenen zou zijn

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

Controleren of een getal een macht van 2 is

Als een geheel getal x een macht van 2 is, wordt slechts één bit ingesteld, terwijl voor x-1 alle bits daarna worden ingesteld. Bijvoorbeeld: 4 is 100 en 3 is 011 als binair getal, dat voldoet aan de bovengenoemde voorwaarde. Nul is geen macht van 2 en moet expliciet worden gecontroleerd.

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

Gebruik voor links en rechts verschuiven

Laten we aannemen dat we drie soorten machtigingen hebben: LEZEN , SCHRIJVEN en UITVOEREN . Elke toestemming kan variëren van 0 tot 7. (Laten we aannemen dat het systeem met 4 bits is)

RESOURCE = LEES SCHRIJF UITVOEREN (12 bit nummer)

RESOURCE = 0100 0110 0101 = 4 6 5 (12 bit nummer)

Hoe kunnen we de machtigingen (12 bitnummer) krijgen die hierboven zijn ingesteld (12 bitnummer)?

0100 0110 0101

0000 0000 0111 (&)

0000 0000 0101 = 5

Dit is dus hoe we de UITVOERINGSrechten van de RESOURCE kunnen krijgen. Wat als we nu LEES- machtigingen van de RESOURCE willen krijgen?

0100 0110 0101

0111 0000 0000 (&)

0100 0000 0000 = 1024

Rechtsaf? Neem je dit waarschijnlijk aan? Maar machtigingen worden verkregen in 1024. We willen alleen LEES-machtigingen voor de bron krijgen. Maak je geen zorgen, daarom hadden we de shift-operators. Als we zien, zijn READ-machtigingen 8 bits achter op het werkelijke resultaat, dus als u een shift-operator toepast, die dan LEES-rechten helemaal rechts van het resultaat brengt? Wat als we doen:

0100 0000 0000 >> 8 => 0000 0000 0100 (Omdat het een positief getal is, dus vervangen door 0's, als u niet om teken geeft, gebruikt u gewoon de niet-ondertekende operator voor rechts verschuiven)

We hebben nu eigenlijk de LEES- machtigingen die 4 is.

Nu krijgen we bijvoorbeeld de machtigingen LEZEN , SCHRIJVEN , UITVOEREN voor een RESOURCE , wat kunnen we doen om machtigingen voor deze RESOURCE te maken ?

Laten we eerst het voorbeeld nemen van binaire machtigingen. (We gaan nog steeds uit van een 4-bits nummerensysteem)

LEZEN = 0001

SCHRIJF = 0100

UITVOEREN = 0110

Als u denkt dat we gewoon zullen doen:

READ | WRITE | EXECUTE , u hebt enigszins gelijk maar niet precies. Kijk, wat gebeurt er als we LEES | gaan uitvoeren SCHRIJF | UITVOEREN

0001 | 0100 | 0110 => 0111

Maar machtigingen worden eigenlijk (in ons voorbeeld) weergegeven als 0001 0100 0110

Om dit te doen, weten we dat READ 8 bits achter is geplaatst, WRITE 4 bits achter is geplaatst en TOESTEMMINGEN als laatste is geplaatst. Het nummersysteem dat wordt gebruikt voor RESOURCE- machtigingen is eigenlijk 12 bit (in ons voorbeeld). Het kan (zal) anders zijn in verschillende systemen.

(LEES << 8) | (SCHRIJF << 4) | (UITVOEREN)

0000 0000 0001 << 8 (LEZEN)

0001 0000 0000 (linker shift met 8 bits)

0000 0000 0100 << 4 (SCHRIJVEN)

0000 0100 0000 (links verschuiven met 4 bits)

0000 0000 0001 (UITVOEREN)

Als we nu de resultaten van bovenstaande verschuiving toevoegen, zal het zoiets zijn;

0001 0000 0000 (LEES)

0000 0100 0000 (SCHRIJVEN)

0000 0000 0001 (UITVOEREN)

0001 0100 0001 (VERGUNNINGEN)

java.util.BitSet-klasse

Sinds 1.7 is er een java.util.BitSet- klasse die een eenvoudige en gebruikersvriendelijke interface voor bitopslag en -manipulatie biedt:

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 implementeert Clonable en Serializable en onder de motorkap worden alle bitwaarden opgeslagen in een long[] words Clonable dat automatisch wordt uitgebreid.

Het ondersteunt ook hele logische bewerkingen and , or , xor , andNot :

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

Ondertekend versus niet-ondertekende dienst

In Java zijn alle nummerprimitieven ondertekend. Een int vertegenwoordigt bijvoorbeeld altijd waarden van [-2 ^ 31 - 1, 2 ^ 31], waarbij het eerste bit de waarde - 1 voor negatieve waarde, 0 voor positief behoudt.

Basic shift-operators >> en << zijn ondertekende operators. Ze zullen het teken van de waarde behouden.

Het is echter gebruikelijk dat programmeurs getallen gebruiken om niet-ondertekende waarden op te slaan. Voor een int betekent dit dat het bereik wordt verschoven naar [0, 2 ^ 32 - 1], om tweemaal zoveel waarde te hebben als met een ondertekende int.

Voor die hoofdgebruikers heeft bit for sign geen betekenis. Dat is de reden waarom Java >>> , een operator in ploegendienst, heeft toegevoegd zonder dat teken te negeren.

                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)

Waarom is er geen <<< ?

Dit komt uit de beoogde definitie van rechts verschuiven. Aangezien het de geleegde plaatsen aan de linkerkant vult, is er geen beslissing te nemen over het stukje teken. Bijgevolg zijn er geen twee verschillende operatoren nodig.

Zie deze vraag voor een meer gedetailleerd antwoord.