Побитови операции
Bitwise Operations
Побитовите операции са най-бързите операции, които процесорът може да изпълнява. Понякога с тяхна помощ можем да подобрим значително бързодействието на програмата си, или пък да спестим памет. Тук ще разгледаме основните побитови оператори и няколко трика с тях.
Автор: Александър Георгиев
Какво са побитови операции
Побитови операции са прости операции, изпълнявани върху цели числа (
int
,
unsigned
,
long long
, etc.). При тях имаме две променливи (константи)
A и
B с
еднаква дължина откъм брой битове и за всяка позиция се изпълнява операцията между съответния бит в
A и този на същата позиция в
B. Тъй като те са относително прости, те са имплементирани като инструкции в процесора, което ги прави много бързи (съизмерими по скорост със събиране и изваждане, около 3-4 пъти по-бързи от умножение и над 50 пъти по-бързи от деление и модул).
Побитови операции
А сега да разгледаме побитовите операции (достъпни в повечето езици). За простота примерите, които даваме, са с 16-битови числа, но от тях трябва да става ясно как операциите работят и за 32-битови такива.
AND
Операцията "and", представена с оператора "
&
" в C++, служи за побитово "и". Тоест ако имаме две 32-битови променливи (константи), и им приложим побитов and, резултатът ще е 32-битово число, което има 1-ца на всяка позиция, в която
и двата аргумента са имали 1-ца. Например
1337 & 4213 == 49
, тъй като:
0000010100111001(2) = 1337(10)
& 0001000001110101(2) = 4213(10)
= 0000000000110001(2) = 49(10)
OR
Операцията "or", представена с оператора "
|
" в C++, служи за побитово "или". Тоест ако имаме две 32-битови променливи (константи), и им приложим побитов or, резултатът ще е 32-битово число, което има 1-ца на всяка позиция, в която
поне един от аргументите е имал 1-ца. Например
1337 | 4213 == 5501
, тъй като:
0000010100111001(2) = 1337(10)
| 0001000001110101(2) = 4213(10)
= 0001010101111101(2) = 5501(10)
XOR
? | Операцията XOR може да се изрази като OR - AND. Наистина, 5501 - 49 = 5452.
|
Операцията "xor" (exclusive or), представена с оператора "
^
" в C++, служи за побитово "изключващо или". Тоест ако имаме две 32-битови променливи (константи), и им приложим побитов xor, резултатът ще е 32-битово число, което има 1-ца на всяка позиция, в която
точно един от аргументите е имал 1-ца. Например
1337 ^ 4213 == 5452
, тъй като:
0000010100111001(2) = 1337(10)
^ 0001000001110101(2) = 4213(10)
= 0001010101001100(2) = 5452(10)
NOT
! | Забележете, че побитовият "not" ("~ ") е различен от логическия такъв ("! "). В края на темата сме разгледали някои от основните разлики между побитови и логически оператори.
|
Унарната операция "not", представена с оператора "
~
" в C++, служи за побитово "не". Тоест ако имаме 32-битова променлива (константа), и ѝ приложим побитов not, резултатът ще е 32-битово число, което има 1 на всяка позиция, в която аргументът е имал 0, и обратно - 0 на всяка позиция, в която аргументът е имал 1. Например
~1337 == 64198
*, тъй като:
~ 0000010100111001(2) = 1337(10)
= 1111101011000110(2) = 64198(10)
* Забележете отново, че работим с 16-битови числа без знак. Ако ползвахме 32-битови,
~1337
щеше да е значително по-голямо число. Ако пък ползвахме числа със знак, поради начина на представяне на числа в компютъра, резултатът щеше да е отрицателно число.
SHIFT LEFT
! | Внимавайте с shift left, когато ползвате 64-битови типове! Много честа грешка е да се ползва, например, "mask & (1 << 42)", където mask e 64-битова променлива. Константите, обаче, по подразбиране в C++ са от тип int, така че (1 << 42) реално ще се изпълни като 32-битова операция, ще овърфлоуне и ще стане 0. Вместо това трябва да укажете, че искате да шифтнете 1 от тип long long, което можете да направите по следния начин: "mask & (1LL << 42)".
|
Операцията "shift left", представена с оператора "
<<
" в C++, служи за преместване на битовете на дадено число наляво. Тоест ако имаме 32-битова променлива (константа), и ѝ приложим побитов shift left 3, резултатът ще е 32-битово число, което има 1-ца на всяка позиция, в която аргументът е имал 1 три позиции надясно (тоест тази единица сега е изместена три позиции наляво). Всички единици, които излязат извън рамките на числото, биват игнорирани. Например
1337 << 3 == 10696
, тъй като:
0000010100111001(2) = 1337(10)
<< 0000000000000011(2) = 3(10)
= 0010100111001000(2) = 10696(10)
Забележете че тъй като shift left с една позиция реално умножава числото по 2, то shift left с три позиции е еквивалентно на умножение по 2
3 = 8. Наистина, 1337 * 8 = 10696.
SHIFT RIGHT
! | В C++ shift right, приложен върху signed типове (int, long long, ...) копира първия бит (който носи знака), тоест резултатът може да не е това, което очаквате!
|
Операцията "shift right", представена с оператора "
>>
" в C++, служи за преместване на битовете на дадено число надясно. Тоест ако имаме 32-битова променлива (константа), и ѝ приложим побитов shift right 3, резултатът ще е 32-битово число, което има 1-ца на всяка позиция, в която аргументът е имал 1 три позиции наляво (тоест тази единица сега е изместена три позиции надясно). Всички единици, които излязат извън рамките на числото, биват игнорирани. Например
1337 >> 3 == 167
, тъй като:
0000010100111001(2) = 1337(10)
>> 0000000000000011(2) = 3(10)
= 0000000010100111(2) = 167(10)
Забележете, че
за положителни числа shift right с една позиция реално дели (целочислено) на 2. Така може да ползваме shift right за деление на степени на две - например shift right с три позиции е еквивалентно на (целочислено) деление на 2
3 = 8. Наистина, 1337 / 8 = 167.
Битови маски (bitmasks)
? | Битовите маски се срещат относително често в динамичното оптимиране, като си имат цяло собствено подразделение - "динамично по битова маска". Именно с този подход се решава задачата за търговския пътник с до около 25 върха.
|
В състезателната информатика, побитовите операции намират най-често приложение в манипулирането на така наречените "битови маски". Ако имате сравнително малки множества, можете да ползвате едно единствено цяло число (от тип
int
за 0 до 32 елемента и
long long
за 33 до 64) за да пазите кои от елементите са вече използвани (обработени, посетени) и кои не са. Забележете, че това е доста по-компактно откъм памет (поне 32-пъти), като в същото време е
и по-бързо! Числото, което ползвате вместо масив, се нарича
битова маска.
Операции над битови маски
Как точно става това? Всеки бит в числото ще отговаря за един от елементите на множеството и ще бъде 0, ако съответният елемент не е в множеството, и 1 ако е. Така означаваме празното множество с една променлива
int mask = 0
.
За да проверим дали елементът
el е в множеството или не, можем да ползваме следната функция:
bool
contains(int
mask,
int
el) {
return
mask &
(1
<
<
el);
}
За да означим, че елементът
el е в множеството, трябва да направим бита на позиция
el единица. Това можем да направим по следния начин:
void
insert(int
&
mask,
int
el) {
mask |
=
(1
<
<
el);
}
За да премахнем елемента
el от множеството (независимо дали той е бил в него или не), бихме ползвали:
void
erase(int
&
mask,
int
el) {
mask &
=
~
(1
<
<
el);
}
За да променим принадлежността на елемента
el в множеството (да го добавим, ако не е бил в него, но да го премахнем, ако е бил), можем да ползваме операцията XOR:
void
change(int
&
mask,
int
el) {
mask ^
=
(1
<
<
el);
}
Операции над цели множества (обединение, сечение, разлика), които по принцип са със сложност
O(N)
или по-голяма, тук са
O(1)
.
Например, за да обединим два сета (две битови маски) бихме ползвали:
int
unite(int
mask1,
int
mask2) {
return
mask1 |
mask2;
}
За да намерим тяхното сечение пък бихме могли да ползваме:
int
intersect(int
mask1,
int
mask2) {
return
mask1 &
mask2;
}
Разликата на две множества, представени чрез битови маски, става по следния начин:
int
subtract(int
mask1,
int
mask2) {
return
mask1 &
~
mask2;
}
? | Свойството на компилатора да изнесе кода от дадена функция във викащия го код и да си спести викането на функция (което отнема някакво време, макар и минимално), се нарича inlining. Можете да ползвате ключовата дума inline пред името на функция за да подскажете на компилатора, че дадената функция е подходяща за това.
|
На практика тези парчета код са достатъчно дребни да не са изнесени във функция и много често ще видите те да бъдат използвани из самия код. Все пак, при по-сложни програми силно ви съветваме да си ги изнасяте във функция - компилаторът е достатъчно умен да не изпълнява истинско викане на функция (тоест кодът си остава бърз), като в същото време вашият код е много по-спретнат и неподатлив на грешки.
Малко по-сложен пример
Сега нека разгледаме как би изглеждала малко по-сложна програма, която ползва битови маски. Представете си, че са ви дадени целите числа
N и
K и се иска от вас да намерите
K-тата пермутация на числата от 1 до
N, включително, като:
Тази задачка бихме могли да решим по следния начин:
long
long
fact[MAX];
void
kthPermutation(int
n,
long
long
k,
int
cnt,
int
used) {
if
(cnt =
=
n) {
return
;
}
for
(int
num =
1
;
num <
=
n;
num+
+
) if
(!
(used &
(1
<
<
num))) {
if
(k <
=
fact[n -
cnt -
1
]) {
printf("%d%c"
,
num,
cnt +
1
=
=
n ?
'\n'
:
' '
);
kthPermutation(n,
k,
cnt +
1
,
used |
(1
<
<
num));
break
;
}
k -
=
fact[n -
cnt -
1
];
}
}
void
printKthPermutation(int
n,
long
long
k) {
fact[0
] =
1
;
for
(int
i =
1
;
i <
n;
i+
+
)
fact[i] =
fact[i -
1
] *
i;
kthPermutation(n,
k,
0
,
0
);
}
Ако забелязахте, вече използваните числа от пермутацията пазихме в битова маска (променливата
used).
Трикове и употреба
Тук ще покажем няколко случая, в които побитовите операции често намират приложение, а както и трикове, с които удобно можете да ги ползвате.
Намиране на всички подмножества на дадено множество
Понякога се налага да намерите всички (непразни) подмножества на дадено множество. Това може да стане по следния начин (ако
mask е битова маска на началното множество):
for
(int
nmask =
mask;
nmask >
0
;
nmask =
((nmask -
1
) &
mask)) {
...
}
Намиране на най-нисък бит (lowest bit)
В други случаи пък ще ви се налага да намирате бързо най-младшата единица (или по-точно нейната стойност) в двоичния запис на дадено число (вижте темата за
индексни дървета). Това можете да направите по следния начин (ако
num е числото, чиито най-младши бит искате да намерите):
int
lowestBit(int
num) {
return
num -
(num &
(num -
1
));
}
Защо работи това? Нека имаме числото 10696
(10) = 0010100111001000
(2).
0010100111001000(2) = 10696(10)
& 0010100111000111(2) = 10695(10)
= 0010100111000000(2) = 10688(10)
Вадейки резултата от оригиналното число получаваме:
0010100111001000(2) = 10696(10)
- 0010100111000000(2) = 10688(10)
= 0000000000001000(2) = 8(10)
Което е и точно стойността на най-ниския бит.
Друг начин (който също може да срещнете) да се направи това дори по-кратко е:
int
lowestBit(int
num) {
return
num &
-
num;
}
Защо това работи, сме показали в повече детайли в темата за
индексни дървета.
Брой сетнати битове (popcount)
? | Броят сетнати битове (битове със стойност 1) в дадено число се нарича "Хемингово тегло".
|
Ползвайки горния трик за премахване на най-младшия сетнат бит можем да напишем ефективна функция, която намира броя единици в двоичния запис на число:
int
popcount(int
num) {
int
cnt =
0
;
while
(num) {
num &
=
(num -
1
),
cnt+
+
;
}
return
cnt;
}
Алтернативно може да ползвате нестандартизираната, но почти навсякъде достъпна GCC функция
__builtin_popcount()
.
Разстояние на Хеминг
В кодирането често се ползва
разстояние на Хеминг, което е броя позиции, в които два двоични стринга (в частност числа) се различават. Това чрез битови операции може да бъде имплементирано много ефективно:
int
hammingDistance(int
num1,
int
num2) {
return
popcount(num1 ^
num2);
}
Както казахме по-горе, операцията XOR оставя само
различните битове, докато
popcount()
намира техния брой - което е точно нещото, което се иска.
Размяна на цели числа
Относително чест трик с побитови операции е как можем да разменим две цели числа без
никаква допълнителна памет. За целта трябва да ползваме, че операцията XOR е обратима чрез себе си - ако имаме XOR-ът две числа
X и
Y, както и едно от двете можем да намерим другото, като XOR-нем XOR-ът им с това от двете, което имаме.
Така следната функция разменя стойностите на двете числа без да ползва допълнителна променлива (съответно и допълнителна памет):
void
swap(int
&
x,
int
&
y) {
x ^
=
y ^
=
x ^
=
y;
}
Разлика от логически операции
Забележете, че побитовите AND ("
&
"), OR ("
|
") и NOT ("
~
") са различни от логическите AND ("
&&
"), OR ("
||
") и NOT ("
!
").
Докато побитовите изпълняват операцията върху отделните битове на аргументите си, логическите такива първо превръщат аргументите си в
true
/
false
константи и
чак след това изпълняват операцията върху тях (тоест изпълняват побитов AND/OR/NOT само на един единствен бит). В следствие на това, резултатите от тях понякога са различни. Например:
~
13
=
=
-
14
(true
)
!
13
=
=
0
(false
)
42
&
17
=
=
0
(false
)
42
&
&
17
=
=
1
(true
)
42
|
13
=
=
47
42
|
|
13
=
=
1
Друга съществена разлика между тях е, че логическите оператори са "свързани на късо" - тоест са оптимизирани по такъв начин, че ако е ясен резултатът от операция по което и да е време не се стига до останалите оператори. Например:
bool
printAndReturnTrue() {
printf("True!\n"
);
return
true
;
}
bool
printAndReturnFalse() {
printf("False!\n"
);
return
false
;
}
void
shortCircuitExample() {
if
(printAndReturnTrue() |
|
printAndReturnFalse()) {
printf("Here!\n"
);
}
}
Тук първо би се извикала функцията
printAndReturnTrue()
, след което, тъй като имаме OR а функцията е върнала
true
, C++ се усеща, че няма смисъл да изпълнява и
printAndReturnFalse()
, съответно кодът би влязъл директно в тялото на
if()
-a, без да вика втората функция.
! | За разлика от логическите оператори && и || , побитовите & и | не са short-circuited. Ако използваме тях в горния код винаги биха се извикали и двете функции.
|
За да се уверите в това можете да изпълните горния код и ще видите, че се печатат само "True" и "Here".
По подобен начин ако имахме "
&&
" и функциите в
if()
-а бяха наобратно (първо тази с
false
) изобщо не би се викнала тази с
true
(тъй като няма начин целият иф да се евалюира до
true
, ако първият аргумент вече е
false
.
Референции
- A bit of fun - fun with bits (www.topcoder.com)
- Hamming Weight (en.wikipedia.org)
- Hamming Distance (en.wikipedia.org)
Страницата е посетена 17813 пъти.