ما هي الحيل الشائعة في التعامل مع البتات (Bit Manipulation)؟

Question

Accepted Answer

**التعامل مع البتات (Bit manipulation)** يعمل مباشرة على التمثيل الثنائي للأعداد الصحيحة باستخدام AND و OR و XOR و NOT والتحويلات (shifts). يتيح عمليات مضغوطة وخالية من التفريع وسريعة جداً. ## العمليات الأساسية ```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 على الحالات)، الأعلام (flags)، الرياضيات السريعة، والكود منخفض المستوى / المدمج. احذر من بتات الإشارة، السلوك الخاص باللغة في التحويلات، والوضوح — علق على الحيل غير الواضحة. ## لماذا يهم التعامل مع البتات ينتج عنه حلول أنيقة بمساحة O(1) (مثل حيلة XOR للرقم الفريد) تثير الإعجاب في المقابلات. DP مع Bitmask يجعل العديد من مسائل الفضاء الحالاتي التوليفي قابلة للتطبيق. هو أساسي في الأنظمة والرسوميات والضغط والكود الحرج للأداء حيث تعتبر كل دورة مهمة.