Thuật toán chia khôi phục (Restoring Division) cho số nguyên không dấu bằng C++

Thuật toán chia khôi phục (Restoring Division) dùng trong mạch số. Giả sử 0 < divisor < dividend. Sử dụng thanh ghi: Q (thương), A (dư), M (chỉ số chia), N (số bit).

Các bước

• Khởi tạo: Q = Dividend, A = 0, M = Divisor, N = số bit.
• Dịch trái AQ (xem như một đơn vị).
• A = A - M.
• Kiểm tra bit dấu (MSB) của A:
  • Nếu 0: set LSB của Q = 1.
  • Nếu 1: set LSB của Q = 0, khôi phục A = A + M.
• Giảm N, lặp lại cho đến N = 0.
• Thương nằm trong Q.

Ví dụ

#include <iostream>
using namespace std;

int main() {
    int Q = 8, q = 1, M = 3;
    short N = 4;
    int A = Q;
    M <<= N;
    for (int i = N - 1; i >= 0; i--) {
        A = (A << 1) - M;
        if (A < 0) {
            q &= ~(1 << i); // set bit i = 0
            A = A + M;      // restore
        } else {
            q |= 1 << i;    // set bit i = 1
        }
    }
    cout << "Quotient: " << q;
    return 0;
}

Kết quả

Quotient: 2

Kết luận

Đã trình bày thuật toán chia khôi phục cho số nguyên không dấu, minh họa bằng sơ đồ luồng và code C++ thao tác bit.