c++ - 将 vector<bool> 转换为十进制(作为字符串)

Question

使用这个函数我们可以轻松地将 vector 转换为十进制(整数):

vector<bool> A = {0, 1, 1, 1,0,1}; # A size will change during run time
long int integer = 0, n = 0;

    for (auto i : A)
    {
        if (i)
        {
            integer += pow(2, n);
        }
        n = n + 1;
    }

但如果 vector 的元素超过 64 个，结果将不可预测。

我们如何编写类似的函数，但返回的是字符串呢？

Answer 1

正如其他人所建议的那样，使用 std::bitset是表示任何固定长度的二进制数的更好选择(对于动态长度，如您的情况，请参阅 boost::dynamic_bitset )。 This link解释了为什么不使用 std::vector<bool> 的一些原因.

您的问题几乎可以概括为实现 BigNum 类。就像您在方法中所做的那样，您首先需要将您的值从二进制转换为十进制(但现在需要 64 位以上的精度)。一旦构建了 BigNum，将其转换为字符串就很简单了。我通过简单地修改 BigNum 实现了您请求的算法我前段时间制作的类(class)。

要打印二进制数，以下几行就足够了。

/*Creates a 90-digit binary number with all bits set.*/
std::vector<bool> A(90, 1);
/*Prints its decimal reprsentation*/
cout << longBinaryToDecimalAsString(A);

至于实现:

#ifndef BIG_NUM_H
#define BIG_NUM_H

#include <string>
#include <vector>
#include <sstream>
#include <cstdint>

class BigNum {

public:

    BigNum(){values.push_back(0);}

    BigNum(std::uint64_t val){
        if (val == 0)
            values.assign(1, 0);
        else{
            while (val > 0){
                values.push_back(val % 10);
                val /= 10;
            }
        }
    }

    BigNum &operator+=(BigNum &rhs)
    {
        std::vector<std::uint8_t> *lowAddend, *bigAddend;
        /*If right value is larger, ‘values’ vector will always grow*/
        if (rhs.values.size() > values.size()){
            values.resize(rhs.values.size(), 0);
            lowAddend = &values;
            bigAddend = &rhs.values;
        }
        else{
            values.push_back(0);
            bigAddend = &values;
            lowAddend = &rhs.values;
        }

        std::uint8_t carry = 0;
        size_t i = 0;
        /*First we sum lower part*/
        for (; i < lowAddend->size(); ++i){
            std::uint8_t sum = values[i] + rhs.values[i] + carry;
            values[i] = sum % 10;
            carry = sum / 10;
        }
        /*Now we copy the remaining part*/
        for (; i < bigAddend->size(); ++i){
            /*For 10 10, sum will be 18, at most*/
            std::uint8_t sum = (*bigAddend)[i] + carry;
            values[i] = sum % 10;
            carry = sum / 10;
        }
        this->trimFrontalZeros();
        return *this;
    }
    BigNum &operator*=(BigNum &rhs)
    {
        /*Case when one of the operands is Zero*/
        if (this->isZero())
            return *this;
        else if (rhs.isZero()){
            values.assign(1, 0);    
            return *this;
        }

        size_t maxLen = values.size() + rhs.values.size();
        std::vector<std::uint8_t> product(maxLen);

        size_t lowSize, bigSize;
        std::vector<std::uint8_t> *multiplier, *multiplicand;

        /*The iteration process for the multiplicaiton is developed as the multiplier (A in A*B)
        as the one with more digits.*/
        if (values.size() > rhs.values.size()){
            multiplier = &values;
            multiplicand = &rhs.values;
            bigSize = values.size();
            lowSize = rhs.values.size();
        }
        else{
            multiplier = &rhs.values;
            multiplicand = &values;
            bigSize = rhs.values.size();
            lowSize = values.size();
        }

        /*Implemented as 'values x rhs.values' */
        std::uint8_t carry = 0;
        for (size_t n = 0; n < maxLen; ++n){

            size_t numIters;
            if (maxLen - n - 1< lowSize) numIters = maxLen - n - 1;
            else                         numIters = std::min(n + 1, lowSize);

            std::uint64_t sum = 0;
            for (size_t i = 0; i < numIters; ++i){
                size_t indBelow = i + n + 1 - std::min(n + 1, lowSize);
                size_t indAbove = std::min(n + 1, lowSize) - 1 - i;
                std::uint8_t be = (*multiplier)[indBelow];
                std::uint8_t ab = (*multiplicand)[indAbove];
                sum += be*ab;
            }
            sum += carry;
            product[n] = sum % 10;
            carry = sum / 10;
        }
        values.assign(product.begin(), product.end());
        this->trimFrontalZeros();
        return *this;
    }

    std::string toString(){
        std::stringstream ss;
        std::copy(values.rbegin(), values.rend(), std::ostream_iterator<int>(ss, ""));
        return ss.str();
    }

private:

    bool isAbsOne() {return values.size() == 1 && values[0] == 1;}
    bool isZero()   {return values.size() == 1 && values[0] == 0;}
    void trimFrontalZeros(){
        size_t newSize = values.size();
        auto it = values.rbegin();
        while (it != values.rend() && *it == 0){
            ++it;
            --newSize;
        }
        values.resize(newSize);
    }

    std::vector<std::uint8_t> values;
};

std::string longBinaryToDecimalAsString(std::vector<bool> &longBinary){

    BigNum big;
    std::uint64_t n = 0;
    for (bool bit : longBinary){
        if (bit){
            if (n > 63){
                BigNum aux(1);          
                for (std::uint64_t i = 0; i < n / 32; ++i){
                    aux *= BigNum(1ULL << 32);
                }
                aux *= BigNum(1ULL << (n % 32));
                big += aux;
            }
            else{
                big += BigNum(1ULL << n);
            }
        }
        ++n;
    }
    return big.toString();
}

#endif

请注意这是一个非常简化的版本 BigNum类(class)。将它用于此问题之一以外的目的可能会产生不良结果。例如，它没有考虑 + 的负数。和 *操作。