Бітові операції

Двійкове число

Двійкове число — це число, записане в системі числення за основою 2 (двійковій системі числення); це спосіб математичного запису, який використовує лише два символи: зазвичай «0» (нуль) і «1» (одиниця).

Ми кажемо, що певний біт встановлений (одиничний), якщо він дорівнює одиниці, і очищений (нульовий), якщо він дорівнює нулю.

Двійкове число $(a_k a_{k-1} \dots a_1 a_0)_2$ задає число:

$$(a_k a_{k-1} \dots a_1 a_0)_2 = a_k \cdot 2^k + a_{k-1} \cdot 2^{k-1} + \dots + a_1 \cdot 2^1 + a_0 \cdot 2^0.$$

Наприклад, двійкове число $1101_2$ задає число $13$:

$$\begin{align} 1101_2 &= 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 \\ &= 1\cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1 \cdot 1 = 13 \end{align}$$

Комп'ютери зберігають цілі числа як двійкові числа. Додатні цілі числа (як знакові, так і беззнакові) подаються просто своїми двійковими цифрами, а від'ємні знакові числа (які можуть бути додатними і від'ємними) зазвичай подаються у вигляді доповняльного коду.

C++

unsigned int unsigned_number = 13;
assert(unsigned_number == 0b1101);

int positive_signed_number = 13;
assert(positive_signed_number == 0b1101);

int negative_signed_number = -13;
assert(negative_signed_number == 0b1111'1111'1111'1111'1111'1111'1111'0011);

Python

# int у Python — безмежний, тож понять "доповняльний код фіксованої довжини"
# для нього немає: -13 завжди зберігається як -13.
unsigned_number = 13
assert unsigned_number == 0b1101

positive_signed_number = 13
assert positive_signed_number == 0b1101

# Щоб побачити доповняльний код у заданій розрядності, накладаємо маску:
negative_signed_number = -13
assert negative_signed_number & 0xFFFFFFFF == 0b1111_1111_1111_1111_1111_1111_1111_0011

TypeScript

// number у JS — 64-бітний float; бітові оператори працюють на 32-бітних
// знакових int, тому -13 у доповняльному коді дає те саме 32-бітне значення.
const unsignedNumber = 13;
console.assert(unsignedNumber === 0b1101);

const positiveSignedNumber = 13;
console.assert(positiveSignedNumber === 0b1101);

// >>> 0 інтерпретує біти як беззнакові, щоб порівняти з 0b1111...0011.
const negativeSignedNumber = -13;
console.assert((negativeSignedNumber >>> 0) === 0b1111_1111_1111_1111_1111_1111_1111_0011);

Go

package main

func main() {
	var unsignedNumber uint = 13
	if unsignedNumber != 0b1101 {
		panic("unsigned")
	}

	positiveSignedNumber := 13
	if positiveSignedNumber != 0b1101 {
		panic("positive")
	}

	// int32 у Go зберігає від'ємні числа у доповняльному коді;
	// інтерпретуємо ті самі біти як uint32 для порівняння.
	var negativeSignedNumber int32 = -13
	if uint32(negativeSignedNumber) != 0b1111_1111_1111_1111_1111_1111_1111_0011 {
		panic("negative")
	}
}

Процесори дуже швидко маніпулюють цими бітами за допомогою спеціальних операцій. Для деяких задач ми можемо скористатися цими двійковими представленнями чисел собі на користь і пришвидшити час виконання. А для деяких задач (зазвичай у комбінаториці чи динамічному програмуванні), де ми хочемо відстежувати, які об'єкти ми вже вибрали з певної множини об'єктів, ми можемо просто використати достатньо велике ціле число, у якому кожна цифра відповідає об'єкту, і залежно від того, беремо ми об'єкт чи відкидаємо, ми встановлюємо чи очищаємо відповідну цифру.

Бітові оператори

Усі ці введені оператори виконуються миттєво (з тією самою швидкістю, що й додавання) на процесорі для цілих чисел фіксованої довжини.

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

• $\&$ : оператор побітового І порівнює кожен біт свого першого операнда з відповідним бітом другого операнда. Якщо обидва біти дорівнюють 1, відповідний біт результату встановлюється в 1. Інакше відповідний біт результату встановлюється в 0.

• $|$ : оператор побітового АБО (включного) порівнює кожен біт свого першого операнда з відповідним бітом другого операнда. Якщо хоча б один із двох бітів дорівнює 1, відповідний біт результату встановлюється в 1. Інакше відповідний біт результату встановлюється в 0.

• $\wedge$ : оператор побітового виключного АБО (XOR) порівнює кожен біт свого першого операнда з відповідним бітом другого операнда. Якщо один біт дорівнює 0, а інший — 1, відповідний біт результату встановлюється в 1. Інакше відповідний біт результату встановлюється в 0.

• $\sim$ : оператор побітового доповнення (НЕ) інвертує кожен біт числа: якщо біт встановлений, оператор його очищає, а якщо очищений — встановлює.

Приклади:

n         = 01011000
n-1       = 01010111
--------------------
n & (n-1) = 01010000

n         = 01011000
n-1       = 01010111
--------------------
n | (n-1) = 01011111

n         = 01011000
n-1       = 01010111
--------------------
n ^ (n-1) = 00001111

n         = 01011000
--------------------
~n        = 10100111

Оператори зсуву

Існує два оператори для зсуву бітів.

• $\gg$ зсуває число праворуч, прибираючи кілька останніх двійкових цифр числа. Кожен зсув на одиницю відповідає цілочисловому діленню на 2, тож зсув праворуч на $k$ відповідає цілочисловому діленню на $2^k$.

  Наприклад, $5 \gg 2 = 101_2 \gg 2 = 1_2 = 1$, що збігається з $\frac{5}{2^2} = \frac{5}{4} = 1$. Проте для комп'ютера зсув кількох бітів виконується значно швидше, ніж ділення.

• $\ll$ зсуває число ліворуч, дописуючи нульові цифри. Аналогічно до зсуву праворуч на $k$, зсув ліворуч на $k$ відповідає множенню на $2^k$.

  Наприклад, $5 \ll 3 = 101_2 \ll 3 = 101000_2 = 40$, що збігається з $5 \cdot 2^3 = 5 \cdot 8 = 40$.

  Зауважте, однак, що для цілого числа фіксованої довжини це означає відкидання крайніх лівих цифр, і якщо зсунути занадто сильно, ви отримаєте число $0$.

Корисні трюки

Встановити/інвертувати/очистити біт

Використовуючи побітові зсуви та деякі базові побітові операції, ми можемо легко встановити, інвертувати чи очистити біт. $1 \ll x$ — це число, у якому встановлений лише $x$-й біт, тоді як $\sim(1 \ll x)$ — це число, у якому встановлені всі біти, крім $x$-го.

• $n ~|~ (1 \ll x)$ встановлює $x$-й біт у числі $n$
• $n ~\wedge~ (1 \ll x)$ інвертує $x$-й біт у числі $n$
• $n ~\&~ \sim(1 \ll x)$ очищає $x$-й біт у числі $n$

Перевірка, чи встановлений біт

Значення $x$-го біта можна перевірити, зсунувши число на $x$ позицій праворуч, щоб $x$-й біт опинився в розряді одиниць, після чого ми можемо вилучити його, виконавши побітове & з 1.

C++

bool is_set(unsigned int number, int x) {
    return (number >> x) & 1;
}

Python

def is_set(number: int, x: int) -> bool:
    return bool((number >> x) & 1)

TypeScript

function isSet(number: number, x: number): boolean {
  return ((number >> x) & 1) === 1;
}

Go

func isSet(number uint, x int) bool {
	return (number>>x)&1 == 1
}

Перевірка, чи ділиться число на степінь двійки

За допомогою операції І ми можемо перевірити, чи число $n$ парне, оскільки $n ~\&~ 1 = 0$, якщо $n$ парне, і $n ~\&~ 1 = 1$, якщо $n$ непарне. У загальнішому випадку $n$ ділиться на $2^{k}$ тоді й лише тоді, коли $n ~\&~ (2^{k} − 1) = 0$.

C++

bool isDivisibleByPowerOf2(int n, int k) {
    int powerOf2 = 1 << k;
    return (n & (powerOf2 - 1)) == 0;
}

Python

def is_divisible_by_power_of_2(n: int, k: int) -> bool:
    power_of_2 = 1 << k
    return (n & (power_of_2 - 1)) == 0

TypeScript

function isDivisibleByPowerOf2(n: number, k: number): boolean {
  const powerOf2 = 1 << k;
  return (n & (powerOf2 - 1)) === 0;
}

Go

func isDivisibleByPowerOf2(n, k int) bool {
	powerOf2 := 1 << k
	return n&(powerOf2-1) == 0
}

Ми можемо обчислити $2^{k}$, зсунувши 1 ліворуч на $k$ позицій. Цей трюк працює, бо $2^k - 1$ — це число, що складається рівно з $k$ одиниць. А число, яке ділиться на $2^k$, повинно мати нульові цифри в цих позиціях.

Перевірка, чи є ціле число степенем двійки

Степінь двійки — це число, у якому встановлений лише один біт (наприклад, $32 = 0010~0000_2$), тоді як попереднє за ним число має цю цифру не встановленою, а всі цифри після неї — встановленими ($31 = 0001~1111_2$). Тож побітове І числа з його попередником завжди дорівнюватиме 0, оскільки вони не мають жодної спільної встановленої цифри. Ви можете легко переконатися, що це трапляється лише для степенів двійки та для числа $0$, у якого й так немає жодної встановленої цифри.

C++

bool isPowerOfTwo(unsigned int n) {
    return n && !(n & (n - 1));
}

Python

def is_power_of_two(n: int) -> bool:
    return n != 0 and (n & (n - 1)) == 0

TypeScript

function isPowerOfTwo(n: number): boolean {
  return n !== 0 && (n & (n - 1)) === 0;
}

Go

func isPowerOfTwo(n uint) bool {
	return n != 0 && n&(n-1) == 0
}

Очищення крайнього правого встановленого біта

Вираз $n ~\&~ (n-1)$ можна використати, щоб скинути крайній правий встановлений біт числа $n$. Це працює, бо вираз $n-1$ інвертує всі біти після крайнього правого встановленого біта числа $n$, включно з самим крайнім правим встановленим бітом. Тож усі ці цифри відрізняються від початкового числа, і після виконання побітового І вони всі стають 0, даючи вам початкове число $n$ зі скинутим крайнім правим встановленим бітом.

Наприклад, розгляньмо число $52 = 0011~0100_2$:

n         = 00110100
n-1       = 00110011
--------------------
n & (n-1) = 00110000

Алгоритм Брайана Кернігана

Ми можемо порахувати кількість встановлених бітів за допомогою наведеного вище виразу.

Ідея полягає в тому, щоб розглядати лише встановлені біти цілого числа, скидаючи його крайній правий встановлений біт (після того як ми його порахували), так що наступна ітерація циклу розглядає наступний крайній правий біт.

C++

int countSetBits(int n)
{
    int count = 0;
    while (n)
    {
        n = n & (n - 1);
        count++;
    }
    return count;
}

Python

def count_set_bits(n: int) -> int:
    count = 0
    while n:
        n = n & (n - 1)
        count += 1
    return count


# У стандартній бібліотеці є готові аналоги:
#   bin(n).count("1")     — працює на будь-якій версії Python;
#   n.bit_count()         — від Python 3.10.

TypeScript

function countSetBits(n: number): number {
  let count = 0;
  while (n) {
    n = n & (n - 1);
    count++;
  }
  return count;
}

Go

func countSetBits(n int) int {
	count := 0
	for n != 0 {
		n = n & (n - 1)
		count++
	}
	return count
	// У стандартній бібліотеці: bits.OnesCount(uint(n)) з пакета math/bits.
}

Підрахунок встановлених бітів аж до $n$

Щоб порахувати кількість встановлених бітів у всіх числах аж до числа $n$ (включно), ми можемо запустити алгоритм Брайана Кернігана на всіх числах аж до $n$. Але це призведе до «Time Limit Exceeded» у змаганнях.

Ми можемо скористатися тим фактом, що для чисел аж до $2^x$ (тобто від $1$ до $2^x - 1$) є $x \cdot 2^{x-1}$ встановлених бітів. Це можна унаочнити так.

0 ->   0 0 0 0
1 ->   0 0 0 1
2 ->   0 0 1 0
3 ->   0 0 1 1
4 ->   0 1 0 0
5 ->   0 1 0 1
6 ->   0 1 1 0
7 ->   0 1 1 1
8 ->   1 0 0 0

Ми бачимо, що всі стовпці, крім крайнього лівого, мають по $4$ (тобто $2^2$) встановлених біти кожен, тобто аж до числа $2^3 - 1$ кількість встановлених бітів дорівнює $3 \cdot 2^{3-1}$.

Маючи це нове знання, ми можемо вивести такий алгоритм:

• Знайти найбільший степінь $2$, що менший або рівний заданому числу. Нехай це число буде $x$.
• Обчислити кількість встановлених бітів від $1$ до $2^x - 1$ за формулою $x \cdot 2^{x-1}$.
• Порахувати кількість встановлених бітів у найстаршому розряді від $2^x$ до $n$ і додати її.
• Відняти $2^x$ від $n$ і повторити наведені вище кроки з новим $n$.

C++

int countSetBits(int n) {
        int count = 0;
        while (n > 0) {
            int x = std::bit_width(n) - 1;
            count += x << (x - 1);
            n -= 1 << x;
            count += n + 1;
        }
        return count;
}

Python

def count_set_bits(n: int) -> int:
    count = 0
    while n > 0:
        x = n.bit_length() - 1  # аналог std::bit_width(n) - 1
        # коли x == 0, доданок дорівнює 0; Python (на відміну від C++)
        # не дозволяє від'ємний зсув, тож обробляємо цей випадок окремо.
        if x > 0:
            count += x << (x - 1)
        n -= 1 << x
        count += n + 1
    return count

TypeScript

function countSetBits(n: number): number {
  let count = 0;
  while (n > 0) {
    // 32 - clz32(n) - 1 — аналог std::bit_width(n) - 1
    const x = 31 - Math.clz32(n);
    count += x << (x - 1);
    n -= 1 << x;
    count += n + 1;
  }
  return count;
}

Go

package main

import "math/bits"

func countSetBits(n int) int {
	count := 0
	for n > 0 {
		x := bits.Len(uint(n)) - 1 // аналог std::bit_width(n) - 1
		// коли x == 0, доданок дорівнює 0; Go (на відміну від C++)
		// панікує на від'ємному зсуві, тож обробляємо цей випадок окремо.
		if x > 0 {
			count += x << (x - 1)
		}
		n -= 1 << x
		count += n + 1
	}
	return count
}

Додаткові трюки

• $n ~\&~ (n + 1)$ очищає всі кінцеві одиниці: $0011~0111_2 \rightarrow 0011~0000_2$.
• $n ~|~ (n + 1)$ встановлює останній очищений біт: $0011~0101_2 \rightarrow 0011~0111_2$.
• $n ~\&~ -n$ вилучає останній встановлений біт: $0011~0100_2 \rightarrow 0000~0100_2$.

Багато інших можна знайти в книзі Hacker's Delight.

Підтримка в мові та компіляторі

C++ підтримує деякі з цих операцій починаючи з C++20 через стандартну бібліотеку bit:

• has_single_bit: перевіряє, чи є число степенем двійки
• bit_ceil / bit_floor: заокруглення вгору/вниз до найближчого степеня двійки
• rotl / rotr: циклічний зсув бітів у числі
• countl_zero / countr_zero / countl_one / countr_one: підрахунок ведучих/кінцевих нулів/одиниць
• popcount: підрахунок кількості встановлених бітів

Крім того, у деяких компіляторах є також наперед визначені функції, що допомагають працювати з бітами. Наприклад, GCC визначає список у Built-in Functions Provided by GCC, які працюють і в старіших версіях C++:

• __builtin_popcount(unsigned int) повертає кількість встановлених бітів (__builtin_popcount(0b0001'0010'1100) == 4)
• __builtin_ffs(int) знаходить індекс першого (крайнього правого) встановленого біта (__builtin_ffs(0b0001'0010'1100) == 3)
• __builtin_clz(unsigned int) кількість ведучих нулів (__builtin_clz(0b0001'0010'1100) == 23)
• __builtin_ctz(unsigned int) кількість кінцевих нулів (__builtin_ctz(0b0001'0010'1100) == 2)
• __builtin_parity(x) парність (парна чи непарна) кількості одиниць у двійковому представленні числа

Зауважте, що деякі з операцій (як функції C++20, так і вбудовані функції компілятора) можуть бути доволі повільними в GCC, якщо ви не ввімкнете відповідну ціль компілятора через #pragma GCC target("popcnt").

Задачі для практики

• Codeforces - Raising Bacteria
• Codeforces - Fedor and New Game
• Codeforces - And Then There Were K

Відеоматеріали