বিট ম্যানিপুলেশনের সাধারণ কৌশলগুলি কী?

Question

Accepted Answer

**বিট ম্যানিপুলেশন** AND, OR, XOR, NOT এবং শিফট ব্যবহার করে পূর্ণসংখ্যার বাইনারি প্রতিনিধিত্বে সরাসরি কাজ করে। এটি কম্প্যাক্ট, শাখা-মুক্ত এবং অত্যন্ত দ্রুত অপারেশন সক্ষম করে। ## মূল অপারেশন ```python x & 1 # is x odd? (lowest bit) x << 1 # multiply by 2 x >> 1 # integer divide by 2 x & (1 << k) # is bit k set? x | (1 << k) # set bit k x & ~(1 << k) # clear bit k x ^ (1 << k) # toggle bit k ``` ## দরকারী কৌশল ```python x & (x - 1) # clears the lowest set bit x & (x - 1) == 0 # is x a power of two? (x>0) x & (-x) # isolates the lowest set bit bin(x).count('1') # popcount (number of set bits) ``` ## উদাহরণ: একক সংখ্যা খুঁজুন (XOR কৌশল) ```python def single_number(nums): result = 0 for n in nums: result ^= n # pairs cancel: a ^ a == 0 return result # the lone unpaired value remains single_number([4, 1, 2, 1, 2]) # -> 4 ``` ## জটিলতা বিট অপারেশন O(1); উপরের XOR স্ক্যান **O(n) সময়, O(1) স্থান**। ## কখন ব্যবহার করতে হবে / সতর্কতা **bitmasks** (সাবসেট গণনা, স্থিতিশীলতার উপর DP), ফ্ল্যাগ, দ্রুত গণিত এবং নিম্ন-স্তরের/এমবেডেড কোডের জন্য ব্যবহার করুন। স্বাক্ষর বিট, ভাষা-নির্দিষ্ট শিফট আচরণ এবং পাঠযোগ্যতার বিষয়ে সতর্ক থাকুন — অস্পষ্ট কৌশলগুলিতে মন্তব্য করুন। ## এটি কেন গুরুত্বপূর্ণ বিট ম্যানিপুলেশন মার্জিত O(1)-স্থান সমাধান তৈরি করে (XOR একক-সংখ্যা কৌশলের মতো) যা সাক্ষাতে বিস্মিত করে। Bitmask DP অনেক সমন্বিত অবস্থা-স্থান সমস্যাগুলি সমাধানযোগ্য করে তোলে। এটি সিস্টেম, গ্রাফিক্স, সংকোচন এবং কর্মক্ষমতা-সমালোচনামূলক কোডে অপরিহার্য যেখানে প্রতিটি চক্র গুরুত্বপূর্ণ।