В этой статье блога мы рассмотрим различные эффективные методы решения проблемы «количество 1 бит» в LeetCode с использованием C++. Задача требует, чтобы мы подсчитали количество бит, которым присвоено значение 1 в заданном целом числе.

Метод 1: наивный подход
Самый простой подход – перебирать каждый бит целого числа и подсчитывать количество бит, установленных в 1. Вот код:

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n != 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

Метод 2: алгоритм Брайана Кернигана
Алгоритм Брайана Кернигана представляет собой оптимизированный подход, который более эффективно подсчитывает количество установленных бит в целом числе. Он работает путем многократного вычитания 1 из числа и выполнения побитовой операции И с исходным числом. Вот код:

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

Метод 3: Таблица поиска
Если нам нужно подсчитать количество бит в нескольких целых числах, мы можем предварительно вычислить количество бит для всех возможных значений (от 0 до 255) и сохранить их в таблице поиска. Затем для любого целого числа мы можем разделить его на 8-битные сегменты и посчитать биты, используя справочную таблицу. Вот код:

int hammingWeight(uint32_t n) {
    int count = 0;
    uint8_t* lookupTable = new uint8_t[256]; // Precomputed lookup table
    // Initialize lookup table with number of bits for each possible 8-bit value
    // Count bits in 8-bit segments
    count += lookupTable[n & 0xFF];
    count += lookupTable[(n >> 8) & 0xFF];
    count += lookupTable[(n >> 16) & 0xFF];
    count += lookupTable[(n >> 24) & 0xFF];
    delete[] lookupTable;
    return count;
}

Метод 4: встроенная функция
В C++ мы также можем использовать встроенную функцию bitset::count()для подсчета количества установленных бит в целом числе. Этот метод преобразует целое число в его двоичное представление и подсчитывает количество единиц. Вот код:

#include <bitset>
int hammingWeight(uint32_t n) {
    std::bitset<32> bits(n);
    return bits.count();
}

В этой статье мы рассмотрели несколько методов решения проблемы «Количество 1 бит» в LeetCode с использованием C++. Представленные решения включают в себя наивный подход, алгоритм Брайана Кернигана, подход с использованием таблицы поиска и использование встроенной функции bitset::count(). В зависимости от конкретных требований и ограничений вашего приложения вы можете выбрать наиболее подходящий метод.