JuniorКодОчень частоЕщё не отвечали
Посчитайте количество единиц (set bits) в числе
Верните количество установленных битов (единиц в двоичном представлении) 32-битного беззнакового целого.
Требования:
прохода O(32) на разреженных входах.
- Стремитесь к O(k), где k — число единиц — лучше фиксированного побитового
- Используйте беззнаковый тип, чтобы избежать UB при сдвиге отрицательных значений.
- Не вызывайте
std::popcount; реализуйте подсчёт самостоятельно.
int countBits(uint32_t n) {
// ваш код здесь
}Допишите реализацию.
Трюк Кернигана: n &= n - 1 сбрасывает младший установленный бит, повторяем до n == 0 — O(k), где k — количество единиц. В C++20 лучше std::popcount, компилируется в одну инструкцию.
- ✗Использовать наивный побитовый цикл O(32) вместо трюка Кернигана O(set bits)
- ✗Некорректно обрабатывать отрицательные числа при знаковом int — используйте unsigned
- ✗Забывать о
std::popcountв C++20, который делает задачу однострочной
- →Как проверить, является ли число степенью двойки, используя побитовые операции?
- →Что делает
n & (n-1)в общем случае?
Оглавление
Задача
Напишите функцию, принимающую целое число и возвращающую количество установленных битов (единиц в двоичном представлении).
Решение
#include <bit> // std::popcount (C++20)
#include <cstdint>
#include <cassert>
// --- Modern (C++20) ---
int countBitsModern(uint32_t n) {
return std::popcount(n);
}
// --- Kernighan's trick (pre-C++20) ---
int countBitsKernighan(uint32_t n) {
int count = 0;
while (n) {
n &= n - 1; // clears the lowest set bit
++count;
}
return count;
}
// --- Naive (for illustration only) ---
int countBitsNaive(uint32_t n) {
int count = 0;
while (n) {
count += n & 1;
n >>= 1;
}
return count;
}
int main() {
assert(countBitsKernighan(0) == 0);
assert(countBitsKernighan(1) == 1);
assert(countBitsKernighan(0xFF) == 8);
assert(countBitsKernighan(0b1011) == 3);
assert(countBitsKernighan(UINT32_MAX)== 32);
}Ключевые моменты
n &= n - 1сбрасывает ровно один (самый младший) установленный бит за итерацию.- Работает за O(k) итераций, где k — число установленных битов, а не за O(32).
- На практике предпочитайте
std::popcount<uint32_t>(C++20) — компилируется в одну инструкциюPOPCNTна x86. - Используйте беззнаковые типы, чтобы избежать UB при сдвиге отрицательных значений.
Оглавление
