Оператори над битовима¶

За рад над битовима броја у програмском језику C користе се следећи битски оператори (енгл. Bitwise Operators):

&, битски оператор И (енгл. Bitwise AND),
|, битски оператор ИЛИ (енгл. Bitwise OR),
^, битски оператор ЕКСИЛИ (енгл. Bitwise XOR),
~, битски оператор НЕ (енгл. Bitwise NOT),
<<, битски оператор померања у лево (енгл. Shift Left) и
>>, битски оператор померања у десно (енгл. Shift Right).

Примењују се над целобројним (и знаковним) операндима.

Битски оператори се често користе приликом израде системких програма, програма у којима се врши „паковање” података, програма за обраду графичких и мултимедијалних садржаја, мрежних програма, програма који користе криптографске алгоритме и сл. У неким случајевима операције са битовима могу да произведу ефикасније и оптимизованије програме него друге стандардне операције.

Подсети се да основни тип података за чување целих бројева користи једну реч (енгл. word), која се састоји од \(4\) бајта, односно \(32\) бита. То значи да неозначен број (unsigned) може добити вредности од \(0\) до \(4,294,967,295\), односно до \(2^{32}-1\). Тако, \(0\) се представља као бинарни број 00000000 00000000 00000000 00000000, а \(4,294,967,295\) као бинарни број 11111111 11111111 11111111 11111111, оба добијена директном конверзијом декадног броја у бинарни.

Међутим, цели бројеви могу бити и позитивни и негативни, односно могу бити означени (signed). Ако је број означен, први бит од \(32\) бита мора се жртвовати за знак. По конвенцији, ако је први бит 0, онда је број позитиван, односно, ако је први бит 1 онда је број негативан. Пошто је остао још \(31\) бит, значи да цео број може добити вредности од \(-2,147,483,648\) до \(2,147,483,647\), односно до \(\pm{2^{31}}-1\). Међутим, представљање означених целих бројева у меморији се знатно компликује, јер се конверзија декадног броја у бинарни, ако је број негативан, не врши директно.

Конверзија означених целих бројева у бинарне бројеве укључује рачунање комплемента двојке што превазилази знања из математике ученика првих и других разреда средње стручне школе. На пример, неозначен цео број \(54,321\) представља се у меморији као бинарни број 00000000 00000000 11010110 00010001 добијен директном конверзијом декадног броја у бинарни, док се негативан означен цео број \(-54,321\) представља као бинарни број 11111111 11111111 00101001 11101111 у комплементу двојке.

У овој лекцији ћеш, због тога, битске операторе примењивати само над операндима који су неозначени цели бројеви.

Ако ипак желиш да научиш више, конверзија негативних означених целих бројева у бинарне врши се на следећи начин:

Рачуна се апсолутна вредност негативног декадног броја: |-54321|=54321. Добијени декадни број конвертује се у бинарни: 54321 = 11010110 00010001. Нулама се допуњује лева страна добијеног бинарног броја до жељеног броја бинарних цифара (нпр. до 32 бинарне цифре за целе бројеве типа int): 00000000 00000000 11010110 00010001. Инвертују се све битови у бинарном броју (0 у 1 и 1 у 0): 11111111 11111111 00101001 11101110. На крају се добијени бинарни број сабира са један: 11111111 11111111 00101001 11101110 + 1.

Добијени збир представља негативан означен цео број -54321 записан у бинарном облику у нотацији комплемента двојке: 11111111 11111111 00101001 11101111. У овом случају сабирање је било једноставно јер су последњи битови сабирака били 0 и 1, чији збир износи 1. Ако се сабирају битови 1 и 1, збир износи 2, па се једна јединица записује, а друга се преноси - слично као приликом сабирања декадних бројева, где се врши пренос када је збир већи од 9.

Битски оператор И¶

Битски оператор & се примењује над битовима два бинарна броја једнаке дужине извођењем логичке операције И над наспрамним битовима. Ако су оба бита која се пореде јединице, резултирајући бит биће јединица, а у супротном биће нула.

`a`	`b`	`a & b`
`1`	`1`	`1`
`1`	`0`	`0`
`0`	`1`	`0`
`0`	`0`	`0`

Напиши програм у програмском језику C за извођење логичке операције И над битовима два унета неозначена цела броја.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    unsigned a, b;
    scanf("%u%u", &a, &b);
    unsigned res = a & b;
    printf("%u", res);
    return 0;
}

Ако се на стандардни улаз унесу бројеви \(10\) и \(12\) на стандардном излазу исписаће се број \(8\). Зашто? У овом случају довољно је да посматраш само последње битове унетих бројева, јер су пре тога сви битови нуле. На последњој позицији, 0 & 0 резултира битом 0, на позицији пре, 0 & 1 резултира битом 0, на позицији пре, 1 & 0 резултира битом 0 и на позицији пре, 1 & 1 резултира битом 1. Према томе, резултат претворен у декадни број има вредност \(8\).

a = 10      00000000 00000000 00000000 00001100
b = 12      00000000 00000000 00000000 00001010
            -----------------------------------
a & b = 8   00000000 00000000 00000000 00001000

Битски оператор ИЛИ¶

Битски оператор | се примењује над битовима два бинарна броја једнаке дужине извођењем логичке операције ИЛИ над наспрамним битовима. Ако је макар један од битова који се пореде различит од нуле, резултирајући бит биће јединица, а у супротном биће нула.

`a`	`b`	`a \| b`
`1`	`1`	`1`
`1`	`0`	`1`
`0`	`1`	`1`
`0`	`0`	`0`

Напиши програм у програмском језику C за извођење логичке операције ИЛИ над битовима два унета неозначена цела броја.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    unsigned a, b;
    scanf("%u%u", &a, &b);
    unsigned res = a | b;
    printf("%u", res);
    return 0;
}

Ако се на стандардни улаз унесу бројеви \(10\) и \(12\) на стандардном излазу исписаће се број \(14\). Зашто? И у овом случају довољно је да посматраш само последње битове унетих бројева, јер су пре тога сви битови нуле. На последњој позицији, 0 & 0 резултира битом 0, на позицији пре 0 & 1 резултира битом 1, на позицији пре 1 & 0 резултира битом 1 и на позицији пре 1 & 1 резултира битом 1. Према томе, резултат претворен у декадни број има вредност \(14\).

a = 10      00000000 00000000 00000000 00001100
b = 12      00000000 00000000 00000000 00001010
            -----------------------------------
a | b = 14  00000000 00000000 00000000 00001110

Битски оператор ЕКСИЛИ¶

Битски оператор ^ се примењује над битовима два бинарна броја једнаке дужине извођењем логичке операције ЕКСИЛИ над наспрамним битовима. Ако су битови који се пореде различити, резултирајући бит биће јединица, а у супротном биће нула.

`a`	`b`	`a ^ b`
`1`	`1`	`0`
`1`	`0`	`1`
`0`	`1`	`1`
`0`	`0`	`0`

Напиши програм у програмском језику C за извођење логичке операције ЕКСИЛИ над битовима два унета неозначена цела броја.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    unsigned a, b;
    scanf("%u%u", &a, &b);
    unsigned res = a ^ b;
    printf("%u", res);
    return 0;
}

Ако се на стандардни улаз унесу бројеви \(10\) и \(12\) на стандардном излазу исписаће се број \(6\). Зашто? И у овом случају довољно је да посматраш само последње битове унетих бројева, јер су пре тога сви битови нуле. На последњој позицији, 0 & 0 резултира битом 0, на позицији пре 0 & 1 резултира битом 1, на позицији пре 1 & 0 резултира битом 1 и на позицији пре 1 & 1 резултира битом 0. Према томе, резултат претворен у декадни број има вредност \(6\).

a = 10      00000000 00000000 00000000 00001100
b = 12      00000000 00000000 00000000 00001010
            -----------------------------------
a ^ b = 6   00000000 00000000 00000000 00000110

Битски оператор НЕ¶

Битски оператор ^ је оператор који се примењује над битовима једног бинарног броја за који се рачуна његов комплемент. У најједноставнијем случају, ако је број неозначен, вршиће се инвертовање за бит јединица резултирајући бит биће нула, односно, за бит нула резултирајући бит биће јединица.

Напиши програм у програмском језику C за извођење логичке операције НЕ над битовима унетог неозначеног целог броја.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    unsigned a;
    scanf("%u", &a);
    unsigned res = ~a;
    printf("%u", res);
    return 0;
}

Ако се на стандардни улаз унесе број \(2\), на стандардном излазу исписаће се број \(4294967293\). Зашто? У овом случају мораш посматрати све битове унетог броја. Када се инвертују сви битови, резултат претворен у декадни број је \(4,294,967,293\).

a = 2               00000000 00000000 00000000 00000010
~a = 4294967293     11111111 11111111 11111111 11111101

Битски оператор померања у лево¶

Битски оператор померања у лево << је бинарни оператор помоћу којег се померају битови целобројне променљиве за одређени број места у лево. Битови првог операнда померају се улево за број позиција дефинисаних другим операндом. Након померања, на празна места која се стварају на десној страни додају се нуле.

Напиши програм у програмском језику C за померање b битова улево унетог неозначеног целог броја a.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    unsigned a, b;
    scanf("%u%u", &a, &b);
    unsigned res = a << b;
    printf("%u", res);
    return 0;
}

Ако се на стандардни улаз унесу бројеви \(48\) и \(1\) на стандардном излазу исписаће се број \(96\).

48        00000000 00000000 00000000 00110000
48 << 1   00000000 00000000 00000000 01100000

Ако после операције померања улево са леве стране има битова са вредношћу \(1\) за које нема места, резултат је неодређен (дешава се „преливање”). На пример, ако се на стандардни улаз унесу бројеви \(48\) и \(31\), на стандардном излазу исписаће се \(0\), јер резултату није остао ни један бит - сви су се прелили на леву страну.

Ако су вредности оператора које изазивају преливање у изразу наведене у самом програму, Microsoft C/C++ компајлер ће издати упозорење: Warning C26450: Arithmetic overflow: 'operator' operation causes overflow at compile time. Use a wider type to store the operands (io.1). На пример, у следећем програму операција померања за \(31\) место улево битова неозначеног целог броја \(48\) изазваће „преливање”:

#include <stdio.h>

int main(void)
{
    unsigned res = 48 << 31;
    printf("%u", res);
    return 0;
}

и приказ грешке од стране компајлера.

Битски оператор померања у десно¶

Битски оператор померањау десно >> је бинарни оператор помоћу којег се померају битови целобројне променљиве за одређени број места у десно. Битови првог операнда померају се удесно за број позиција дефинисаних другим операндом. Битови са десне стране, за које након померања нема места занемарују се, док се са леве стране додају нуле.

Напиши програм у програмском језику C за померање b битова удесно унетог неозначеног целог броја a.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    unsigned a, b;
    scanf("%u%u", &a, &b);
    unsigned res = a >> b;
    printf("%u", res);
    return 0;
}

Ако се на стандардни улаз унесу бројеви \(48\) и \(1\) на стандардном излазу исписаће се број \(24\).

48        00000000 00000000 00000000 00110000
48 >> 1   00000000 00000000 00000000 00011000

Као што је напоменуто, битови који се „прелију” са десне стране се занемарују - то је предвиђена ситуација и не изазива грешку.