计算函数并将输出数字逐个写入数组

Question

所以，我基本上需要的是使用 C++ 计算指数函数 (2^n)*(2^(n-1)-1) 的值，其中n 是一个 unsigned int 类型的用户输入。由于 n 可以在 unsigned int 范围内分配任何值，我不能简单地计算函数值并将其分配给一些 unsigned int 变量（因为结果数字显然会超出所述范围）。因此，以某种方式逐个获取我想要的函数值并将每个数字写为数组元素对我来说似乎是合理的。唯一的挣扎就是实现这个方法。

任何想法（使用建议的方法或任何其他方法）将不胜感激。

编辑：现在我有以下代码：

outdated

正如预期的那样，它只适用于较小的 n

编辑 2：正如其中一位评论员所建议的，我已经手工完成了一些二进制数。收获颇丰，但我仍然需要帮助。现在我有以下代码，它将正确输出所述函数的二进制值：

outdated

剩下的就是将这个值转换为十进制和十六进制。我没有使用字符串 class 的经验，因此不胜感激。

编辑3：感谢大家的帮助。我已经完成了我的程序并将其转换为 C（不是自愿的，因为我的教授告诉我这样做）。对于任何感兴趣的人，当前版本的代码如下所示：

#include <stdio.h>
#include <stdlib.h>

void binary(unsigned int);
void hex(unsigned int);
void decimal(unsigned int);
int *calculatepower(unsigned int, unsigned int);
void addition(int*, int*, int);

int main(int argc, char** argv){
    if (argc != 2){
        printf("wrong number of arguments \n");
        return -2;
    }
    unsigned int n = atoi(argv[1]);
    printf("exponent - %d \n", n);
    binary(n);
    hex(n);
    decimal(n);
    return 0;
}

void binary(unsigned int n){
    int i;
    printf("binary - ");
    for (i=n-1; i>0; i--)
        printf("1");
    for (i=n; i>0; i--)
        printf("0");
    printf("\n");
}

void hex(unsigned int nn){
    int ones = nn-1;
    int zeroes = nn;
    int hexzeroes=0, hexfs=0, i;
    char switchf, switchzero;
    while (zeroes > 3){
        hexzeroes+=1;
        zeroes-=4;
    }
    switch (zeroes){
        case 0:
            break;
        case 1:
            switchzero='E';
        ones-=3;
        break;
        case 2:
            switchzero='C';
        ones-=2;
        break;
        case 3:
            switchzero='8';
        ones-=1;
        break;
        default:
            break;
    }
    while (ones>3){
        hexfs+=1;
        ones-=4;
    }
    switch (ones){
        case 0:
            switchf='[=12=]';
            break;
        case 1:
            switchf='1';
            break;
        case 2:
            switchf='3';
            break;
        case 3:
            switchf='7';
            break;
        default:
            break;
    }
    printf("hexadecimal - %c", switchf);
    for (i=0; i<hexfs; i++)
        printf("F");
    if (zeroes !=0) printf("%c", switchzero);
    for (i=0; i<hexzeroes; i++)
        printf("0");
    printf("\n");
}

void decimal(unsigned int nn){
    unsigned int n=nn;
    int *str,*powerstr, i, flag=0;
    // decimal = 2^n+...+2^((2*n)-1)
    unsigned int size = (2*n)/3 + 2;
    str = (int*)calloc(size, sizeof(*str));
    if(str==NULL)
    {
        printf("unable to allocate memory");
        exit(0);
    }
    for (i=0; i<size; i++)
    {
        str[i] = 0;
    }
    for (n;n<2*nn-1;n++){
        powerstr = calculatepower( n, size);
        addition(str,powerstr,size);
   }
    printf("decimal - ");
    for (i=0;i<size;i++) {
        if ((*(str+i)==0) && (flag==0)){
            continue;
        }
        printf("%d", *(str+i));
        flag+=1;
    }
}

int *calculatepower(unsigned int n, unsigned int size){
    int i, j, buf=0, *powerstr;
    powerstr = (int*)calloc(size, sizeof(*powerstr));
    for (i=0; i<size; i++)
    {
        powerstr[i] = 0;
    }
    powerstr[size-1]=1;
    for(j=0;j<n;j++) {
        for (i=size-1; i > -1; i--) {
            powerstr[i] = powerstr[i] * 2;
            if (buf!=0) {
                powerstr[i] += 1;
                buf=0;
            }
            if (powerstr[i] > 9) {
                buf = 1;
                powerstr[i]%=10;
            }

        }
    }
    return powerstr;
}

void addition(int *str, int *powerstr, int size){
    int i, buf=0;
    for (i=size-1; i > -1; i--) {
        str[i] = powerstr[i] + str[i];
        if (buf!=0) {
            str[i] += 1;
            buf=0;
        }
        if (str[i] > 9) {
            buf = 1;
            str[i]%=10;
        }
    }
}

很遗憾，我没有足够的时间来润色它。目前最大的问题是没有释放分配的内存，我稍后会修复它，但我不会再更新问题了。再次感谢大家的回答和评论。

Answer 1

如果 unsigned int 无法容纳您的文件，您可以使用 unsigned long 或 unsigned long long（或 uintX_t，其中 X 是您的平台支持的最大大小）输出。如果这对您的用例来说仍然不够，那么要么实现您自己的大整数 class，要么使用现有的库（如果您负担得起，推荐使用）。那里有几个。例如，GNU Multiple Precision Arithmetic Library (GMP) and bigint-library. See this list 表示更多。

如果您决定自己动手实施自己的 class，这可能会给您一些关于如何开始的线索。（请注意，对于效率问题，可以应用数论算法。要实现良好的实现并非易事）。

template<typename T = unsigned, int Base = 10> class Bigint {
    std::vector<T> digits;
    bool sign; // For e.g. true for + or 0, false for -

public:
    Bigint() : digits(), sign(true) { }
    
    Bigint(int x)
    {
        // Insert digits of x into digits vector
        // Don't forget the sign
    }
    // Do the same with other types: short, long, unsigned, etc.
    
    Bigint(const char *x)
    {
        // You need to parse x. Bad formatting is to be handled (tip: use exceptions)
    }
    // Provide an std::string version
    
    Bigint(const Bigint& bi) : digits(bi.digits), sign(bi.sign) {}

    Bigint& operator=(const Bigint& bi)
    {
        // Copy...
        return *this;
    }
    
    // You also have to implement operators
    Bigint& operator+(const Bigint& bi)
    {
        // Logic...
        return *this;
    }
    // Other operators: -, /, %, bitwise, etc.
    // Tip: you can use a helper class to be used by both / and % since they share a similar logic (for avoiding redundant code).
    
    Bigint power(const Bigint& bi) // Provide other signatures: int, string, etc.
    {
        // Logic...
    }
};

Answer 2

对于 16 位整数它是可行的并产生大约 40k 个十进制字符。对于 32 位整数，与其说它是 10^20 个十进制字符，不如说它超出了任何可能的范围。即使每秒输出一百万个字符，也比宇宙的生命周期还长。

这是 16 位整数的代码。对于 n = 65535，不包括输出时间，运行大约 3 秒。它通过累积以 10 为底的总和并偶尔进行归一化以防止溢出来提高性能。

#include <iostream>
#include <vector>
#include <string>
#include <cstdint>
using std::cout;
using std::vector;
using std::string;

struct BigDecPower2 {
    static constexpr uint32_t Normalize_Max{ 26 };        // int8:3, int16:10, int32:26
    vector<uint32_t> v;
    uint32_t top;
    uint32_t normalize_count;
    BigDecPower2(uint32_t n) : v(n), top(0), normalize_count(0) {};
    void normalize()
    {
        normalize_count = 0;
        for (uint32_t i = 0;; i++)
        {
            v[i + 1] += v[i] / 10u;
            v[i] = v[i] % 10u;
            if (i >= top && v[i + 1] == 0)
            {
                top = i;
                return;
            }
        }
    }
    void times2() {
        for (uint32_t i = 0; i <= top; i++)
            v[i] *= 2;
        if ((++normalize_count) > Normalize_Max)
            normalize();
    }
};

void add(BigDecPower2& v1, const BigDecPower2& v2)
{
    uint32_t max_top = v1.top > v2.top ? v1.top : v2.top;
    for (uint32_t i = 0; i <= max_top; i++)
        v1.v[i] += v2.v[i];
    if (++v1.normalize_count < v2.normalize_count)
        v1.normalize_count = v2.normalize_count;
    if (v1.normalize_count > v1.Normalize_Max)
        v1.normalize();
}

void print_base(unsigned int n, int number_base)
{
    int64_t ones = n-1;
    int64_t zeros = n;
    if (number_base ==2)
    {
        while (ones-- > 0)
            cout << '1';
        while (zeros-- > 0)
            cout << '0';
    }
    else if (number_base == 16) {
        int resid = (ones + zeros) % 4;
        if (resid == 0)
            resid = 4;
        cout << "~137F"[resid];
        ones -= resid;
        while ((ones -= 4) > 0)
            cout << 'F';
        cout << "8CEF"[ones + 3];
        zeros /= 4;
        while (zeros--)
            cout << '0';
    }
    else if (number_base == 10)
    {
        BigDecPower2 v_accum(40000u);
        BigDecPower2 v_pwr(40000u); v_pwr.v[0] = 1;
        for (uint32_t i = 0; i < n - 1; i++)
        {
            add(v_accum, v_pwr);
            v_pwr.times2();
        }
        for (uint32_t i = 0; i < n; i++)
            v_accum.times2();
        v_accum.normalize();
        for (uint32_t i = v_accum.top; i != -1; i--)
            cout << static_cast<char>(v_accum.v[i] + '0');
    }
    cout << '\n';
}

int main()
{
    //    calcs in about 3 seconds, outputs about 40k decimal chars
    //    print_base(0xffff, 10);
    // Demo
    for (int i = 1; i < 10; i++)
    {
        print_base(i, 2);
        print_base(i, 16);
        print_base(i, 10);
        cout << '\n';
    }
}

计算函数并将输出数字逐个写入数组

Calculating function and writing output number by number as an array

c

c++

math

numbers