Я использую приведенный ниже код, который более интуитивно понятен.
int countSetBits(int n) {
return !n ? 0 : 1 + countSetBits(n & (n-1));
}
Логика: n & amp; (n-1) сбрасывает последний бит набора n.
P.S: Я знаю, что это не O (1) решение, хотя и интересное решение.