Operații pe biți, partea 2

1. Deplasare pe biți la stânga

Java are, de asemenea, 3 operatori de deplasare pe biți : Dacă chiar aveți nevoie, puteți muta pur și simplu toți biții unui număr în mai multe poziții la stânga sau la dreapta.

Pentru a muta biții unui număr la stânga, aveți nevoie de operatorul de deplasare la stânga pe biți . Asa este scris:

a << b

Unde aeste numărul ai cărui biți sunt deplasați și beste un număr care indică de câte ori trebuie mutați biții numărului ala stânga. În timpul acestei operații, biții de ordin inferior adăugați în dreapta sunt zerouri.

Exemple:

0b00000011 << 1

0b00000110

0b00000011 << 2

0b00001100

0b00000011 << 5

0b01100000

0b00000011 << 20

0b001100000000000000000000

Deplasarea unei cifre la stânga are același efect ca și înmulțirea unui număr cu 2.

Want to multiply a number by 16? 16 is the same as 2⁴. So you shift the number 4 digits to the left

2. Bitwise shift right

Bits can also be shifted to the right. To do this, use the bitwise right shift operator. This is how it's written:

a >> b

Where a is the number whose bits are being shifted, and b is the number of times to shift the bits of the number a to right.

Examples:

0b11000011 >> 1

0b01100001

0b11000011 >> 2

0b00110000

0b11000011 >> 5

0b00000110

0b11000011 >> 20

0b00000000

Shifting one digit to the right has the same effect as dividing a number by 2.

During this operation, the high-order bits added on the left are zeros, but not always!

When shifting the bits of a number to the right, the value of the sign bit would ordinarily also shift and the sign of the number would be lost. Accordingly, for negative numbers (where the leftmost bit is 1), this bit gets special treatment. When shifting the bits of a number to the right, a 0 is added on the left if the leftmost bit was 0, and a 1 is added on the left if the leftmost bit was 1.

But in the example above, that doesn't appear to be the result. Why? Because integer literals are ints, and 0b11111111 actually means 0b00000000000000000000000011111111. That is, the leftmost bit is zero.

Mulți programatori sunt frustrați de acest comportament de schimbare la dreapta și ar prefera ca numărul să fie întotdeauna completat cu zerouri. Deci Java a adăugat un alt operator de schimbare la dreapta .

Asa este scris:

a >>> b

Unde a este numărul ai cărui biți sunt deplasați și b  este numărul de ori pentru a muta biții numărului ala dreapta. Acest operator adaugă întotdeauna zerouri în stânga, indiferent de valoarea inițială a bitului semn al numărului a.

3. Lucrul cu steaguri

Programatorii au creat un domeniu de studiu aproape complet nou pe baza operațiunilor pe biți și deplasare: lucrul cu steaguri.

Când computerele aveau foarte puțină memorie, era foarte popular să înghesuiți o mulțime de informații într-un singur număr. Un număr a fost tratat ca o matrice de biți: un int este de 32 de biți, iar un lung este de 64 de biți.

You can write a lot of information in such a number, especially if you need to store logical (true or false) values. A single long is like a boolean array comprised of 64 elements. These bits were called flags and were manipulated using the following operations:

• set flag
  (make a specific bit equal to 1)
• reset flag
  (make a specific bit equal to 0)
• check flag
  (check the value of a specific bit)

And here's how it's done with bitwise operators.

Setting a flag

To set a specific bit to 1, you need to perform a bitwise OR operation between the number whose bit you want to set and a specially created number, where only that bit is 1.

For example, suppose you have the number 0b00001010 and you need to set the 5th bit to 1. In that case, you need to:

0b00001010 | 0b00010000 = 0b00011010

If the 5th bit had been set to one already, then nothing would have changed.

In general, the operation of setting a flag can be written as follows

a | (1 << b)

Where a is the number whose bit will be set to 1. And b is the position of the bit to be set. Using the left shift operator is super convenient here, since you can immediately tell which bit we are working with.

Resetting a flag

To reset a specific bit (i.e. set it to 0) without disturbing other bits, you need to perform an & operation between the number whose bit you want to reset (i.e. set to 0) and a specially created number, where all the bits are equal to 1 except for the bit you want to reset.

For example, suppose you have the number 0b00001010 and you need to set the 4th bit to 0. In that case, you need to:

0b00001010 & 0b11110111 = 0b00000010

If the 4th bit had been set to zero already, then nothing would have changed.

In general, the operation of resetting a flag can be written as follows

a & ~(1 << b)

Where a is the number whose bit will be reset to 0. And b is the position of the bit to be cleared.

Pentru a obține un număr în care toți biții sunt, 1cu excepția celui pe care vrem să fie zero, mai întâi deplasăm 1 b  poziții la stânga și apoi folosim NOToperatorul pe biți pentru a inversa rezultatul.

Verificarea unui steag

Pe lângă setarea sau resetarea unui anumit steag, uneori trebuie doar să verificați dacă un anumit steag este setat, adică dacă un anumit bit este egal cu 1. Acest lucru este destul de ușor de făcut cu un bit &.

De exemplu, să presupunem că trebuie să verificați dacă al 4-lea bit este setat 1la numărul 0b00001010. Atunci trebuie să faci asta:

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

În general, operația de verificare a unui steag poate fi scrisă după cum urmează

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

Unde a este numărul al cărui bit este verificat. Și b este poziția bitului de verificat.

4. Criptare

The bitwise XOR operation is often used by programmers for simple encryption. In general, such encryption looks like this:

result = number ^ password;

Where number is the data we want to encrypt, password is a special number used as a "password" for the data, and result is the encrypted number.

number == (number ^ password) ^ password;

The important thing here is that when the XOR operator is applied to a number twice, it produces the original number, regardless of the "password".

To recover number from the encrypted result, you just need to perform the operation again:

original number = result ^ password;

Example:

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