الـ Integer Overflow: ليه (low + high) / 2 باج في كل بحث ثنائي تقريبًا

الـ Integer Overflow: ليه (low + high) / 2 باج في كل بحث ثنائي تقريبًا

هذا المقال يتطلب مستوى: محترف. لو انت مبتدئ أو متوسط، هيفيدك، لكنه بيفترض إنك تعرف البحث الثنائي (binary search) وتقرأ كود Java.

سطر واحد بتكتبه في أي بحث ثنائي بيحسب نقطة المنتصف: mid = (low + high) / 2. السطر ده صحيح رياضيًا وغلط برمجيًا، وظل باجًا نائمًا في مكتبة Java القياسية تسع سنوات. بعد ما تخلص، هتعرف تكتشف نفس الخطأ في أي كود عندك وتصلّحه في ثانية.

المشكلة باختصار

البحث الثنائي بيقسم المصفوفة نص كل خطوة. عشان يعمل كده لازم يحسب المؤشر في النص: mid. الطريقة البديهية بتجمع low + high الأول. المشكلة إن الناتج ممكن يتعدّى أقصى قيمة يشيلها العدد الصحيح، فيلتف (wraps) لرقم سالب. المؤشر السالب بيكسر الوصول للمصفوفة أو بيرجّع نتيجة غلط. الخطأ مبيظهرش على المصفوفات الصغيرة، فبيعدّي كل الاختبارات ويوصل للـ production.

ليه العدد بيلتف؟ ابدأ بالعدّاد

تخيّل عدّاد مسافة عربية بستة أرقام. أقصى رقم يوصّله 999999. لو مشيت كيلومتر واحد زيادة، مش هيبقى 1000000، هيرجع لـ 000000 لأنه مفيش خانة سابعة. ده بالظبط اللي بيحصل للعدد الصحيح في الذاكرة: عدد الخانات ثابت، ولما تتخطّى السقف بترجع من الأول.

علميًا: الـ int في Java وC وGo بيتخزّن في 32 بت بنظام المتممة الثنائية (two's complement). أقصى قيمة موجبة هي 2,147,483,647 (أي 2^31 − 1). البت الأعلى محجوز للإشارة. أول ما المجموع يعدّي القيمة دي، البت الأعلى بيتقلب، فالعدد بيتفسّر كرقم سالب. مفيش استثناء بيترمى، مفيش تحذير: العملية بتكمّل بصمت بقيمة غلط. ده الفرق الخطير: الـ overflow في الأعداد الصحيحة مش error، ده سلوك معرّف بيديك رقم خاطئ.

الخطأ في البحث الثنائي بالتفصيل

خُد مصفوفة كبيرة، وافترض إن البحث وصل لحالة low = 1,500,000,000 و high = 2,000,000,000. دي أرقام واقعية لو عندك مصفوفة فيها أكثر من مليار عنصر.

المجموع low + high = 3,500,000,000. الرقم ده أكبر من سقف الـ int (2,147,483,647)، فبيلتف إلى -794,967,296. وبقسمته على 2 بيطلع mid = -397,483,648، وهو مؤشر سالب. النتيجة: ArrayIndexOutOfBoundsException في Java، أو قراءة ذاكرة خارج الحدود في C.

كود يفجّر الخطأ ويصلّحه

جرّب الكود ده بنفسك. لاحظ إني استخدمت Java قصدًا: في Python الأعداد الصحيحة عندها دقة لا نهائية فالـ overflow ده مبيحصلش أصلًا، وده بالظبط سبب أهمية معرفة لغتك.

public class BinarySearchBug {
    public static void main(String[] args) {
        int low  = 1_500_000_000;
        int high = 2_000_000_000;

        // الطريقة الشائعة — بها الخطأ
        int buggyMid = (low + high) / 2;
        System.out.println("buggyMid = " + buggyMid);   // -397483648  (مؤشر سالب!)

        // الإصلاح — لا يتجاوز السقف أبدًا
        int safeMid = low + (high - low) / 2;
        System.out.println("safeMid  = " + safeMid);     // 1750000000  (صحيح)
    }
}

الإصلاح شغّال لأن high - low دايمًا أصغر من high، فمجموعه مع low ميعدّيش السقف. بديل تاني في Java هو الإزاحة غير المُوقَّعة: (low + high) >>> 1، وده اللي استخدمه فريق JDK فعلًا في الإصلاح الرسمي. الاتنين صفر تكلفة أداء.

السيناريو الواقعي: مش مجرد نظرية

الخطأ ده مش افتراضي. في 2006 نشر Joshua Bloch (مؤلف Effective Java وكاتب java.util.Arrays.binarySearch) مقالًا عنوانه "تقريبًا كل عمليات البحث الثنائي وترتيب الدمج مكسورة"، وكشف إن نفس الباج عاش في مكتبة JDK من 1997 لحد 2006. الشرط لظهوره: مصفوفة أكبر من 1,073,741,823 عنصر (حوالي 2^30). ده كان مستحيل عمليًا في 1997، لكن بقى ممكن مع كِبَر الذاكرة.

وعلى مستوى أخطر: صاروخ Ariane 5 في رحلته الأولى 1996 انفجر بعد 37 ثانية من الإقلاع. السبب المباشر كان تجاوز عددي عند تحويل رقم عائم 64-bit إلى صحيح 16-bit. الخسارة قُدّرت بمئات ملايين الدولارات. تجاوز السعة العددية سطر واحد، والتكلفة ممكن تبقى صاروخ.

الـ trade-offs وما يجب الانتباه له

الإصلاح low + (high - low) / 2 بيكسب لك الأمان بصفر تكلفة في الأداء، بس بتخسر شوية من وضوح القراءة: الصيغة أقل بداهة للمبتدئ. الـ trade-off هنا في صالح الأمان دايمًا. الافتراض إنك بتشتغل بأعداد صحيحة ذات حجم ثابت (32 أو 64 بت). لو low نفسه ممكن يبقى سالب (مش الحالة في مؤشرات المصفوفات)، الإصلاح ده محتاج مراجعة إضافية لأن high - low بردو ممكن يتجاوز.

متى لا تشغل بالك بهذا

مش كل كود معرّض للمشكلة. تجاهلها بأمان لو: بتكتب بـ Python أو Ruby أو JavaScript BigInt (دقة لا نهائية)، أو مصفوفاتك أصغر من مليار عنصر بمراحل وlow + high مستحيل يتعدّى السقف، أو بتستخدم long (64-bit) والقيم أصغر بكتير من 9.2 كوينتيليون. القاعدة: المشكلة بتظهر بس لما مجموع مؤشرين يقترب من سقف نوع العدد اللي بتستخدمه.

الخطوة التالية

افتح أي بحث ثنائي أو حساب منتصف في الكود بتاعك دلوقتي، ودوّر على النمط (a + b) / 2. لو لقيته على نوع صحيح ثابت الحجم، بدّله بـ a + (b - a) / 2. الاستبدال ده صفر مخاطرة وبيقفل ثغرة عاشت عشرين سنة في مكتبات أنضف مننا.

المصادر

• Joshua Bloch، "Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken"، Google Research Blog، 2 يونيو 2006.
• توثيق Java الرسمي: Integer.MAX_VALUE = 2,147,483,647 (2^31 − 1)، تمثيل الأعداد بنظام المتممة الثنائية (two's complement).
• تقرير لجنة التحقيق في حادث Ariane 5 Flight 501 (ESA/CNES Inquiry Board Report)، 1996 — تجاوز عددي عند تحويل عائم 64-bit إلى صحيح 16-bit.
• سِجل تعديلات OpenJDK لدالة java.util.Arrays.binarySearch والإصلاح باستخدام الإزاحة غير المُوقَّعة >>> 1.