C++-এ পূর্ণসংখয়ায় সেট বিট গণনা: ব্রায়ান কের্নিঘ্যান অ্যালগরিদম

একটি পূর্ণসংখ্যা দেওয়া আছে। এর বাইনারি রিপ্রেজেন্টেশনে কতটি ১ (সেট বিট) আছে তা বের করুন।

উদাহরণ

num=50 → Binary: 00110010 → ৩টি সেট বিট

num=10 → Binary: 00001010 → ২টি সেট বিট

পদ্ধতিগুলো

১. বেসিক লুপ (O(log n))

while (num) {
    count += num & 1;
    num >>= 1;
}

২. ব্রায়ান কের্নিঘ্যান অ্যালগরিদম (O(set bits))

while (num) {
    num &= (num - 1);  // সবচেয়ে ডানপাশের সেট বিট ক্লিয়ার
    count++;
}

৩. বিল্ট-ইন ফাংশন

__builtin_popcount(num);  // GCC/Clang

C++ বাস্তবায়ন (ব্রায়ান কের্নিঘ্যান)

#include 
using namespace std;

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

int main() {
    int num = 50;
    cout << "Set bits: " << countSetBits(num);
    return 0;
}

তুলনা