অ্যাডভান্সড টপিক৭ মিনিট পড়া

বিট ম্যানিপুলেশন (Bit Manipulation)

বিদ্যুতের গতিতে সুইচ উল্টান বা ফ্লিপ (flip) করুন — এবং তা করুন \(O(1)\) সময়ে
all bitwise ops:\(O(1)\) — একক সিপিইউ নির্দেশনা বা সিঙ্গেল সিপিইউ ইন্সট্রাকশন (single CPU instruction)word size:আধুনিক হার্ডওয়্যারের ক্ষেত্রে ৬৪ বিট (64 bits)hardware popcount:\(O(1)\) POPCNT ইন্সট্রাকশনের মাধ্যমে

আপনার কম্পিউটারের প্রতিটি ইনটিজার বা পূর্ণসংখ্যা লাইটের সুইচের (light switches) একটি সারি হিসেবে সংরক্ষিত থাকে — যেখানে প্রতিটি সুইচ হলো একটি বিট (bit), যা হয় চালু (1) থাকে অথবা বন্ধ (0) থাকে। অঙ্কের ধীরগতির জটিল প্রক্রিয়ার মধ্য দিয়ে না গিয়ে, সরাসরি নির্দিষ্ট কোনো সুইচে গিয়ে তাকে উল্টে বা ফ্লিপ (flip) করে দেওয়াকেই বিট ম্যানিপুলেশন (Bit manipulation) বলা হয়।

অযথা এত কষ্ট কেন করবেন? কারণ এই অপারেশন বা কাজগুলো একটি মাত্র সিপিইউ ক্লক সাইকেলে (CPU clock cycle) সম্পন্ন হয় — অর্থাৎ আক্ষরিক অর্থেই এটি হলো একটি কম্পিউটার করতে পারে এমন সবচেয়ে দ্রুততম কাজ। অনেক ট্রিক বা কৌশল আছে যেগুলোকে দেখে মনে হতে পারে যে এতে \(O(n)\) পরিমাণ কাজ করতে হবে, কিন্তু সঠিক সুইচের সংমিশ্রণ ব্যবহার করলে তা এক নিমিষেই কমে এসে \(O(1)\) হয়ে যায়।

ছয়টি সাধারণ অপারেশন (The six basic operations)

অ্যান্ড (AND &): বিট বা ফলাফল 1 হবে কেবল তখনই যদি উভয় ইনপুটে 1 থাকে। নির্দিষ্ট কোনো বিটকে মাস্ক (mask) বা আইসোলেট করতে এটি ব্যবহার করা হয়।
অর (OR |): বিট বা ফলাফল 1 হবে যদি যেকোনো একটি ইনপুটেও 1 থাকে। নির্দিষ্ট কোনো বিটকে সেট (set) করতে এটি ব্যবহার করা হয়।
এক্সঅর (XOR ^): বিট বা ফলাফল 1 হবে যদি দুটি ইনপুট ভিন্ন (differ) হয়। বিট টগল (toggle) করতে বা পার্থক্য খুঁজে বের করতে এটি ব্যবহার করা হয়।
নট (NOT ~): নট সমস্ত বিটকে উল্টে বা ফ্লিপ (flip) করে দেয়। টুজ কমপ্লিমেন্টের (two's complement) ক্ষেত্রে: ~x = −x − 1।
লেফট শিফট (Left shift << k): 2^k দিয়ে গুণ করা হয় (বিটগুলোকে বাম দিকে সরানো হয় এবং ডান পাশের ফাঁকা জায়গাটি জিরো (0) বা শূন্য দিয়ে পূরণ করা হয়)।
রাইট শিফট (Right shift >> k): 2^k দিয়ে ভাগ করা হয় (ডান দিকে সরানো হয়; এর অ্যারিথমেটিক শিফট (arithmetic shift) সাইন বা চিহ্নকে অপরিবর্তিত বা সংরক্ষণ করে)।

কিছু অত্যন্ত প্রয়োজনীয় ট্রিক বা কৌশল (Essential tricks)

n কোনো 2 এর পাওয়ার (power of 2) কিনা তা যাচাই করুন: n & (n−1) == 0 (এবং n > 0)। যেকোনো 2 এর পাওয়ারের সংখ্যায় ঠিক একটি বিটই 1 বা সেট করা থাকে। এর থেকে 1 বিয়োগ করলে তার নিচের সমস্ত শূন্যগুলো (0) উল্টে 1 হয়ে যায় এবং সবার ওপরের 1 বিটটি 0 হয়ে যায়। তখন এদের AND করলে 0 পাওয়া যায়।

সবচেয়ে নিচের সেট করা বিটটিকে বা 1-কে আইসোলেট করুন (Isolate the lowest set bit): n & (−n)। টুজ কমপ্লিমেন্টের (Two's complement) ক্ষেত্রে, −n = ~n + 1। যখন 1 যোগ করা হয় তখন এটি পেছনের সমস্ত শূন্যগুলোর মধ্য দিয়ে ট্রাভেল বা ক্যারি (carry) করে, যতক্ষণ না এটি একটি 1-বিটে গিয়ে পৌঁছায় — আর আন্দ (AND) করার পর শুধুমাত্র এই 1-বিটটিই অবশিষ্ট থাকে।

সবচেয়ে নিচের সেট করা বিটটিকে বা 1-কে ক্লিয়ার করুন (Clear the lowest set bit): n & (n−1)। এটি প্রতি কলে ঠিক একটি করে বিট ক্লিয়ার করে বা মুছে ফেলে — যা ব্রায়ান কেরিঙ্গানের (Brian Kernighan) পপকাউন্ট (popcount) অ্যালগরিদমের মূল ভিত্তি।

এক্সঅর (XOR)-এর সুপারপাওয়ার বা বিশেষ ক্ষমতাগুলো

টেম্প (temp) ভেরিয়েবল ছাড়াই সোয়াপ করুন: a ^= b; b ^= a; a ^= b। এটি কাজ করে কারণ XOR হলো তার নিজেরই ইনভার্স (inverse): (a^b)^b = a।

একমাত্র একাকী বা নন-ডুপ্লিকেট (non-duplicate) উপাদানটি খুঁজুন: সব উপাদানের ওপর XOR করুন। জোড়াগুলো বা পেয়ারগুলো একে অপরকে বাতিল করে দেয় (x^x = 0), আর শূন্য (0) হলো আইডেন্টিটি বা পরিচয় (0^x = x), তাই শেষপর্যন্ত আপনার কাছে শুধু ইউনিক বা অদ্বিতীয় উপাদানটিই অবশিষ্ট থাকে। XOR হলো কমিউটেটিভ (commutative) এবং অ্যাসোসিয়েটিভ (associative) — অর্থাৎ এখানে উপাদানের ক্রম বা অর্ডার কোনো ব্যাপার নয়।

0 থেকে n পর্যন্ত থাকা সংখ্যাগুলোর মধ্যে কোনটি মিসিং বা নেই তা বের করুন (Missing number in 0..n): 0^1^2^…^n এর সাথে অ্যারেতে থাকা সমস্ত উপাদানের XOR করুন। জোড়ভুক্ত মানগুলো একে অপরকে বাতিল করে দেবে, আর তখন শুধু মিসিং বা হারিয়ে যাওয়া সংখ্যাটিই অবশিষ্ট থাকবে।

সাবসেটের জন্য বিটমাস্ক (Bitmasks for subsets)

{0, 1, …, n−1} এর যেকোনো একটি সাবসেটকে একটি পূর্ণসংখ্যা বা ইনটিজার হিসেবে প্রকাশ করুন, যেখানে i তম বিট 1 হবে যদি এবং কেবল যদি i উপাদানটি উক্ত সাবসেটে থাকে। আপনি কোনো অতিরিক্ত খরচ বা হিসেব ছাড়াই 2^n টি সম্ভাব্য সাবসেট পাবেন, যার প্রতিটিই একেকটি একক পূর্ণসংখ্যা।

i উপাদানটি মাস্কে (mask) আছে কি না তা চেক করুন: (mask >> i) & 1।
i উপাদানটি যোগ করুন: mask | (1 << i)।
i উপাদানটি বাদ বা রিমুভ (Remove) করুন: mask & ~(1 << i)।
মাস্কের সমস্ত সাবসেটের ওপর ইটারেট (Iterate) বা লুপ করুন: for (s = mask; s > 0; s = (s−1) & mask)।

সেট করা বিট বা 1 গণনা করা (Counting set bits - popcount)

হার্ডওয়্যার পপকাউন্ট (Hardware POPCNT): যেকোনো আধুনিক সিপিইউ-তে, __builtin_popcount(n) (সি/সি++), Integer.bitCount(n) (জাভা), অথবা bin(n).count('1') (পাইথন) কম্পাইল হয়ে একটি একক POPCNT ইন্সট্রাকশনে রূপান্তরিত হয়। সবসময় এটি ব্যবহার করার চেষ্টা করবেন।

ব্রায়ান কার্নিগানের পদ্ধতি (Brian Kernighan's method): while n: n &= n−1; count++। প্রতি ইটারেশনে বা লুপে একটি করে বিট ক্লিয়ার করে বা মুছে ফেলে, তাই এটি \(O(popcount(n))\) সময়ে সম্পন্ন হয় — যখন খুব কম সংখ্যক বিট 1 থাকে বা সেট করা থাকে তখন এটি খুব ভালো কাজ করে।

দ্রষ্টব্য: XOR হলো বিট ম্যানিপুলেশনের সুইস আর্মি নাইফের (Swiss Army knife) মতো: কোনো কিছু টগল (toggle) করা, অদলবদল (swap) করা, পার্থক্য খুঁজে বের করা, অথবা ডুপ্লিকেট বাতিল করার জন্য এর তুলনা নেই। কোনো সমস্যায় যদি কখনো 'জোড়া (pair)', 'পার্থক্য (difference)' বা 'টগল (toggle)' শব্দগুলো দেখেন, তবে নিজেকে প্রশ্ন করুন: 'XOR কি এটি \(O(1)\)-এ সমাধান করতে পারে?'

বিট ট্রিক্স (Bit tricks) — 2 এর পাওয়ার, পপকাউন্ট (popcount), XOR নন-ডুপ্লিকেট বা ইউনিক মান খোঁজা

# Power of 2 check
def is_power_of_2(n):
    return n > 0 and (n & (n - 1)) == 0


print(is_power_of_2(16))   # True
print(is_power_of_2(18))   # False


# Isolate lowest set bit
def lowest_bit(n):
    return n & (-n)


print(bin(lowest_bit(0b10110)))  # 0b10 (bit 1)


# Count set bits (popcount)
def popcount(n):
    count = 0
    while n:
        n &= n - 1  # clear lowest set bit
        count += 1
    return count


print(popcount(0b101101))  # 4
print(bin(255).count('1')) # 8  (faster way)


# XOR: find the single non-duplicate
def find_unique(arr):
    result = 0
    for x in arr:
        result ^= x
    return result


print(find_unique([4, 1, 2, 1, 2]))  # 4
print(find_unique([3, 3, 7, 5, 5]))  # 7


# Subset enumeration
mask = 0b1011  # subset {0, 1, 3}
subsets = []
s = mask
while s > 0:
    subsets.append(bin(s))
    s = (s - 1) & mask
print(subsets)
Output
True
False
0b10
4
8
4
7
['0b1011', '0b1010', '0b1001', '0b1000', '0b11', '0b10', '0b1']

Complexity

⚡ AND, OR, XOR, NOT, শিফটস (shifts)
আক্ষরিক অর্থেই একটি সিপিইউ-এর জন্য এগুলো হলো সবচেয়ে দ্রুততম কাজ বা অপারেশন — প্রতিটির জন্য মাত্র একটি ক্লক সাইকেলের প্রয়োজন হয়
একটি মাত্র সিপিইউ ইন্সট্রাকশন বা নির্দেশ (Single CPU instruction) \(O(1)\)
🔢 হার্ডওয়্যার পপকাউন্ট বা Hardware popcount (POPCNT)
সব আধুনিক x86/ARM সিপিইউ-তে পাওয়া যায় — __builtin_popcount, Integer.bitCount, অথবা BitOperations.PopCount ব্যবহার করুন
একটি মাত্র সিপিইউ ইন্সট্রাকশন বা নির্দেশ (Single CPU instruction) \(O(1)\)
🔁 ব্রায়ান কার্নিগানের পপকাউন্ট (Brian Kernighan's popcount)
খুব কম বিট সেট করা থাকলে অসামান্য কাজ করে; অন্যথায় সর্বদা হার্ডওয়্যার POPCNT কে অগ্রাধিকার দিন
প্রতিটি সেট করা বিটের বা 1 এর জন্য একটি করে ইটারেশন বা লুপ \(O(\text{popcount}(n))\)
📦 বিটমাস্কের মাধ্যমে সাবসেট অ্যানুমেরেশন বা বের করা (Subset enumeration via bitmask)
প্রতিটি সাবসেট একেকটি পূর্ণসংখ্যা বা ইনটিজার — সাবসেটের সমস্ত কার্যবিধি (যোগ, বাদ দেওয়া, চেক করা) হলো \(O(1)\)
সমস্ত 2^n সাবসেটগুলো ভিজিট করুন \(O(2^n)\)

ছোট কুইজ

n & (n-1) এক্সপ্রেশনটি বা গাণিতিক পদটি কী গণনা করে বা হিসেব করে?

পড়া চালিয়ে যান