কোন একটি সংখ্যাকে বাইনারিতে প্রকাশ করলে সেখানে শুধুমাত্র $০$ অথবা $১$ থাকে। একটি বাইনারি সংখ্যায় কতগুলো $১$ আছে, তার মানই সংখ্যাটির সেট বিট । সেট বিট কাউন্ট করার বেশ কিছু উপায় আছে । এর মধ্যে দুটো উপায় নিয়ে আমি আলোচনা করবো।
মেথড ০১. (ব্রুটফোর্স মেথড)
এটি খুবই সহজ একটি উপায়। একটি সংখ্যার সবগুলো বিট পর্যায়ক্রমে চেক করতে হবে। যদি নির্দিস্ট বিটটি সেট অবস্থায় থাকে। তাহলে সেট বিট কাউন্টারের মান $১$ বাড়াতে হবে। কোন একটি বিট সাধারণত দুটো অবস্থায় থাকতে পারে – সেট অবস্থা আর ক্লিয়ার অবস্থা। যদি বিটটি $০$ শূন্য তাহলে বলা হবে ক্লিয়ায় মোড আর $১$ হলে বলা হবে সেট মোড। তুমি ডেসিম্যাল টু বাইনারি কনভার্সন জেনে থাকলে বিট চেক করা তোমার জন্য কোন কাজই না। কোন পূর্ণ সংখ্যাকে $২$ দিয়ে ভাগ দিলে হয় ভাগশেষ $১$ থাকবে না হয় $০$ থাকবে। $২$ দিয়ে বারবার ভাগ করেই বাইনারি টু ডেসিম্যাল কনভার্সন করা হয়।
ধর, তোমার কাছে একটি সংখ্যা $১১$ আছে। সংখ্যাটিকে $২$ দিয়ে ভাগ দিলে ভাগফল হবে $৫$ আর ভাগশেষ হবে $১$। যেহেতু ভাগশেষ $১$ তাহলে সেট বিটের মান হবে $১$। এবার $৫$ কে দুই দিয়ে ভাগ দিলে ভাগফল হবে $২$ আর ভাগশেষ হবে $১$। এবারো যেহেতু ভাগশেষের মান $১$ পাওয়া গিয়েছে, তাহলে সেট বিট কাউন্টারের মান বেড়ে হবে $২$। এখন, $২$ কে $২$ দ্বারা ভাগ দিলে ভাগফল হবে $১$ আর ভাগশেষ হবে $০$। সেট বিট কাউন্টারের মান যা ছিলো তাই থাকবে । এখন আবার $১$ কে $২$ দ্বারা ভাগ দিলে ভাগফল হবে $০$ আর ভাগশেষ হবে $১$। সেট বিট কাউন্টারের মান ১ বেড়ে, মোট হবে ০৩। তাহলে সংখ্যা ১১ তে সেট বিটের মোট সংখ্যা হলো ৩।
$১১$ কে বাইনারিতে প্রকাশ করলে – $১০১১$। এখানে $৩$ টি সেট বিট (১) আছে। তাই মোট সেট বিট সংখ্যা $৩$।
মেথড ০১ এর কোডিং
উপরের কথাগুলো বুঝে থাকলে তুমি ডেসিম্যাল টু বাইনারি কনভার্শন ও বুঝে ফেলার কথা। তোমার এই মুহুর্তে কাজ হল – ডেসিম্যাল টু বাইনারি কনভার্শনের প্রোগ্রাম লিখে ফেলা।
মেথড ০২. Brian Kernighan এলগরিদম
Brian Kernighan’s এলগরিদম প্রত্যেকবার একটি বিওয়াইজ এন্ড (&) অপারেশন চালায় ইনপুটেড ইন্টিজার $n$ এবং $n-1$ এর মাঝে এবং কাউন্টারের মান $১$ করে বাড়ায়। এই সল্যুশনে যতটা সেট বিট আছে ঠিক ততবার লুপ আইটারেট করে, যা আগের মেথডের চেয়ে অনেক বেশী দ্রুত। আমরা যদি $১৭$ এর সেট বিট কাউন্ট করতে যাই, তাহলে Brian Kernighan’s এলগরিদম অনুযায়ী লুপ চলবে $২$ বার, অথচ আগের মেথড অনুযায়ী লুপ $৫$ বার ঘুরবে।
সেট বিট নির্ণয়ের ধাপসমূহ –
১. ইনিশিয়ালাইজ
count = 0২. যদি ইন্টিজার $n$ শূন্য না হয় –
ক) $n$ এর সাথে $n-1$ বিটওয়াইজ এন্ড $(\&)$ কর এবং প্রাপ্য মান $n$ এ এসাইন কর।
$n = n \& (n-1)$ খ) কাউন্টারের(count)এর মান $১$ বাড়াও।
গ) স্টেপ $২$ আবার তে ফিরে যাও।
যদি $n$ শূন্য হয়, তাহলে আমরা উত্তর পেয়ে গেছি।৩. এবার, কাউন্টারের (count) মান রিটার্ন করো।