§ 27. Бітавыя аперацыі ў мове праграміравання

Бітавыя аперацыі таксама ляжаць у аснове камп’ютарных устройстваў, бо на іх заснавана логіка работы лагічных вентыляў — базавых элементаў лічбавых схем.

Бітавыя аперацыі па сэнсе падобныя да лагічных, але ўжываюцца для кожнага разраду двайковага ўяўлення ліку (біта) асобна. Яны вызначаны толькі для цэлалікавых тыпаў і не могуць ужывацца ў дачыненні да рэчаісных лікаў. У двайковым ліку біты нумаруюцца справа налева, пачынаючы з 0.

С++ падтрымлівае ўсе існыя бітавыя аперацыі. (Разгледзьце прыклад 27.1.)

Аперацыя

Знак аперацыі

Адмаўленне NOT

~

Пабітавае AND

&

Пабітавае OR

|

Складанне па модулі два  XOR

^

Зрух улева

<< 

Зрух управа

>> 

Табліцы праўдзівасці бітавых і звычайных лагічных аперацый І, АБО, НЕ супадаюць. Адрозненне толькі ў тым, што бітавыя аперацыі выконваюцца над асобнымі бітамі.

Відавочна, што бітавыя аператары могуць стварыць значэнні, адрозныя ад 0 ці 1. Лагічныя ж аператары заўсёды вяртаюць 0 ці 1 (прыклад 27.2). Бітавыя аператары звычайна не выкарыстоўваюцца ва ўмоўных аператарах, якімі з’яўляюцца аператары адносін і лагічныя аператары.

Аператары зруху >> і << зрушваюць біты ў пераменнай управа і  ўлева на вызначаны лік:

пераменная >> колькасць зрухаў;

агульны вягляд аператара зруху ўлева:

пераменная << колькасць зрухаў;

Пры пабітавым зруху біт, які выкідаецца, знікае, не ўплываючы на астатнія біты, а на месцы біта, што з’явіўся, запісваецца 0 (прыклад 27.3).

Пры выкарыстанні бітавых і лагічных аперацый, а таксама аперацый параўнання неабходна ўлічваць прыярытэт іх выканання (прыклад 27.4).

Области применения битовых операций:

  1. Праверка, скідванне і ўстаноўка асобных бітаў у складзе ліку.
  2. Выкананне хуткага множання і дзялення (зрух улева раўнасільны множанню на 2, а зрух управа — дзяленню на 2).
  3. Эканомія памяці (упакоўка некалькіх лагічных значэнняў у адну цэлую пераменную).
  4. Павышэнне прадукцыйнасці праграм — бітавыя аперацыі могуць выконвацца адначасова з усімі разрадамі.
  5. Пры распрацоўцы драйвераў устростваў, напрыклад праграм для мадэмаў, дыскаў і прынтараў.
  6. Пры дэкадзіраванні інфармацыі ад знешніх устройстваў.
  7. У шыфраванні.

Разгледзім выкарыстанне бітавых аперацый у С++ у дачыненні да натуральных лікаў (прыклады 27.9 — 27.16).

Прыклад 27.9. Вылічыць 2n + 2m.

  1. Пры n = m выконваецца зрух адзінкі ўлева на n + 1 пазіцыю.
  2. Пры n ≠ m  выконваецца паслядоўна:

а) зрух адзінкі ўлева на n пазіцый;

б) зрух адзінкі ўлева на m пазіцый;

в) пабітавае OR з вынікамі зрухаў.

Прыклад 27.10. Устанавіць i-ы біт ліку A роўным  1.

Паслядоўна выконваецца:

  1. Зрух адзінкі ўлева на i пазіцый.
  2. Пабітавае OR ліку A з вынікам зруху адзінкі.

Прыклад 27.11. Інвертаваць i-й біт ліку A.

Паслядоўна выконваецца:

  1. Зрух адзінкі ўлева на i пазіцый.
  2. Пабітавае XOR ліку A з вынікам зруху адзінкі.

Прыклад 27.12. Устанавіць i-ы біт ліку A роўным 0.

Паслядоўна выконваецца:

  1. Зрух адзінкі ўлева на i пазіцый.
  2. Інверсія выніку зруху адзінкі.
  3. Пабітавае AND ліку A з вынікам інверсіі зруху адзінкі.

Прыклад 27.13. Абнуліць усе біты ліку A, акрамя i бітаў.

Паслядоўна выконваецца:

  1. Зрух адзінкі ўлева на i пазіцый.
  2. Адніманне 1 з выніку зруху адзінкі.
  3. Пабітавае AND ліку A з вынікам аднімання.

Прыклад 27.14. Вызначыць значэнне i-га біта ліку A.

Паслядоўна выконваецца:

  1. Зрух ліку A ўправа на i пазіцый.
  2. Пабітавае AND зруху ліку A з адзінкай.

Прыклад 27.15. Палічыць колькасць адзінак у двайковым запісе ліку A, зададзенага ў дзесятковай сістэме лічэння.

Спосаб I

  1.  Заводзім бітавую «маску» (пераменная mask), якая змяшчае адзіны ненулявы біт у малодшым разрадзе (32-разрадны двайковы лік).
  2.  Пазіцыя ненулявога біта змяняецца ў цыкле ад малодшага да старэйшага.
  3.  Калі бягучы біт ліку A роўны 1, то вынік пабітавага AND чарговага значэння маскі на значэнне ліку A супадае з маскай. Гэты факт выкарыстоўваецца для павелічэння лічыльніка num.

Спосаб II

У цыкле, які паўтараем, пакуль A > 0, выконваем:

    1.  Выкідваем крайнюю справа адзінку ў двайковым уяўленні ліку A. Для гэтага змяняем значэнне ліку A на вынік пабітавага AND ліку A і  (A – 1). Вынікам гэтага дзеяння будзе выдаленне ў ліку A адзінкі ў малодшым разрадзе.
    2. Павялічваем значэнне лічыльніка адзінак cnt у ліку A на 1.

Прыклад 27.1. Выполнение битовых операций  NOT, AND, OR, XOR.

Бітавае NOT

Пераменная

Значэнне

Двайковае
ўяўленне

X

44

0010 1100

X

211

1101 0011

int x = 44, z;

  z = ~x;

  cout << z << endl;  //211

Бітавае AND

Пераменная

Значэнне

Двайковае 
ўяўленне

X

14

0000 1110

Y

11

0000 1011

X & Y

10

0000 1010

int x = 14, y = 11, z;

  z = x & y;

  cout << z << endl;  //10


Бітавае OR

Пераменная

Значэнне

Двайковае 
ўяўленне

X

10

0000 1010

Y

9

0000 1001

X | Y

11

0000 1011

int x = 10, y = 9, z;

 z = x | y;

 cout << z << endl;  //11

  

Бітавае XOR

Пераменная

Значэнне

Двайковае 
ўяўленне

X

10

1010 1100

Y

9

0010 0100

begin mathsize 14px style space straight X space to the power of logical and space straight Y end style

3

1000 1000

int x = 172, y = 36, z;

 z = x ^ y;

 cout << z << endl;  //136 

Прыклад 27.2.

int x = 10, z1, z2;

z1 = x & 8;

cout << z1 << endl;  //8

z2 = x && 8;

cout << z2 << endl;  //1

Прыклад 27.3. Выкананне аперацый пабітавага зруху.

Зрух у лева

Пераменная

Значэнне

Двайковае 
ўяўленне

     X

10

00001010

     Y = X << 1

20

000010100

     Y = X << 2

40           0000101000
     Y = X << 3 80 00001010000

     Y = X << 5

64

0000101000000

 

int x = 10, z;

z = x << 2;

cout << z << endl;  //40

Зрух у лева

Пераменная Значэнне Двайковае 
ўяўленне
  X 10 00001010
  Y = X >> 1 5 000001010
  Y = X >> 2 2 0000001010
  Y = X >> 3 1 00000001010
  Y = X >> 5 0 0000000001010

int x = 10, z;

z = x >> 3;

cout << z << endl;  //1

  Прыклад 27.4. Прыярытэт выканання аперацый.

Аперацыя

Апісанне

>>, <<

Пабітавыя зрухі

>, <, >=, <=

Аперацыі параўнання (1)

==, !=

Аперацыі параўнання (2)

&

 Пабітавае AND

^

 Пабітавае XOR

|

 Пабітавае OR

&&

 Лагічнае AND

||

 Лагічнае OR

Прыклад 27.5.

Калі лік з’яўляецца ступенню двойкі:

      int z = i & (i 1) // z = 0    

Калі ў двайковым уяўленні ліку ўсе адзінкі:

      int z = i & (i + 1) // z = 0    

Прыклад 27.6. Абнуленне крайняга правага  біта ліку.

     A &= A - 1;   

A

1000 1010

A — 1

1000 1001

&

1000 1000

Прыклад 27.7. Абнуленне крайніх правых i біт ліку.

i = 2;

A >>= i;

A <<= i;

A

1000 1011

>> 2

0010 0010

<< 2

1000 1000

Прыклад 27.8. Вылічыць 2n. 

n = 2;

A = 1 << n;  // A = 4

A

0000 0001

<< 2

0000 0100

Прыклад 27.9.

if (n == m)

  A = 1 << (n + 1);

else

  A = 1 << n | 1 << m;

1) n = m = 2:

A

0000 0001

<< (2 + 1)

0000 1000

A = 8.

2) n = 2, m = 3:

 

0000 0001

<< 2

0000 0100

A = 4

 

0000 0001

<< 3

0000 1000

A = 8

|

0000 1100

A = 12

Прыклад 27.10.

i = 2;

A |= (1 << i);

A

1000 1011

 

0000 0001

<< 2

0000 0100

|

1000 1110

Прыклад 27.11.

           A ^= (1 << i);          

1) i = 3:

A

1000 1011

 

0000 0001

<< 3

0000 1000

^

1000 0011

2) i = 2:

A

1000 1011

 

0000 0001

<< 2

0000 0100

^

1000 1111

Прыклад 27.12.

i = 3;

A &= ~(1 << i);

A

1000 1011

 

0000 0001

<< 3

0000 1000

~

1111 0111

&

1000 0011

Прыклад 27.13.

i = 4;

A &= (1 << i) - 1;

A

1001 1011

 

0000 0001

<< 4

0001 0000

– 1

0000 1111

&

0000 1011

Прыклад 27.14.

i = 3;

int z = (A >> i) & 1;

  

A

1001 1011

>> 3

0001 0011

 

0000 0001

&

0000 0001

Прыклад 27.15. Вывесці значэнне 8-разраднага ліку пабітна.

for (int i = 7; i >= 0; i--)

 cout << (A >> i & 1);

Прыклад 27.16.

Спосаб I.

 int bit;

 int mask = 1;
 int num =
0; 
 for (int i =
0; i <= 31; i++)
 {

   bit = mask & A;

   if (bit == mask)

      num++;
   mask = mask <<
1;

 }

Спосаб II.

 int cnt = 0;
 
while (A != 0)

 {

    A = (A  1) & A;

    cnt++;

 }

Крок цыкла

Пераменная

Значэнне

1

A

1000 1001

A - 1

1000 1000

&

1000 1000

cnt

1

2

A

1000 1000

A - 1

1000 0111

&

1000 0000

cnt

2

3

A

1000 0000

A - 1

0111 1111

&

0000 0000

cnt

3