تكرار السؤال: …
الإجابة المختصرة
العمليات الثنائية تنفذ على مستوى دوائر المعالج في دورة ساعة واحدة (Single CPU Cycle)؛ فحص قوى 2 يتم عبر (n & (n - 1)) == 0، وإيجاد العنصر الفريد الوحيد يتم بتطبيق XOR على جميع الأرقام.
الشرح
خواص XOR المفيدة: A ^ A = 0 و A ^ 0 = A، والعملية تبادلية وتجميعية. فإذا كانت مصفوفة تحتوي على كل الأرقام مكررة مرتين عدا رقم واحد، فإن تطبيق XOR التراكمي يلغي كل العناصر المكررة ويتبقى الرقم الفردي تلقائياً بزمن O(N) ومساحة O(1)! حيلة n & (n - 1) تقوم بحذف البت الأحادي الأيمن الأخير (Least Significant Bit)، وتُستخدم في خوارزمية Brian Kernighan لعد البتات المضاءة بزمن يتناسب مع عدد الآحاد فقط.
مثال بالكود
// فحص هل الرقم قوة لـ 2 (Power of Two):
const isPowerOfTwo = (n > 0) && ((n & (n - 1)) === 0);
// إيجاد العنصر الفريد الفردي:
const singleNumber = (nums: number[]) => nums.reduce((acc, num) => acc ^ num, 0);أخطاء شائعة
- نسيان وضع الأقواس حول العمليات الثنائية؛ حيث تمتلك معاملات المقارنة مثل == أولوية أعلى من & في معظم اللغات البرمجية.
أسئلة متابعة
- كيف تعمل خوارزمية البحث الثنائي (Binary Search) وما هي الحيل الرياضية لتفادي مشكلة Integer Overflow؟