Побитови операции

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₍₂₎ = 1337₍₁₀₎ & 0001000001110101₍₂₎ = 4213₍₁₀₎ = 0000000000110001₍₂₎ = 49₍₁₀₎

OR

Операцията "or", представена с оператора "|" в C++, служи за побитово "или". Тоест ако имаме две 32-битови променливи (константи), и им приложим побитов or, резултатът ще е 32-битово число, което има 1-ца на всяка позиция, в която поне един от аргументите е имал 1-ца. Например 1337 | 4213 == 5501, тъй като:

0000010100111001₍₂₎ = 1337₍₁₀₎ | 0001000001110101₍₂₎ = 4213₍₁₀₎ = 0001010101111101₍₂₎ = 5501₍₁₀₎

XOR

?	Операцията XOR може да се изрази като OR - AND. Наистина, 5501 - 49 = 5452.

Операцията "xor" (exclusive or), представена с оператора "^" в C++, служи за побитово "изключващо или". Тоест ако имаме две 32-битови променливи (константи), и им приложим побитов xor, резултатът ще е 32-битово число, което има 1-ца на всяка позиция, в която точно един от аргументите е имал 1-ца. Например 1337 ^ 4213 == 5452, тъй като:

0000010100111001₍₂₎ = 1337₍₁₀₎ ^ 0001000001110101₍₂₎ = 4213₍₁₀₎ = 0001010101001100₍₂₎ = 5452₍₁₀₎

NOT

!	Забележете, че побитовият "not" ("`~`") е различен от логическия такъв ("`!`"). В края на темата сме разгледали някои от основните разлики между побитови и логически оператори.

Унарната операция "not", представена с оператора "~" в C++, служи за побитово "не". Тоест ако имаме 32-битова променлива (константа), и ѝ приложим побитов not, резултатът ще е 32-битово число, което има 1 на всяка позиция, в която аргументът е имал 0, и обратно - 0 на всяка позиция, в която аргументът е имал 1. Например ~1337 == 64198*, тъй като:

~ 0000010100111001₍₂₎ = 1337₍₁₀₎ = 1111101011000110₍₂₎ = 64198₍₁₀₎

* Забележете отново, че работим с 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₍₂₎ = 1337₍₁₀₎ << 0000000000000011₍₂₎ = 3₍₁₀₎ = 0010100111001000₍₂₎ = 10696₍₁₀₎

Забележете че тъй като shift left с една позиция реално умножава числото по 2, то shift left с три позиции е еквивалентно на умножение по 2³ = 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₍₂₎ = 1337₍₁₀₎ >> 0000000000000011₍₂₎ = 3₍₁₀₎ = 0000000010100111₍₂₎ = 167₍₁₀₎

Забележете, че за положителни числа shift right с една позиция реално дели (целочислено) на 2. Така може да ползваме shift right за деление на степени на две - например shift right с три позиции е еквивалентно на (целочислено) деление на 2³ = 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, включително, като:

1 ≤ N ≤ 20
1 ≤ K ≤ 10¹⁸

Тази задачка бихме могли да решим по следния начин:

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₍₁₀₎ = 0010100111001000₍₂₎.

0010100111001000₍₂₎ = 10696₍₁₀₎ & 0010100111000111₍₂₎ = 10695₍₁₀₎ = 0010100111000000₍₂₎ = 10688₍₁₀₎

Вадейки резултата от оригиналното число получаваме:

0010100111001000₍₂₎ = 10696₍₁₀₎ - 0010100111000000₍₂₎ = 10688₍₁₀₎ = 0000000000001000₍₂₎ = 8₍₁₀₎

Което е и точно стойността на най-ниския бит.

Друг начин (който също може да срещнете) да се направи това дори по-кратко е:

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.

Референции

За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.

Страницата е посетена 17815 пъти.

Побитови операции

Bitwise Operations

Какво са побитови операции

Побитови операции

AND

OR

XOR

NOT

SHIFT LEFT

SHIFT RIGHT

Битови маски (bitmasks)

Операции над битови маски

Малко по-сложен пример

Трикове и употреба

Намиране на всички подмножества на дадено множество

Намиране на най-нисък бит (lowest bit)

Брой сетнати битове (popcount)

Разстояние на Хеминг

Размяна на цели числа

Разлика от логически операции

Референции

Предложете корекция