高精度下二进制转为十进制的办法?

P1009 [NOIP1998 普及组] 阶乘之和

Mari316 @ 2025-01-11 14:31:09

这一题我参照了计算机组成课本上的硬件乘法电路,使用加法和左移实现了乘法器。手动验证后,我发现十六进制结果是对的。但是因为数组中最后结果是二进制,我查不到高精度下二转十的相关资料,有没有什么办法呢?

#include<stdio.h>
#include<stdlib.h>
class highAcuInt {
public:
    unsigned int* value;
    highAcuInt() {
        value = new unsigned int[100]{ 0 };
    }
    highAcuInt(highAcuInt* old) {
        this->value = new unsigned int[100]{ 0 };
        for (int i = 0; i < 100; i++) {
            this->value[i] = old->value[i];
        }
    }
    void setvalue(int i, unsigned int a) {
        this->value[i] = a;
    }
    int getvalue(int i) {
        return this->value[i];
    }
    static highAcuInt bitwiseAND(highAcuInt& h1, highAcuInt& h2) {//按位与
        highAcuInt result = new highAcuInt();
        for (int i = 0; i < 100; i++) {
            result.value[i] = h1.value[i] & h2.value[i];//数组每个元素按位与
        }
        return result;
    }
    highAcuInt highAccuLShift(unsigned int a) {//左移运算
        unsigned int n = a / 32;//每个左移32位应视为整体
        unsigned int s = a % 32;//其余部分单独处理
        highAcuInt result = new highAcuInt(this);
        if (n != 0) {
            for (int i = n; i < 100; i++) {
                result.value[i - n] = result.value[i];
            }//左移n*32位
            for (int i = 1; i <= n; i++) {
                result.value[100 - i] = 0;
            }//左移时右侧填充0
        }
        for (int i = 0; i < 99 - n; i++) {
            int hw = 0;
            result.value[i] = (result.value[i] << s);
            result.value[i] += (result.value[i + 1] >> 32 - s);
        }//处理其余部分。将i+1单元左移被舍弃的部分存入i位置的低位
        result.value[99] = (result.value[99] << s);//最低位单独处理
        return result;
    }
    highAcuInt highAccuRShift(unsigned int a) {//右移运算,本题没什么用,建议忽视
        unsigned int n = a / 32;//每个右移32位应视为整体
        unsigned int s = a % 32;//其余部分单独处理
        highAcuInt result = new highAcuInt(this);
        if (n != 0) {
            for (unsigned int i = 99 - n; i < 100; i--) {
                result.value[i + n] = result.value[i];
            }//右移n*32位
            for (int i = 0; i < n; i++) {
                result.value[i] = 0;
            }//右移时左侧填充0(由于该类是无符号数,因此是逻辑右移)
        }
        for (int i = 99; i >= n; i++) {
            result.value[i] = (result.value[i] >> s);
            //result.value[i] += (result.value[i + 1] << 32 - s);
        }//处理其余部分。将i+1单元右移被舍弃的部分存入i位置的高位
        return result;
    }
    static highAcuInt highAccuPlus(highAcuInt& h1, highAcuInt& h2) {//加法运算
        highAcuInt result = new highAcuInt();
        int cf = 0;//存放进位标志
        for (unsigned int i = 99; i < 100; i--) {//注:使用i--遍历数组的特殊写法,为了避免unsigned恒大于0
            unsigned int temp = h1.value[i] + h2.value[i] + cf;//类似全加器的原理
            if (
                (temp < h1.value[i] || temp < h2.value[i]) ||
                (h1.value[i] == 0xFFFFFFFF && h2.value[i] == 0xFFFFFFFF)//判断无符号数的加法溢出
                )
                cf = 1;//若溢出则记录进位
            else cf = 0;
            result.value[i] = temp;
        }
        return result;
    }
    static highAcuInt highAccuMultiply(highAcuInt& h1, highAcuInt& h2) {//无符号乘法运算
        int n0 = 0;
        highAcuInt result = new highAcuInt();
        highAcuInt mask = new highAcuInt();
        mask.value[0] = 0x80000000;//mask用于判断h2最高位是否为0
        highAcuInt temp = bitwiseAND(h2, mask);
        for (int i = 0; i < 3200; i++) {
            result = result.highAccuLShift(1);
            if (temp.value[0] != 0) {
                result = highAccuPlus(result, h1);
            }
            h2 = h2.highAccuLShift(1);//乘法电路原理,使用加法和移位实现无符号数乘法
            temp = bitwiseAND(h2, mask);
        }
        return result;
    }
    static void highAccuFactorial(int a) {
        highAcuInt result = new highAcuInt();
        result.value[99] = 1;
        highAcuInt h = new highAcuInt();
        h.value[99] = 1;
        for (int i = 1; i <= a; i++) {
            h.value[99] = i;
            result = highAccuMultiply(result, h);
        }
        printf("0x%.8x%.8x%.8x%.8x%.8x", result.value[90], result.value[91], result.value[92], result.value[93], result.value[94]);
        printf("%.8x%.8x%.8x%.8x%.8x\n", result.value[95], result.value[96], result.value[97], result.value[98], result.value[99]);
    }
};
int main() {
    int a = 50;
    highAcuInt::highAccuFactorial(a);
}

by anke2017 @ 2025-01-11 14:54:21

Cu ball


|