โปรแกรม C/C++ นับจำนวน Set Bits ในจำนวนเต็ม

ที่นี่เราจะดูวิธานับจำนวน Set Bits ในจำนวนเต็ม Set bits คือบิต 1 ในรูปแบบไบนารี เช่น 13 = 1101 มี set bits 3 ตัว

วิธีแก้: เลข shift right ไปเรื่อยๆ ถ้า LSB เป็น 1 ให้เพิ่ม count จนกว่าเลขจะกลายเป็น 0

อัลกอริทึม

countSetBit()

begin
    count := 0
    while n is not 0, do
        if LSB of n is set, then
            count := count + 1
        end if
        n := n after shifting 1 bit to right
    done
    return count
end

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

#include <iostream>
using namespace std;

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

int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    cout << "Number of set bits: " << count_set_bit(n);
}

ผลลัพธ์

Enter a number: 29
Number of set bits: 4

หมายเหตุ: โค้ดนี้ compile ได้ใน C แต่ใน C++ อาจ error ว่า "too many arguments" เนื่องจาก built-in function `__builtin_popcount` หรือ overload อื่น