Подсчёт битов в одном целом числе

 

Я

Алиса

Скорее всего, ты имеешь в виду подсчёт количества единичных битов (popcount) в числе или в массиве битов с использованием парадигмы «разделяй и властвуй».

Есть два распространённых контекста:

1. Подсчёт битов в одном целом числе (классический хак с масками).

2. Подсчёт суммы битов в массиве/строке битов через рекурсивное деление диапазона.

Ниже разберу оба варианта.

---

Вариант 1. Подсчёт битов в числе (алгоритм Брайана Кернигана / битовые маски)

Это самый известный «разделяй и властвуй» для одного числа. Идея в том, чтобы параллельно суммировать биты, сначала объединяя соседние биты в пары, потом пары в четвёрки и так далее.

Допустим, у нас 32-битное число x.

1. Разделение на пары битов. Считаем количество единиц в каждой паре (0–2):

   c

   x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
   // 0x5 = 0101 в двоичной — маска для пар
   

2. Объединение пар в группы по 4 бита. Суммируем результаты из предыдущего шага:

   c

   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
   // 0x3 = 0011 — маска для групп по 4
   

3. Группы по 8 битов:

   c

   x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
   

4. Группы по 16 битов:

   c

   x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
   

5. Финальное сложение (32 бита):

   c

   x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
   

Почему это «разделяй и властвуй»: на каждом шаге мы «властвуем» над всё большими группами битов, объединяя результаты подзадач меньшего размера. Сложность — $O(\log w)$, где $w$ — разрядность числа (для 32 бит это ровно 5 шагов).

---

Вариант 2. Подсчёт единиц в массиве битов/чисел рекурсивно

Если задача — посчитать общее число единичных битов в большом массиве (или в длинной битовой строке), можно применить классический рекурсивный «разделяй и властвуй»:

1. Разделить: разбить массив на две половины.

2. Властвовать (рекурсия): рекурсивно посчитать количество единиц в левой и правой половине.

3. Объединить: сложить результаты двух половин.

Псевдокод

python

def count_ones(arr, left, right):
    # Базовый случай: пустой диапазон
    if left > right:
        return 0
    
    # Базовый случай: один элемент
    if left == right:
        # Если элемент — число, считаем его биты (например, bin(x).count('1'))
        # Или если это уже бит (0/1), просто возвращаем его
        return count_bits_in_number(arr[left])
    
    mid = (left + right) // 2
    left_count = count_ones(arr, left, mid)
    right_count = count_ones(arr, mid + 1, right)
    
    return left_count + right_count

Пример на Python (полный рабочий код)

python

def count_bits_in_int(n: int) -> int:
    # Можно использовать встроенный метод, а можно битовую версию
    return bin(n).count('1')

def count_ones_divide_and_conquer(arr, left: int, right: int) -> int:
    if left > right:
        return 0
    if left == right:
        return count_bits_in_int(arr[left])
    
    mid = (left + right) // 2
    left_sum = count_ones_divide_and_conquer(arr, left, mid)
    right_sum = count_ones_divide_and_conquer(arr, mid + 1, right)
    
    return left_sum + right_sum

# Пример использования
numbers = [3, 7, 8, 15]  # 011, 111, 1000, 1111
total = count_ones_divide_and_conquer(numbers, 0, len(numbers) - 1)
print(total)  # Вывод: 3 + 3 + 1 + 4 = 11

---

Важные нюансы

• Сложность. Для массива из $n$ элементов рекурсивный подход имеет сложность $O(n)$ (так как каждый элемент всё равно нужно обработать хотя бы один раз). Глубина рекурсии — $O(\log n)$.

• Практическое применение. Рекурсивный «разделяй и властвуй» полезен, если:

  • Нужно распараллелить задачу (левую и правую половину можно считать на разных ядрах).

  • Есть дополнительные условия (например, считать биты только в тех поддиапазонах, где выполняется какое-то свойство).

• Для одного числа битовая версия (Вариант 1) эффективнее, чем цикл по всем битам, и не требует рекурсии.

Если скажешь, какая именно задача у тебя (одно число, массив, параллельные вычисления, язык программирования), могу адаптировать алгоритм точнее.

Я

Алиса

Тут есть небольшое недопонимание: 0x5 (это 0101 в двоичной записи) — это не сумма битов, а маска, которая помогает эту сумму посчитать. И она работает не с «3 битами», а с парами битов (по 2 бита).

Давай разберёмся по шагам, как это работает в алгоритме «разделяй и властвуй» для подсчёта единичных битов.

---

Что такое маска 0x55555555

В шестнадцатеричной системе:

• 0x5 = 0101 в двоичной.

• 0x55 = 0101 0101.

• 0x55555555 — это 32-битная маска, где единицы стоят через один бит: 01010101...0101.

Эта маска нужна, чтобы выделить биты на чётных позициях (0-й, 2-й, 4-й и т. д.) в каждой паре.

Как работает первый шаг алгоритма

Возьмём одну пару битов из числа x. Пусть это будут биты b1 b0 (где b1 — старший бит пары, b0 — младший).

Формула:

c

x = (x & 0x55555555) + ((x >> 1) & 0x55555555);

Разберём, что происходит с каждой парой:

1. x & 0x55555555:

   • Маска 01 пропускает только младший бит (b0) каждой пары.

   • Старший бит (b1) в этой части обнуляется.

2. (x >> 1) & 0x55555555:

   • Сначала сдвигаем число вправо на 1 бит: теперь b1 оказывается на месте b0.

   • Потом применяем ту же маску 01, чтобы оставить только этот бит.

3. Складываем результаты:

   • В итоге в каждой 2-битной ячейке оказывается сумма этих двух битов: b1 + b0.

Примеры для каждой возможной пары

Пара битов (b1 b0)	x & 0x... (берём b0)	(x>>1) & 0x... (берём b1)	Сумма (результат в 2 битах)
00	0	0	00 (0)
01	1	0	01 (1)
10	0	1	01 (1)
11	1	1	10 (2)

Видно, что после этого шага в каждой паре битов хранится количество единиц в этой паре (число от 0 до 2).

---

Почему не «для 3 битов»?

Потому что:

• Маска 0x5 = 0101₂ имеет период 2 бита: один бит включён, следующий выключен.

• Она специально создана, чтобы работать с парами битов, а не тройками.

• Если бы мы хотели работать с тройками, маска была бы совсем другой (и такой простой схемы сложения уже не получилось бы).

На следующем шаге алгоритма мы уже работаем с группами по 4 бита и используем маску 0x33333333 (00110011...), потому что теперь в каждой 2-битной ячейке у нас уже хранится число (0, 1 или 2), и нам нужно сложить соседние ячейки.

---

Итог

• 0x5 — не сумма, а маска. Она выделяет нужные биты, чтобы их можно было сложить.

• Работает с парами битов (2 бита), а не с 3.

• Цель шага — в каждой паре битов получить число, равное количеству единиц в этой паре.

Если хочешь, могу показать пример на конкретном числе (например, 0b1011), чтобы увидеть, как меняются биты после каждого шага.

#include <stdint.h>

int popcount_64(uint64_t x) {

    // Шаг 1: считаем единицы в парах битов (маска 0x55...55)

    x = (x & 0x5555555555555555ULL) + ((x >> 1) & 0x5555555555555555ULL);

    // Шаг 2: считаем в четвёрках (маска 0x33...33)

    x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL);

    // Шаг 3: считаем в восьмёрках (маска 0x0F...0F)

    x = (x & 0x0F0F0F0F0F0F0F0FULL) + ((x >> 4) & 0x0F0F0F0F0F0F0F0FULL);

    // Шаг 4: считаем в 16‑битных группах

    x = (x & 0x00FF00FF00FF00FFULL) + ((x >> 8) & 0x00FF00FF00FF00FFULL);

    // Шаг 5: считаем в 32‑битных группах

    x = (x & 0x0000FFFF0000FFFFULL) + ((x >> 16) & 0x0000FFFF0000FFFFULL);

    // Шаг 6: финальное сложение двух 32‑битных половин

    x = (x & 0x00000000FFFFFFFFULL) + ((x >> 32) & 0x00000000FFFFFFFFULL);

    return (int)x;

}

#include <stdint.h>

#include <stdio.h>

// Таблица позиций для 64 бит (размер 64)

static const int deBruijnBitPosition[64] = {

    0,  1,  48, 2,  57, 49, 28, 3,

    61, 58, 50, 42, 38, 29, 17, 4,

    62, 55, 59, 36, 53, 51, 43, 22,

    45, 39, 33, 30, 24, 18, 12, 5,

    63, 47, 56, 27, 60, 41, 37, 16,

    54, 35, 52, 21, 44, 32, 23, 11,

    46, 26, 40, 15, 34, 20, 10, 25,

    14, 19, 9,  13, 8,  7,  6

};

// Магическое число для 64 бит

#define DEBRUIJN_MAGIC 0x03F79D71B4CB0A89ULL

int get_lsb_de_bruijn(uint64_t v) {

    if (v == 0) return -1; // Обработка нуля

    

    // 1. Изолируем младший бит (классический трюк)

    v = v & -v;

    

    // 2. Умножаем на магическое число.

    // Результат умножения сдвинется так, что старшие 6 бит будут равны индексу.

    // Это работает из-за свойств последовательности Де Брёйна.

    return deBruijnBitPosition[(uint64_t)(v * DEBRUIJN_MAGIC) >> 58];

}

int main() {

    uint64_t tests[] = {1, 2, 4, 8, 12, 0x8000000000000000ULL};

    for (int i = 0; i < 6; ++i) {

        printf("Value: %llu, LSB index: %d\n", tests[i], get_lsb_de_bruijn(tests[i]));

    }

    return 0;

}