Анализ поведения функции

Условие

Необходимо выяснить, что делает функция f и для чего она может быть использована.

#include <iostream>

int f(int x) {
    int count = 0;
    while (x) {
        count++;
        x = x & (x - 1);
    }
    return count;
}

int main() {
    std::cout << f(11) << std::endl;
}

Ответ

Функция считает количество единичных битов для неотрицательного x. Для 11, то есть двоичного 1011, она вернёт и напечатает 3.

Выражение x & (x - 1) очищает младший установленный бит. Цикл проходит ровно столько итераций, сколько единиц было в числе: 1011 → 1010 → 1000 → 0000.

Такой подсчёт применяют к битовым маскам, флагам и множествам, представленным битами. Для произвольных битовых значений лучше использовать unsigned: в исходном варианте отрицательные int могут привести к знаковому переполнению при вычитании. В C++20 для беззнаковых целых есть std::popcount из .