การหารจำนวนเต็มสองจำนวนใน C++ (ไม่ใช้ *, /, %)

โจทย์ปัญหา

ได้รับจำนวนเต็มสองจำนวน dividend และ divisor ให้หาร dividend ด้วย divisor โดยไม่ใช้การคูณ การหาร และ modulo คืนค่าผลหาร (Quotient) โดยปัดทศนิยมเข้าสู่ศูนย์

ตัวอย่าง

นำเข้า: dividend = 7, divisor = -3
ผลลัพธ์: -2

แนวคิดการแก้ปัญหา (Bit Manipulation)

ใช้หลักการ Binary Long Division โดยการเลื่อนบิต (Bit Shifting) เพื่อหาตัวคูณที่ใหญ่ที่สุดของ divisor ที่ยังน้อยกว่าหรือเท่ากับ dividend

1. จัดการกรณีพิเศษ: overflow (INT_MIN / -1)
2. แปลงเป็นค่าสัมบูรณ์ (ใช้ long long ป้องกัน overflow)
3. วนลูปจนกว่า dividend < divisor:
   • หา p ใหญ่สุดที่ทำให้ divisor << p <= dividend
   • ลบ divisor << p ออกจาก dividend
   • บวก 1 << p เข้าไปในคำตอบ
4. ปรับเครื่องหมายตาม dividend และ divisor เดิม

โค้ดตัวอย่าง (C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long int lli;

class Solution {
public:
    int divide(int l, int y) {
        if (l == INT_MIN && y == -1) return INT_MAX; // Overflow case
        lli a = labs(l);
        lli b = labs(y);
        lli ans = 0;
        while (a - b >= 0) {
            int x = 0;
            while (a - (b << 1 << x) >= 0) {
                x++;
            }
            a -= b << x;
            ans += 1 << x;
        }
        return ((l > 0) == (y > 0)) ? ans : -ans;
    }
};

int main() {
    Solution ob;
    cout << ob.divide(40, 3);
    return 0;
}

ผลลัพธ์

13

คำอธิบายเพิ่มเติม

• ความซับซ้อนด้านเวลา: O(log n) (n = dividend)
• ใช้ long long เพื่อป้องกัน overflow เมื่อทำ labs(INT_MIN)
• กรณี INT_MIN / -1 ต้องจัดการแยกเพราะผลลัพธ์เกิน INT_MAX