Phép chia không sử dụng toán tử '/' trong C++

Giới thiệu

Thực hiện phép chia hai số nguyên chỉ sử dụng phép trừ, không dùng toán tử chia '/' hay nhân '*'. Đây là bài tập kinh điển về mô phỏng phép chia bằng phép trừ lặp lại.

Ý tưởng thuật toán

Phép chia a ÷ b tương đương với việc trừ b từ a liên tục cho đến khi a < b. Số lần trừ được chính là thương.

Ví dụ: 24 ÷ 5

24 - 5 = 19 (lần 1)
19 - 5 = 14 (lần 2)
14 - 5 = 9  (lần 3)
9  - 5 = 4  (lần 4) → dừng vì 4 < 5
Thương = 4, Dư = 4

Mã nguồn hoàn chỉnh

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

int division(int dividend, int divisor) {
    // Xử lý trường hợp đặc biệt
    if (dividend == 0) return 0;
    if (divisor == 0) return INT_MAX; // Chia cho 0
    
    // Xác định dấu kết quả
    bool negative_result = false;
    if (dividend < 0) {
        dividend = -dividend;
        if (divisor < 0) {
            divisor = -divisor;
        } else {
            negative_result = true;
        }
    } else if (divisor < 0) {
        divisor = -divisor;
        negative_result = true;
    }
    
    // Thực hiện chia bằng phép trừ
    int quotient = 0;
    while (dividend >= divisor) {
        dividend = dividend - divisor;
        quotient++;
    }
    
    // Áp dụng dấu
    if (negative_result) {
        quotient = -quotient;
    }
    
    return quotient;
}

int main() {
    int num_one = 24, num_two = 5;
    cout << "Thương: " << division(num_one, num_two) << endl;
    
    // Test thêm các trường hợp
    cout << "-24 / 5 = " << division(-24, 5) << endl;
    cout << "24 / -5 = " << division(24, -5) << endl;
    cout << "-24 / -5 = " << division(-24, -5) << endl;
    
    return 0;
}

Kết quả chạy chương trình

Thương: 4
-24 / 5 = -4
24 / -5 = -4
-24 / -5 = 4

Phân tích độ phức tạp

• Thời gian: O(thương) = O(a/b) - tuyến tính với kết quả
• Không gian: O(1)

Tối ưu hóa: Chia nhanh (Binary Division)

Thay vì trừ lần lượt, có thể trừ b, 2b, 4b, 8b... (nhân đôi mỗi lần) để đạt O(log(a/b)):

int fastDivision(int dividend, int divisor) {
    if (divisor == 0) return INT_MAX;
    if (dividend == 0) return 0;
    
    bool negative = (dividend < 0) ^ (divisor < 0);
    long long a = abs((long long)dividend);
    long long b = abs((long long)divisor);
    
    int quotient = 0;
    while (a >= b) {
        long long temp = b, multiple = 1;
        while (a >= (temp << 1)) {
            temp <<= 1;
            multiple <<= 1;
        }
        a -= temp;
        quotient += multiple;
    }
    return negative ? -quotient : quotient;
}

Kết luận

Phép chia bằng phép trừ là cơ sở của thuật toán chia trong vi xử lý. Phiên bản tối ưu dùng dịch bit (bit shifting) nhanh hơn gấp nhiều lần.