6. Bit Manipulation Basics
কম্পিউটার মূলত ১ এবং ০ (Binary) ছাড়া কিছুই বোঝে না। বিট ম্যানিপুলেশন হলো সংখ্যার এই বাইনারি লেভেলে সরাসরি কাজ করার একটি অত্যন্ত দ্রুত এবং কার্যকর পদ্ধতি।
1. বাইনারি রিপ্রেজেন্টেশন (Binary Representation)
প্রতিটি পূর্ণসংখ্যাকে বাইনারি বা ২-ভিত্তি বিশিষ্ট সংখ্যায় প্রকাশ করা যায়।
- উদাহরণ: ৫ এর বাইনারি হলো
101(2^2 _ 1 + 2^1 _ 0 + 2^0 * 1)।
2. দশমিক থেকে বাইনারি রূপান্তর (Decimal to Binary Conversion)
একটি দশমিক সংখ্যাকে বার বার ২ দিয়ে ভাগ করে এবং ভাগশেষগুলো (Remainder) উল্টো করে সাজিয়ে বাইনারি পাওয়া যায়।
🛠 কর্মপদ্ধতি (Step-by-Step Logic)
- সংখ্যাটিকে ২ দিয়ে ভাগ করুন।
- ভাগশেষটি (০ বা ১) লিখে রাখুন।
- ভাগফলটিকে পুনরায় ২ দিয়ে ভাগ করুন।
- যতক্ষণ ভাগফল ০ না হয়, ততক্ষণ এটি চালিয়ে যান।
- সবশেষে ভাগশেষগুলোকে নিচ থেকে লিখে সাজালে বাইনারি পাওয়া যাবে।
3. বিটওয়াইজ অপারেশন (Bitwise Operations)
| Operator | Name | Logic |
|---|---|---|
& | AND | দুটির মধ্যে দুটি বিট ১ হলে রেজাল্ট ১, অন্যথায় ০। |
| | OR | যেকোনো একটি বিট ১ হলে রেজাল্ট ১। |
^ | XOR | দুটি ভিন্ন বিট হলে ১, একই হলে ০। |
~ | NOT | বিটকে উল্টে দেয় (১ থাকলে ০, ০ থাকলে ১)। |
📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)
- Time Complexity: O(1)
- Space Complexity: O(1)
4. বিট শিফটিং (Bit Shifting)
Left Shift (<<)
বিটগুলোকে বাম দিকে সরিয়ে দেয় এবং ডানে শূন্য যোগ করে। এটি সংখ্যাকে ২ দিয়ে গুণ করার সমান।
x << nমানে $x * 2^n$
Right Shift (>>)
বিটগুলোকে ডান দিকে সরিয়ে দেয়। এটি সংখ্যাকে ২ দিয়ে ভাগ করার সমান।
x >> nমানে $x / 2^n$
5. গুরুত্বপূর্ণ ট্রিকস (Common Tricks)
1. জোড়-বিজোড় বের করা (Check Even/Odd)
🛠 কর্মপদ্ধতি (Logic)
(n & 1)যদি ১ হয় তবে বিজোড়, ০ হলে জোড়।
2. ২ এর পাওয়ার কিনা চেক করা (Power of 2)
🛠 কর্মপদ্ধতি (Logic)
- যদি
(n & (n-1)) == 0এবংn > 0হয়, তবে সংখ্যাটি ২ এর পাওয়ার।
3. সেট বিট কাউন্ট করা (Count Set Bits)
🛠 কর্মপদ্ধতি (Logic)
- Brian Kernighan's Algorithm ব্যবহার করে লুপ চালিয়ে
n = n & (n-1)করলে প্রতি স্টেপে একটি করে সেট বিট (১) কমে যায়।
IMPORTANT
বিট ম্যানিপুলেশন কোডকে অনেক বেশি ফাস্ট এবং রিসোর্স এফিসিয়েন্ট করে তোলে।
TIP
XOR অপারেশনের একটি বিশেষ গুণ হলো x ^ x = 0 এবং x ^ 0 = x। এটি ব্যবহার করে অ্যারেতে সিঙ্গেল এলিমেন্ট খুঁজে বের করা যায়।