comment 0

পুর্ণ সংখ্যার সেট বিট নির্ণয়

কোন একটি সংখ্যাকে বাইনারিতে প্রকাশ করলে সেখানে শুধুমাত্র ০ অথবা ১ থাকে । একটি বাইনারি সংখ্যায় কতগুলো ১ আছে, তার মানই সংখ্যাটির সেট বিট । সেট বিট কাউন্ট করার বেশ কিছু উপায় আছে । এর মধ্যে দুটো উপায় নিয়ে আমি আলোচনা করবো ।

মেথড ০১ঃ (সিম্পল মেথড)
এটি খুবই সহজ একটি উপায় । একটি সংখ্যার সবগুলো বিট পর্যায়ক্রমে চেক করতে হবে । যদি নির্দিস্ট বিটটি সেট অবস্থায় থাকে । তাহলে সেট বিট কাউন্টারের মান ১ বাড়াতে হবে । কোন একটি বিট সাধারণত দুটো অবস্থায় থাকতে পারে – সেট অবস্থা আর ক্লিয়ার অবস্থা । যদি বিটটি ০ শূন্য তাহলে বলা হবে ক্লিয়ায় মোড আর ১ হলে বলা হবে সেট মোড । তুমি ডেসিম্যাল টু বাইনারি কনভার্সন জেনে থাকলে বিট চেক করা তোমার জন্য কোন কাজই না । কোন পূর্ণ সংখ্যাকে ২ দিয়ে ভাগ দিলে হয় ভাগশেষ ১ থাকবে না হয় ০ থাকবে । ২ দিয়ে বারবার ভাগ করেই বাইনারি টু ডেসিম্যাল কনভার্সন করা হয় ।
ধর, তোমার কাছে একটি সংখ্যা ১১ আছে । সংখ্যাটিকে ২ দিয়ে ভাগ দিলে ভাগফল হবে ৫ আর ভাগশেষ হবে ১ । যেহেতু ভাগশেষ ১ তাহলে সেট বিটের মান হবে ১ । এবার ৫ কে দুই দিয়ে ভাগ দিলে ভাগফল হবে ২ আর ভাগশেষ হবে ১ । এবারো যেহেতু ভাগশেষের মান ১ পাওয়া গিয়েছে, তাহলে সেট বিট কাউন্টারের মান বেড়ে হবে ২ । এখন, ২ কে ২ দ্বারা ভাগ দিলে ভাগফল হবে ১ আর ভাগশেষ হবে ০ । সেট বিট কাউন্টারের মান যা ছিলো তাই থাকবে । এখন আবার ১ কে ২ দ্বারা ভাগ দিলে ভাগফল হবে ০ আর ভাগশেষ হবে ১ । সেট বিট কাউন্টারের মান ১ বেড়ে, মোট হবে ০৩ । তাহলে সংখ্যা ১১ তে সেট বিটের মোট সংখ্যা হলো ৩ ।

১১ কে বাইনারিতে প্রকাশ করলে – ১০১১ । এখানে ৩ টি সেট বিট (১) আছে । তাই মোট সেট বিট সংখ্যা ৩ ।
মেথড ০১ এর কোডিং

উপরের কথাগুলো বুঝে থাকলে তুমি ডেসিম্যাল টু বাইনারি কনভার্শন ও বুঝে ফেলার কথা । তোমার এই মুহুর্তে কাজ হল – ডেসিম্যাল টু বাইনারি কনভার্শনের প্রোগ্রাম লিখে ফেলা ।

মেথড ০২ঃ 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) মান রিটার্ন করো ।

Comments

comments

Leave a Reply

Your email address will not be published. Required fields are marked *