Count set bits in an integer in C++: นับ bit 1 ในจำนวนเต็ม

กำหนดจำนวนเต็ม num นับจำนวน bit 1 (set bits) ใน binary representation

ตัวอย่าง: 50 (110010) → 3 bits, 10 (1010) → 2 bits

วิธีแก้ปัญหา

• Built-in: __builtin_popcount(num) (GCC/Clang)
• Manual: Brian Kernighan's algorithm: while(n){ n &= n-1; count++; }

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int countSetBits(unsigned int n) {
    int count = 0;
    while(n) {
        n &= (n - 1);
        count++;
    }
    return count;
}

int main() {
    cout << countSetBits(50) << endl; // 3
    cout << countSetBits(10) << endl; // 2
}

Input

50

Output

3