বিটের মজা, মজার বিট

আমরা যে কম্পিউটার প্রোগ্রামিং করি, হাজার হাজার লাইনের কোড লিখে জটিল, অস্থির সব এপস, সফটওয়্যার, গেমস বানাই 😀 ; গুগল, Bing কিংবা আমাদের দেশের পিপীলিকা অথবা চড়কির মত সার্চ ইঞ্জিন বানাই 😉 সবকিছুর মূলে যে অসাধারণ ক্ষমতাধর জিনিসটি লুকিয়ে আছে তা হল বিট : ০ আর ১. আমরা যে সংখ্যা(int, double, float, long long) এবং ক্যারেক্টার(char, string) লিখে থাকি, সবই কম্পিউটারে ০, ১ দিয়েই স্টোর করা থাকে। এই বিট ব্যবহার করে বিভিন্ন ধরণের কাজ করা হয়ে থাকে, যেমন – লো-লেভেল ডিভাইস কন্ট্রোল, ডাটা কম্প্রেশন, এনক্রিপশন, নেটওয়ার্কিং ইত্যাদি! বিট নিয়ে যেকোন ধরণের অপারেশনকে প্রোগ্রামিংয়ের ভাষায় বলা হয় বিট ম্যানিপুলেশন।

 

বিটওয়াইজ অপারেশন – বিট ম্যানিপুলেশনের হৃদয় ❤
বিট ম্যানিপুলেশনের হৃদয় হচ্ছে বিটওয়াইজ অপারেশন, তাই এই অপারেশনগুলো হৃদয়ের এক কোণে সযত্নে লুকিয়ে রাখতে হবে, সবসময়! বিটওয়াইজ অপারেশনের জন্যে বেসিক অপারেটর আছে ৬টি।

 

AND, OR, XOR : এই তিনটি অপারেটরই সমান দৈর্ঘ্যের বিট প্যাটার্ন নিয়ে কাজ করে।
AND ( & ) : দুইটি বিটের উভয়ই ১ হলে, এদের AND করলে ১ হবে, নয়ত ০
OR ( | ) : দুইটি বিটের যেকোন একটি বা উভয়ই ১ হলে, এদের OR করলে ১ হবে, নয়ত ০
XOR ( ^ ) : দুইটি বিটের উভয়ই ০ অথবা উভয়ই ১ হলে, এদের XOR করলে ০ হবে, নয়ত ১
NOT ( ~ ) : এই অপারেটরটি কোন বিটকে ফ্লিপ করে, অর্থাৎ ১ এর নট করলে হবে ০, ০ এর নট করলে হবে ১

 

 

আরও দুইটি বিট অপারেটর আছে – লেফট শিফট অপারেটর ( << ) , রাইট শিফট অপারেটর ( >> ). নাম শুনেই বুঝতে পারার কথা, এরা কোনকিছুকে শিফট করে। এরা কোন একটি বিট প্যাটার্নের বিটগুলোকে বামে অথবা ডানে শিফট করে। কোন একটি সংখ্যাকে k বিট লেফট শিফট করা মানে হচ্ছে, 2^k দিয়ে গুন করা।

 

1 << 1 = 2 = 2¹
1 << 2 = 4 = 2²
1 << 3 = 8 = 2³
1 << 4 = 16 = 2⁴
1 << n = 2ⁿ

 

আর কোন একটি সংখ্যাকে k বিট রাইট শিফট করা মানে হচ্ছে, 2^k দিয়ে ভাগ করা।

 

4 >> 1 = 2
6 >> 1 = 3
5 >> 2 = 1
16 >> 3 = 2

 

 

বিটওয়াইজ অপারেশনগুলো অনেক দ্রুত কাজ করে, তাই কোন প্রোগ্রামের টাইম অপ্টিমাইজ করতে বিট ম্যানিপুলেশন অনেক উপকারী। বিট ম্যানিপুলেশনের সাহায্যে করা যায় এরকম কিছু অ্যালগোরিদম দেখে ফেলা যাক এবারঃ

 

১) কোন সংখ্যা ২ এর পাওয়ার কিনা চেক করাঃ
 
আমরা যদি নরমালি চিন্তা করি, তাহলে আমরা সংখ্যাটিকে প্রথমে ২ দিয়ে ভাগ দিব(অবশ্যই যদি নিঃশেষে বিভাজ্য হয় তখন অর্থাৎ সংখ্যাটি যদি জোড় সংখ্যা হয়), তারপরে আবার ভাগ দিব, তারপর আবার…… এভাবে ভাগ দিতে দিতে যদি সংখ্যাটি ১ এ পৌছায়, তবে সংখ্যাটি ২ এর পাওয়ার। খেয়াল করে দেখো, এই অপারেশনটার টাইম কমপ্লেক্সিটি O(logn)

বিট ম্যানিপুলেশনের মাধ্যমে আমরা কন্সটেন্ট O(1) টাইমেই বলে দিতে পারি, কোন সংখ্যা ২ এর পাওয়ার কি না! সংখ্যাটি যদি x হয়, তবে x & (x-1) যদি ০ হয়, তাহলেই সংখ্যাটি ২ এর পাওয়ার হবে। এখন নিশ্চয়ই ভাবছো, এটা কি হল?! উদাহরণের সাহায্যে বোঝার চেষ্টা করি।

x = 4 = (100)₂, x – 1 = 3 = (011)₂
x = 10 = (1010)₂, x – 1 = 9 = (1001)₂

খেয়াল করে দেখো, x এর সবচেয়ে ডানে থাকা ১ ও ১ এর ডানের সবগুলো সংখ্যা ফ্লিপ করলেই x-1 পাওয়া যাচ্ছে। ২ এর পাওয়ার যে সংখ্যাগুলো তাদের বিট প্যাটার্নের মধ্যেও সামঞ্জস্য আছে।

8 = (1000)₂ , 16 = (10000)₂ , 32 = (100000)₂

প্যাটার্নটা লক্ষ করেছো?! এই প্যাটার্ন কিন্তু অন্য কোন সংখ্যায় পাবে না। আর প্যাটার্নটা বুঝতে পারলে নিশ্চয়ই ২ এর পাওয়ারের ক্ষেত্রে x & (x-1) এর ভ্যালু ০ আসার কথা, সেটা বুঝতেই পারছো। এবার তাহলে হাতেকলমে কতগুলো এলোমেলো (Random) সংখ্যা নিয়ে তারা ২ এর পাওয়ার কি না সেটা বের করে ফেলো, যাতে কনসেপ্টটা পুরোপুরি ক্লিয়ার হয়ে যায়! 😀

 

বুঝতেই পারছো, কোডটা এক লাইনেরই হবে! তবু লিখে দিলাম, তবে দেখার আগে নিজে একবার লেখার চেষ্টা করে দেখো, আশা করি পারবে! 🙂

bool isPowerOfTwo(int x)
{
    // x will check if x == 0 and !(x & (x - 1)) will check if x is a power of 2 or not
    return (x && !(x & (x - 1)));
}

 

২) কোন সেটের সবগুলো সাবসেট বের করাঃ
 
N সংখ্যক উপাদানের কোন সেটের সাবসেট সংখ্যা হল 2^N . সাবসেট বের করার জন্যে সেটের প্রতিটি উপাদানকে আমাদের একটি বিট হিসেবে ভাবতে হবে। বিটের ভ্যালু যদি ১ হয়, তাহলে উপাদানটি সাবসেটে আছে, ০ হলে নেই। অর্থাৎ প্রত্যেকটা বিট প্যাটার্নই হবে আমাদের একেকটি সাবসেট। একটি উদাহরণ দিলে বুঝতে সুবিধা হবেঃ

ধরি, A = {a,b,c}

এখন তিনটি উপাদানের জন্যে আমাদের করেস্পন্ডিং ৩টি বিট লাগবে। এই ৩টি বিটের সম্ভাব্য সবগুলো প্যাটার্নই হবে একেকটি সাবসেট।

 

0 = (000)₂ = {}
1 = (001)₂ = {c}
2 = (010)₂ = {b}
3 = (011)₂ = {b, c}
4 = (100)₂ = {a}
5 = (101)₂ = {a, c}
6 = (110)₂ = {a, b}
7 = (111)₂ = {a, b, c}

 

কোডটা হবে এরকমঃ

 

void possibleSubsets(char A[], int N)
{
    for(int i = 0;i < (1 << N); ++i)  // লুপটা 1 << N অর্থাৎ 2N পর্যন্ত ঘুরবে 
    {
        for(int j = 0;j < N;++j)
            if(i & (1 << j))
                cout << A[j] << ‘ ‘;
        cout << endl;
    }
}

 

৩) কোন বিট প্যাটার্নের নির্দিষ্ট ইন্ডেক্সের বিটকে সেট করাঃ
 
এখানে কোন নির্দিষ্ট ইনডেক্স j (0-based index) এর বিটকে সেট করা বলতে বোঝায়, ওই বিটে ১ বসানো। যদি বিট প্যাটার্নটি S হয়, তাহলে বিট সেট করার জন্যে অপারেশনঃ S |= (1<<j)

 

 

৪) কোন বিট প্যাটার্নের নির্দিষ্ট ইন্ডেক্সের বিট সেট আছে কিনা চেক করাঃ
 
এখানে কোন নির্দিষ্ট ইনডেক্স j (0-based index) এর বিট সেট আছে কিনা চেক করা বলতে বোঝায়, ওই বিটে ১ আছে কিনা। যদি বিট প্যাটার্নটি S হয়, তাহলে S & (1<<i) যদি ০ হয়, তাহলে ওই বিটে ১ নেই, নতুবা ১ আছে।

 

 

৫) কোন বিট প্যাটার্নের নির্দিষ্ট ইন্ডেক্সের বিটকে ক্লিয়ার করাঃ
 
এখানে কোন নির্দিষ্ট ইনডেক্স j (0-based index) এর বিটকে ক্লিয়ার করা বলতে বোঝায়, ওই বিটে ০ বসানো। যদি বিট প্যাটার্নটি S হয়, তাহলে বিট ক্লিয়ার করার জন্যে অপারেশনঃ S &= ~(1<<i)

 

 

৬) কোন বিট প্যাটার্নের নির্দিষ্ট ইন্ডেক্সের বিটকে ফ্লিপ করাঃ
 
এখানে কোন নির্দিষ্ট ইনডেক্স j (0-based index) এর বিটকে ফ্লিপ করা বলতে বোঝায়, ওই বিটে যদি ১ থাকে, তাহলে ফ্লিপ করে ০ করা, যদি ০ থাকে তাহলে ফ্লিপ করে ১ করা। যদি বিট প্যাটার্নটি S হয়, তাহলে বিট ফ্লিপ করার জন্যে অপারেশনঃ S ^= ~(1<<i)

 

 

৭) কোন বিট প্যাটার্নের যে Least Significant Bit অন তা নির্ণয় করাঃ
 
Least Significant Bit হচ্ছে কোন বিট প্যাটার্নের একদম ডানের বিট, যা সংখ্যাটি জোড় না বিজোড় তা নির্ধারণ করে। এখানে আমরা বের করব, সবচেয়ে ডানের যে ইনডেক্সে বিট অন করা, অর্থাৎ সবচেয়ে ডানের যে ইনডেক্সে ১ আছে। যদি বিট প্যাটার্নটি S হয়, তাহলে Result = (S & (-S)) এর একমাত্র অন বিটই সবচেয়ে ডানের সেট অন বিট।

 

 
শেষকথাঃ

মনে হতেই পারে, আহ, অনেক কিছু শিখে ফেলছি, কিন্তু এত সহজে তৃপ্তির ঢেঁকুর তুলে বসে থাকা চলবে না। প্রোগ্রামিং জগতের আনাচে কানাচে আরও এমন অনেক কিছুই খুঁজে পাবে যা বিট ম্যানিপুলেশনের সাথে জড়িত। তাই দেরি না করে বেরিয়ে পড়ো, বিটের রহস্যময় জগতের সন্ধানে।

 

C++ এ bitset টেমপ্লেটের বিভিন্ন ফাংশনের মাধ্যমে বিট ম্যানিপুলেশনের অনেক কাজ তুমি নিমেষেই করে ফেলতে পারবে। তবে এর আগে ফাংশনগুলো কিভাবে কাজ করে, সেটা জানা থাকলে ব্যবহার করতে সুবিধা হবে। বিটসেট সম্পর্কে জানতে এই লিঙ্কে যেতে পারোঃ

 

বিটসেট টেমপ্লেট

 

UVA, Hacker Rank এ একসাথে অনেকগুলো প্রব্লেম বিট ম্যানিপুলেশন সেকশনে দেয়া আছে, এগুলো প্র্যাক্টিস করলে কনসেপ্ট আরও ভালমত ক্লিয়ার হবে!

 

UVA
Hacker Rank