Битовые операции
Битовые операции
Целое число в памяти компьютера хранится как последовательность двоичных разрядов (битов). Побитовая операция применяет логическую функцию к битам с одинаковым номером, независимо для каждого разряда. Разряды нумеруются справа налево, начиная с нуля: бит с номером $0$ самый младший. Побитовые операции удобны, когда число задаёт набор флагов или подмножество.
Логические операции над битами
Побитовое И (&) даёт единицу только тогда, когда оба бита равны единице. Побитовое ИЛИ (|) даёт единицу, если хотя бы один бит равен единице. Исключающее ИЛИ (^) даёт единицу, если биты различны. Побитовое НЕ (~) меняет каждый бит на противоположный и применяется к одному числу.
Пример: $a = 12 = 1100_2$, $b = 10 = 1010_2$. Тогда $a \,\&\, b = 1000_2 = 8$, $a \mid b = 1110_2 = 14$, $a \oplus b = 0110_2 = 6$. Результат $\sim a$ зависит от ширины записи: в восьми битах $\sim a = 11110011_2 = 243$.
Сдвиги
Сдвиг влево x << k сдвигает биты числа на $k$ разрядов влево и дописывает справа $k$ нулей. Для беззнакового числа, у которого при сдвиге не теряются единичные биты, это умножение на $2^k$. Сдвиг вправо x >> k отбрасывает $k$ младших битов; для неотрицательного $x$ результат равен $\lfloor x / 2^k \rfloor$. В примерах сдвиги применяются к беззнаковым числам.
Дополнительный код
Отрицательные целые числа обычно хранятся в дополнительном коде (см. урок о представлении чисел в памяти). В $n$-битной записи дополнительный код отрицательного числа $x$ равен $2^n + x$. Отсюда $-x = \sim x + 1$ по модулю $2^n$: чтобы получить противоположное число, нужно инвертировать все биты и прибавить единицу.
Для восьми битов: $5 = 00000101_2$, $\sim 5 = 11111010_2$, $\sim 5 + 1 = 11111011_2$. Число $11111011_2 = 2^8 - 5 = 251$ является записью числа $-5$.
Реализация на Python
# Побитовые операции над целыми числами и двоичная запись результата в восьми битах
def to_bits(x, width):
"""Двоичная запись младших width битов числа x; отрицательные числа записываются в дополнительном коде."""
return format(x & ((1 << width) - 1), f"0{width}b")
def main():
a = 12 # 00001100
b = 10 # 00001010
results = [
("a", a),
("b", b),
("a & b", a & b),
("a | b", a | b),
("a ^ b", a ^ b),
("~a", ~a),
("a << 1", a << 1),
("b >> 1", b >> 1),
("-5", -5),
]
for name, value in results:
print(f"{name:<7} {to_bits(value, 8)} {value & 0xFF}")
if __name__ == "__main__":
main()
Реализация на C++
// Побитовые операции над беззнаковыми числами и двоичная запись результата в восьми битах
#include <cstdio>
#include <string>
// Двоичная запись младших width битов числа x
std::string to_bits(unsigned int x, int width) {
std::string bits;
for (int i = width - 1; i >= 0; --i) {
bits += ((x >> i) & 1u) ? '1' : '0';
}
return bits;
}
void show(const char* name, unsigned int value) {
std::printf("%-7s %s %u\n", name, to_bits(value, 8).c_str(), value & 0xFFu);
}
int main() {
unsigned int a = 12; // 00001100
unsigned int b = 10; // 00001010
show("a", a);
show("b", b);
show("a & b", a & b);
show("a | b", a | b);
show("a ^ b", a ^ b);
show("~a", ~a);
show("a << 1", a << 1);
show("b >> 1", b >> 1);
show("-5", static_cast<unsigned int>(-5));
return 0;
}
Алгоритмы над целыми числами
Несколько стандартных приёмов позволяют быстро получать сведения о двоичной записи целого числа. Во всех формулах $n$ — неотрицательное целое число.
Сброс самого младшего единичного бита
Вычитание единицы заменяет самый младший единичный бит числа нулём, а все нули справа от него — единицами. Поэтому выражение n & (n - 1) равно $n$ с удалённым самым младшим единичным битом. Например, $12 = 1100_2$, $12 - 1 = 1011_2$, и $12 \,\&\, 11 = 1000_2 = 8$.
Проверка степени двойки
Число $n > 0$ является степенью двойки тогда и только тогда, когда в его записи ровно один единичный бит, то есть $n \,\&\, (n - 1) = 0$. Условие $n > 0$ нужно: для $n = 0$ выражение $n \,\&\, (n - 1)$ тоже равно нулю, и без этой проверки ноль был бы принят за степень двойки.
Самый младший единичный бит
В дополнительном коде $-n = \sim n + 1$. Биты числа $n$ ниже самого младшего единичного бита равны нулю, поэтому у $-n$ они тоже нули, а единица стоит в той же позиции $k$. Выше позиции $k$ биты $-n$ противоположны битам $n$. Значит, $n \,\&\, (-n)$ содержит только один единичный бит — самый младший из битов $n$, то есть равно $2^k$. Например, для восьми битов $12 \,\&\, (-12) = 00001100_2 \,\&\, 11110100_2 = 00000100_2 = 4$.
Подсчёт единичных битов
Сброс самого младшего единичного бита, повторённый до нуля, подсчитывает единицы: каждый шаг удаляет одну единицу, поэтому число шагов равно числу единичных битов. Время работы пропорционально этому числу, а оно не превосходит числа разрядов $n$. Готовые средства тоже есть: начиная с C++20 функция std::popcount из заголовка <bit> считает единичные биты (см. cppreference), а в Python версии 3.10 и новее это метод int.bit_count() (см. документацию Python).
Реализация на Python
# Алгоритмы над целыми числами на битовых операциях
def is_power_of_two(n):
"""Истинно, если n (n >= 0) является степенью двойки: 1, 2, 4, 8, ..."""
# У степени двойки ровно один единичный бит; n & (n - 1) убирает самый младший из них
return n > 0 and (n & (n - 1)) == 0
def lowest_set_bit(n):
"""Возвращает 2^k, где k — номер самого младшего единичного бита n; для n = 0 возвращает 0."""
# В дополнительном коде -n = ~n + 1, поэтому n & -n оставляет только самый младший единичный бит
return n & -n
def count_set_bits(n):
"""Возвращает количество единичных битов в двоичной записи неотрицательного n."""
count = 0
while n:
# Каждая итерация удаляет самый младший единичный бит
n &= n - 1
count += 1
return count
def main():
for n in [0, 1, 6, 8, 12, 16, 96]:
power = "да" if is_power_of_two(n) else "нет"
print(f"n = {n:3}: степень двойки: {power}, младший бит {lowest_set_bit(n):3}, единиц {count_set_bits(n)}")
if __name__ == "__main__":
main()
Реализация на C++
// Алгоритмы над целыми числами на битовых операциях
#include <cstdio>
// Истинно, если n является степенью двойки (1, 2, 4, 8, ...)
bool is_power_of_two(unsigned int n) {
// У степени двойки ровно один единичный бит; n & (n - 1) убирает самый младший из них
return n > 0 && (n & (n - 1)) == 0;
}
// Число 2^k, где k — номер самого младшего единичного бита n; для n = 0 возвращает 0
unsigned int lowest_set_bit(unsigned int n) {
// Для беззнакового типа 0u - n равно -n по модулю 2^N (N — число битов в unsigned int)
return n & (0u - n);
}
// Количество единичных битов в двоичной записи n
int count_set_bits(unsigned int n) {
int count = 0;
while (n != 0) {
// Каждая итерация удаляет самый младший единичный бит
n &= n - 1;
++count;
}
return count;
}
int main() {
const unsigned int values[] = {0, 1, 6, 8, 12, 16, 96};
for (unsigned int n : values) {
std::printf("n = %3u: степень двойки: %s, младший бит %3u, единиц %d\n", n, is_power_of_two(n) ? "да" : "нет", lowest_set_bit(n), count_set_bits(n));
}
return 0;
}