อัลกอริทึมการหารแบบ Restoring สำหรับ Unsigned Integer ใน C++

อภิปรายการหารจำนวนเต็มไม่มีเครื่องหมาย (unsigned integer) โดยใช้อัลกอริทึมการหาร บางอัลกอริทึมการหารถูกนำไปใช้บนกระดาษ และบางอันถูกนำไปใช้บนวงจรดิจิทัล อัลกอริทึมการหารมี 2 ประเภท: อัลกอริทึมการหารช้า (slow division algorithm) และอัลกอริทึมการหารเร็ว (fast division algorithm) อัลกอริทึมการหารช้าประกอบด้วย restoring, non-performing restoring, SRT, และ non-restoring algorithm

ในบทช่วยสอนนี้ เราจะอภิปรายอัลกอริทึม Restoring โดยสมมติว่า 0 < divisor < dividend

วิธีการหาคำตอบ

ในวิธีนี้ เราจะใช้ register Q เพื่อเก็บผลหาร (quotient) register A เพื่อเก็บเศษ (remainder) และ M เพื่อเก็บตัวหาร (divisor) ค่าเริ่มต้นของ A ถูกเก็บไว้ที่ 0 และค่าของมันจะถูก restore ซึ่งเป็นเหตุผลที่วิธีนี้เรียกว่า restoring division

• เริ่มต้น register ด้วยค่า:
  • Q = Dividend (ตัวถูกหาร)
  • A = 0
  • M = divisor (ตัวหาร)
  • N = จำนวน bit ของ dividend
• Left shift AQ หมายถึงการนำ register A และ Q มารวมเป็นหน่วยเดียว
• ลบ A ด้วย M และเก็บใน A
• ตรวจสอบ most significant bit (MSB) ของ A:
  • ถ้าเป็น 0 ตั้ง least significant bit เป็น 1
  • มิฉะนั้น ตั้ง least significant bit เป็น 0
• Restore ค่าของ A และลดค่าตัวนับ N ลง 1
• ถ้า N = 0 หยุดลูป มิฉะนั้น ไปขั้นตอน 2
• ผลหาร (quotient) จะถูกเก็บใน register Q

Flow Chart

ตัวอย่าง

โค้ด C++ สำหรับวิธีข้างต้น

#include <iostream>
using namespace std;

int main(){
    // เริ่มต้นตัวแปรทั้งหมดด้วย Dividend = 9, Divisor = 2
    int Q = 8, q = 1, M = 3;
    short N = 4;
    int A = Q;
    M <<= N;
    // ลูปสำหรับการหารด้วย bit operation
    for(int i = N-1; i >= 0; i--) {
        A = (A << 1) - M;
        // ตรวจสอบ MSB ของ A
        if(A < 0) {
            q &= ~(1 << i); // ตั้ง i-th bit เป็น 0
            A = A + M;
        } else {
            q |= 1 << i; // ตั้ง i-th bit เป็น 1
        }
    }
    cout << "Quotient: " << q;
    return 0;
}

ผลลัพธ์

Quotient: 2

สรุป

ในบทช่วยสอนนี้ เราอภิปรายอัลกอริทึมการหารแบบ Restoring สำหรับ unsigned integer เราอภิปรายวิธีง่ายๆ ในการแก้ปัญหานี้ด้วยความช่วยเหลือของ flow chart และการประยุกต์ใช้ bit operations เรายังอภิปรายโปรแกรม C++ สำหรับปัญหานี้ซึ่งเราสามารถทำได้กับภาษาโปรแกรมมิ่งอย่าง C, Java, Python ฯลฯ เราหวังว่าบทช่วยสอนนี้จะเป็นประโยชน์