Bigintegerを文字列に変換する方法

Question

数字の桁のベクトルを持っています。ベクトルは、基数2^32のシステムで大きな整数を表します。たとえば：

vector <unsigned> vec = {453860625, 469837947, 3503557200, 40} 

このベクターは、この大きな整数を表す：

base = 2^32 
3233755723588593872632005090577 = 40 * base^3 + 3503557200 * base^2 + 469837947 * base + 453860625 

文字列で、この10進数表現を取得する方法は？

Answer 1

ここでは、任意のサイズの整数を表す単語値のベクトルから10進数の文字列を取得する非効率的な方法です。

これはクラスとして実装することをお勧めします。これは、カプセル化を強化し、数学演算子を追加できるようにするためですが、質問に応じるために、std::vector<unsigned>オブジェクトを操作するための自由な関数です。しかし、std::vector<unsigned>のエイリアスとしてtypedef BiTypeを使用しています。

このコードのほとんどは、2進除算を行う関数です。その多くはstd::bitsetで実行できるものを複製しますが、任意のサイズのビットセットについては、unsignedワードのベクトルとして複製します。効率を向上させたい場合は、ビット単位ではなくワード単位の演算を行う除算アルゴリズムを組み込みます。また、除算コードは10で除算するために使用される汎用コードであるため、専用の除算コードに置き換えることができます。

一般に、コードはunsignedワードのベクトルを想定しており、そのベースは最大unsignedの値に1を加えた値になっています。私は、2の累乗ではない小規模な基底または基底について、何かが間違っていた場合はどこでもコメントを残しました（2進除算は基数が2の累乗である必要があります）。

また、私はあなたがOPで与えた1つのケースのみをテストしました。これは未確認の新しいコードなので、さらにテストをしたいことがあります。問題が見つかった場合は、ここでバグを修正していただきます。

#include <iostream> 
#include <string> 
#include <vector> 
#include <algorithm> 

namespace bigint { 
using BiType = std::vector<unsigned>; 

// cmp compares a with b, returning 1:a>b, 0:a==b, -1:a<b 
int cmp(const BiType& a, const BiType& b) { 
    const auto max_size = std::max(a.size(), b.size()); 
    for(auto i=max_size-1; i+1; --i) { 
     const auto wa = i < a.size() ? a[i] : 0; 
     const auto wb = i < b.size() ? b[i] : 0; 
     if(wa != wb) { return wa > wb ? 1 : -1; } 
    } 
    return 0; 
} 

bool is_zero(BiType& bi) { 
    for(auto w : bi) { if(w) return false; } 
    return true; 
} 

// canonize removes leading zero words 
void canonize(BiType& bi) { 
    const auto size = bi.size(); 
    if(!size || bi[size-1]) return; 
    for(auto i=size-2; i+1; --i) { 
     if(bi[i]) { 
      bi.resize(i + 1); 
      return; 
     } 
    } 
    bi.clear(); 
} 

// subfrom subtracts b from a, modifying a 
// a >= b must be guaranteed by caller 
void subfrom(BiType& a, const BiType& b) { 
    unsigned borrow = 0; 
    for(std::size_t i=0; i<b.size(); ++i) { 
     if(b[i] || borrow) { 
      // TODO: handle error if i >= a.size() 
      const auto w = a[i] - b[i] - borrow; 
      // this relies on the automatic w = w (mod base), 
      // assuming unsigned max is base-1 
      // if this is not the case, w must be set to w % base here 
      borrow = w >= a[i]; 
      a[i] = w; 
     } 
    } 
    for(auto i=b.size(); borrow; ++i) { 
     // TODO: handle error if i >= a.size() 
     borrow = !a[i]; 
     --a[i]; 
     // a[i] must be set modulo base here too 
     // (this is automatic when base is unsigned max + 1) 
    } 
} 

// binary division and its helpers: these require base to be a power of 2 
// hi_bit_set is base/2 
// the definition assumes CHAR_BIT == 8 
const auto hi_bit_set = unsigned(1) << (sizeof(unsigned) * 8 - 1); 

// shift_right_1 divides bi by 2, truncating any fraction 
void shift_right_1(BiType& bi) { 
    unsigned carry = 0; 
    for(auto i=bi.size()-1; i+1; --i) { 
     const auto next_carry = (bi[i] & 1) ? hi_bit_set : 0; 
     bi[i] >>= 1; 
     bi[i] |= carry; 
     carry = next_carry; 
    } 
    // if carry is nonzero here, 1/2 was truncated from the result 
    canonize(bi); 
} 

// shift_left_1 multiplies bi by 2 
void shift_left_1(BiType& bi) { 
    unsigned carry = 0; 
    for(std::size_t i=0; i<bi.size(); ++i) { 
     const unsigned next_carry = !!(bi[i] & hi_bit_set); 
     bi[i] <<= 1; // assumes high bit is lost, i.e. base is unsigned max + 1 
     bi[i] |= carry; 
     carry = next_carry; 
    } 
    if(carry) { bi.push_back(1); } 
} 

// sets an indexed bit in bi, growing the vector when required 
void set_bit_at(BiType& bi, std::size_t index, bool set=true) { 
    std::size_t widx = index/(sizeof(unsigned) * 8); 
    std::size_t bidx = index % (sizeof(unsigned) * 8); 
    if(bi.size() < widx + 1) { bi.resize(widx + 1); } 
    if(set) { bi[widx] |= unsigned(1) << bidx; } 
    else { bi[widx] &= ~(unsigned(1) << bidx); } 
} 

// divide divides n by d, returning the result and leaving the remainder in n 
// this is implemented using binary division 
BiType divide(BiType& n, BiType d) { 
    if(is_zero(d)) { 
     // TODO: handle divide by zero 
     return {}; 
    } 
    std::size_t shift = 0; 
    while(cmp(n, d) == 1) { 
     shift_left_1(d); 
     ++shift; 
    } 
    BiType result; 
    do { 
     if(cmp(n, d) >= 0) { 
      set_bit_at(result, shift); 
      subfrom(n, d); 
     } 
     shift_right_1(d); 
    } while(shift--); 
    canonize(result); 
    canonize(n); 
    return result; 
} 

std::string get_decimal(BiType bi) { 
    std::string dec_string; 

    // repeat division by 10, using the remainder as a decimal digit 
    // this will build a string with digits in reverse order, so 
    // before returning, it will be reversed to correct this. 
    do { 
     const auto next_bi = divide(bi, {10}); 
     const char digit_value = static_cast<char>(bi.size() ? bi[0] : 0); 
     dec_string.push_back('0' + digit_value); 
     bi = next_bi; 
    } while(!is_zero(bi)); 
    std::reverse(dec_string.begin(), dec_string.end()); 
    return dec_string; 
} 

} 

int main() { 
    bigint::BiType my_big_int = {453860625, 469837947, 3503557200, 40}; 
    auto dec_string = bigint::get_decimal(my_big_int); 
    std::cout << dec_string << '\n'; 
} 

出力：効率的

3233755723588593872632005090577