Bitsgewijze operaties, deel 2

1. Bitsgewijs naar links verschuiven

Java heeft ook 3 bitsgewijze shift-operators : als het echt nodig is, kun je heel eenvoudig alle bits van een nummer meerdere posities naar links of naar rechts verschuiven.

Om de bits van een getal naar links te verschuiven, hebt u de bitsgewijze linkerverschuivingsoperator nodig . Zo staat het geschreven:

a << b

Waar ais het getal waarvan de bits worden verschoven, en bis een getal dat aangeeft hoe vaak de bits van het getal anaar links moeten worden verschoven. Tijdens deze bewerking zijn de bits van lage orde die aan de rechterkant worden toegevoegd nullen.

Voorbeelden:

0b00000011 << 1

0b00000110

0b00000011 << 2

0b00001100

0b00000011 << 5

0b01100000

0b00000011 << 20

0b001100000000000000000000

Een cijfer naar links verschuiven heeft hetzelfde effect als een getal vermenigvuldigen met 2.

Wil je een getal vermenigvuldigen met 16? 16 is hetzelfde als 2 ⁴ . Je schuift het getal dus 4 cijfers naar links

2. Bitsgewijs naar rechts verschuiven

Bits kunnen ook naar rechts worden verschoven. Gebruik hiervoor de bitsgewijze rechtse shift-operator . Zo staat het geschreven:

a >> b

Waar ais het nummer waarvan de bits worden verschoven, en bis het aantal keren dat de bits van het nummer anaar rechts worden verschoven.

Voorbeelden:

0b11000011 >> 1

0b01100001

0b11000011 >> 2

0b00110000

0b11000011 >> 5

0b00000110

0b11000011 >> 20

0b00000000

Een cijfer naar rechts verschuiven heeft hetzelfde effect als een getal delen door 2.

Tijdens deze bewerking zijn de bits van hogere orde die aan de linkerkant worden toegevoegd nullen, maar niet altijd !

Bij het verschuiven van de bits van een getal naar rechts, zou normaal gesproken ook de waarde van het tekenbit verschuiven en zou het teken van het getal verloren gaan. Dienovereenkomstig 1krijgt dit bit voor negatieve getallen (waarbij het meest linkse bit is) een speciale behandeling. Wanneer de bits van een getal naar rechts worden verschoven, 0wordt aan de linkerkant een toegevoegd als de meest linkse bit was 0, en 1aan de linkerkant wordt een toegevoegd als de meest linkse bit was 1.

Maar in het bovenstaande voorbeeld lijkt dat niet het resultaat te zijn. Waarom? Omdat letterlijke gehele getallen ints zijn, en  eigenlijk . Dat wil zeggen, het meest linkse bit is nul.0b111111110b00000000000000000000000011111111

Veel programmeurs zijn gefrustreerd door dit rechtsverschuivingsgedrag en zouden er de voorkeur aan geven dat het nummer altijd met nullen wordt opgevuld. Dus Java voegde nog een rechter shift-operator toe .

Zo staat het geschreven:

a >>> b

Waar a is het nummer waarvan de bits worden verschoven, en b  is het aantal keren dat de bits van het nummer anaar rechts worden verschoven. Deze operator voegt altijd nullen toe aan de linkerkant, ongeacht de oorspronkelijke waarde van het tekenbit van het getal a.

3. Werken met vlaggen

Programmeurs creëerden op basis van bitsgewijze en shiftoperaties een vrijwel geheel nieuw vakgebied: het werken met vlaggen.

Toen computers heel weinig geheugen hadden, was het erg populair om veel informatie in één getal te proppen. Een getal werd behandeld als een reeks bits: een int is 32 bits en een long is 64 bits.

Je kunt veel informatie in zo'n getal schrijven, vooral als je logische ( trueof false) waarden moet opslaan. Een enkele longis als een booleanarray die uit 64 elementen bestaat. Deze bits werden vlaggen genoemd en werden gemanipuleerd met behulp van de volgende bewerkingen:

• zet vlag
  (maak een specifiek bit gelijk aan 1)
• vlag resetten
  (maak een specifiek bit gelijk aan 0)
• vlag controleren
  (controleer de waarde van een specifiek bit)

En hier is hoe het wordt gedaan met bitsgewijze operatoren.

Het plaatsen van een vlag

Om een ​​specifiek bit in te stellen op 1, moet u een bitsgewijze OF-bewerking uitvoeren tussen het nummer waarvan u het bit wilt instellen en een speciaal gemaakt nummer, waarbij alleen dat bit is 1.

Stel dat u het nummer hebt 0b00001010en dat u het 5e bit moet instellen op 1. In dat geval moet u:

0b00001010 | 0b00010000 = 0b00011010

Als het 5e bit al op één was gezet, dan zou er niets zijn veranderd.

Over het algemeen kan de werking van het instellen van een vlag als volgt worden geschreven

a | (1 << b)

Waar a is het nummer waarvan de bit wordt ingesteld op 1. En b is de positie van het bit in te stellen. Het gebruik van de linker shift-operator is hier superhandig, omdat je meteen kunt zien met welk bit we werken.

Een vlag resetten

Om een ​​specifieke bit te resetten (dwz op te zetten 0) zonder andere bits te storen, moet u een &bewerking uitvoeren tussen het nummer waarvan u de bit wilt resetten (dwz op zetten 0) en een speciaal gemaakt nummer, waarbij alle bits gelijk zijn aan 1behalve voor het bit dat u wilt resetten.

Stel dat u het nummer hebt 0b00001010en dat u het 4e bit moet instellen op 0. In dat geval moet u:

0b00001010 & 0b11110111 = 0b00000010

Als het 4e bit al op nul was gezet, dan was er niets veranderd.

Over het algemeen kan de werking van het resetten van een vlag als volgt worden geschreven

a & ~(1 << b)

Waar a is het nummer waarvan de bit wordt gereset naar 0. En b is de positie van het te wissen bit.

Om een ​​getal te krijgen waar alle bits zijn 1behalve degene die we nul willen hebben, verschuiven we eerst 1 b  posities naar links en gebruiken dan de bitsgewijze NOToperator om het resultaat om te keren.

Een vlag controleren

Naast het instellen of resetten van een specifieke vlag, moet je soms gewoon controleren of een bepaalde vlag is ingesteld, dwz of een bepaalde bit gelijk is aan 1. Dit is vrij eenvoudig te doen met een bitwise &.

Stel dat u moet controleren of de 4e bit is ingesteld op 1in het getal 0b00001010. Dan moet je dit doen:

if ( (0b00001010 & 0b00001000) == 0b00001000 )

Over het algemeen kan de werking van het controleren van een vlag als volgt worden geschreven

(a & (1 << b)) == (1 << b)

Waar a is het nummer wiens bit wordt gecontroleerd. En b is de positie van het bit te controleren.

4. Versleuteling

De bitsgewijze XORbewerking wordt vaak gebruikt door programmeurs voor eenvoudige codering. Over het algemeen ziet zo'n codering er als volgt uit:

result = number ^ password;

Waar number zijn de gegevens die we willen versleutelen, password is een speciaal nummer dat wordt gebruikt als een "wachtwoord" voor de gegevens en result is het versleutelde nummer.

number == (number ^ password) ^ password;

Het belangrijkste hier is dat wanneer de XORoperator twee keer op een nummer wordt toegepast, het originele nummer wordt geproduceerd, ongeacht het "wachtwoord".

Om te herstellen number van de encrypted result, hoeft u alleen maar de bewerking opnieuw uit te voeren:

original number = result ^ password;

Voorbeeld:

class Solution
{
   public static int[] encrypt(int[] data, int password)
   {
     int[] result = new int[data.length];
     for (int i = 0; i <  data.length; i++)
       result[i] = data[i] ^ password;
     return result;
   }

   public static void main(String[] args)
   {
     int[] data =  {1, 3, 5, 7, 9, 11};
     int password = 199;

     // Encrypt the array of data
     int[] encrypted = encrypt(data, password);
     System.out.println(Arrays.toString(encrypted));

     // Decrypt the array of data
     int[] decrypted = encrypt(encrypted, password);
     System.out.println(Arrays.toString(decrypted));
   }
}