定點小數補碼一位乘（Booth比較法）

程序：
[cpp] 
// 定點小數補碼一位乘（Booth比較法） 
// http://blog.csdn.net/justme0 
 
#define _CRT_SECURE_NO_WARNINGS 
#include <iostream> 
#include <bitset> 
#include <string> 
using namespace std; 
 
const int n = 4;    // 數值位位數 
 
// a,b聯合右移（算術移位） 
void RightMove(bitset<n + 2> &a, bitset<n + 1> &b, bool &eBit) 
{ 
    eBit = b[0]; 
 
    b >>= 1;                       
    b[n] = a[0]; 
 
    a >>= 1; 
    a[n + 1] = a[n];    // 算術右移 
} 
 
bitset<n + 2> operator+(bitset<n + 2> a, bitset<n + 2> b) // 求a,b的算術和 
{ 
    return a.to_ullong() + b.to_ullong(); 
} 
bitset<n + 2> operator-(bitset<n + 2> a, bitset<n + 2> b) 
{ 
    return a.to_ullong() - b.to_ullong(); 
} 
 
bitset<n + 1> GetComplement(bitset<n + 1> a) 
{ 
    if (a[n]) 
    { 
        a = ~a.to_ullong() + 1; 
        a.set(n);   // NOTE 
    } 
 
    return a; 
} 
bitset<2 * n + 1> GetComplement(const bitset<n + 2> high, const bitset<n + 1> low)    // low的最低位捨棄，因為它不屬於積，而是原來乘數的符號 
{ 
    bitset<2 * n + 1> ans(high.to_string().substr(1) + low.to_string().substr(0, 4)); 
 
    if (ans[2 * n]) 
    { 
        ans = ~ans.to_ullong() + 1; 
        ans.set(2 * n); // NOTE 
    } 
 
    return ans; 
} 
 
enum Sign{_00, _01, _10, _11}; 
 
Sign Test(bool a, bool b) 
{ 
    if (!a && !b) 
    { 
        return _00; 
    } 
    else if (!a && b) 
    { 
        return _01; 
    } 
    else if (a && !b) 
    { 
        return _10; 
    }  
    else // if (a && b) // 所有路徑都必須返回值 
    { 
        return _11; 
    } 
} 
 
bitset<2 * n + 1> ComplementOneMul(const bitset<n + 1> X, const bitset<n + 1> Y)//傳進被乘數X和乘數Y（原碼表示） 
{ 
    bitset<n + 2> A;                                  // A放部分積（最後是積的高位） 
    bitset<n + 2> tmp = GetComplement(X).to_ullong(); 
    tmp[n + 1] = tmp[n];                                // 注意補碼最高位的擴展 
    const bitset<n + 2> B(tmp);                           // B是X的補碼  //無法利用返回值的不同而重載，故引入tmp 
    bitset<n + 1> C = GetComplement(Y);                   // C是Y0.Y1Y2...Yn（Y的補碼） 
    int cd = n + 1;                                     // cd是計數器 
    bool Yn1 = 0; 
 
#pragma region 核心算法 
 
    while (cd--) 
    { 
        switch (Test(C[0], Yn1))    // 檢測Y(i+1)-Y(i) 
        { 
        case _00: case _11: 
            break; 
 
        case _10: 
            A = A - B; 
            break; 
 
        case _01: 
            A = A + B; 
            break; 
 
        default: 
            break; 
        } 
        if (cd != 0)    // 最後一次不移位 
        { 
            RightMove(A, C, Yn1);   // A,C聯合右移，C的低位移至Yn1 
        } 
    } 
 
#pragma endregion 核心算法 
 
    return GetComplement(A, C); 
} 
 
bitset<2 * n + 1> DirectMul(const bitset<n + 1> X, const bitset<n + 1> Y) 
{ 
    const bitset<n> x(X.to_ullong()); // 用截斷高位的方法取絕對值 
    const bitset<n> y(Y.to_ullong()); 
    bitset<2 * n + 1> ans(x.to_ullong() * y.to_ullong()); 
    ans[2 * n] = X[n] ^ Y[n];           // 最後單獨計算符號位 
    return ans; 
} 
 
int main(int argc, char **argv) 
{ 
    //freopen("cin.txt", "r", stdin); 
    string inputStrX; 
    string inputStrY; 
    while (cin >> inputStrX >> inputStrY) 
    { 
        const bitset<n + 1> X(inputStrX); // X是被乘數 
        const bitset<n + 1> Y(inputStrY); // Y是乘數 
 
        cout << "ComplementOneMul:\t" << X << " * " << Y << " = " 
            << ComplementOneMul(X, Y) << endl; 
        cout << "DirectMul:\t\t" << X << " * " << Y << " = " 
            << DirectMul(X, Y) << endl << endl; 
    } 
 
    return 0; 
} 
運行結果：