如何将十进制字符串转换为二进制字符串？

Question

我有一个十进制字符串，长度小于5000：

std::string decimalString = "555";

有没有一种标准的方法将这个字符串转换为二进制表示形式？就像这样：

std::string binaryString = "1000101011";

---

更新。 这篇文章 对我很有帮助。

- Denis

---

binaryString 和 decimalString 之间有什么明显的对应关系吗？我看不出来。 - Paul R

@Paul R，这是示例字符串。BinaryString与decimalString无关。 - Denis

好的 - 也许您可以给出一个适当的示例（可能使用较短的输入字符串），因为不清楚您正在寻找什么样的转换？ - Paul R

供日后参考，该数字的实际二进制表示为100000011111001111010100010100001000011001110111010101000110010110101100100111001100110000110111011110000011100000000000101101001101001100110111111000100011000100000110010100101100111011011010101101111001010010101010。 - Kevin

@Denis：好的-看起来你想将十进制字符串转换为实际的值，然后将该值转换回二进制表示形式作为字符串。 - Paul R

Answer 1

由于数字非常大，您可以使用一个大整数库（比如boost），或者自己编写必要的函数。

如果您决定自己实现这些函数，一种方法是在代码中实现旧的纸笔长除法方法，您需要反复用2去除十进制数，并将余数累加到另一个字符串中。这可能有点繁琐，但是2的除法不应该太难。

- Sufian Latif

---

无法工作。如果十进制字符串非常大，则无法表示为数字，因此无法被2整除。 - derek

Answer 2

因为10不是2的幂（或者说反过来），所以你需要在十进制中实现算术运算。你需要以下两个操作：

1. 整数除以2
2. 检查除以2后的余数

两者可以通过相同的算法计算。或者，你可以使用各种C++大整数库，如GNU MP或Boost.Multiprecision。

- Niklas B.

---

谢谢您的建议。您的答案也帮助了我。 - Denis

Answer 3

我试图这样做... 我不认为我的答案是正确的，但这是我尝试做的事情的想法。

假设我们有两个小数：

100 和 200。

要将它们连接起来，我们可以使用以下公式：

a * CalcPower(b) + b 其中 CalcPower 如下所示。

知道了这一点，我试图将非常长的小数字符串分成每四个一组的块。我将每个字符串转换为二进制并将它们存储在一个向量中。

最后，我遍历每个字符串并应用上述公式来将每个二进制字符串连接成一个巨大的字符串。

我没有让它工作，但这是代码... 也许别人能看出我哪里错了... BinaryAdd、BinaryMulDec、CalcPower 运行得很好... 问题实际上在 ToBinary 中。

#include <iostream>
#include <bitset>
#include <limits>
#include <algorithm>

std::string BinaryAdd(std::string First, std::string Second)
{
    int Carry = 0;
    std::string Result;

    while(Second.size() > First.size())
        First.insert(0, "0");

    while(First.size() > Second.size())
        Second.insert(0, "0");

    for (int I = First.size() - 1; I >= 0; --I)
    {
        int FirstBit = First[I] - 0x30;
        int SecondBit = Second[I] - 0x30;
        Result += static_cast<char>((FirstBit ^ SecondBit ^ Carry) + 0x30);
        Carry = (FirstBit & SecondBit) | (SecondBit & Carry) | (FirstBit & Carry);
    }

    if (Carry)
        Result += 0x31;

    std::reverse(Result.begin(), Result.end());
    return Result;
}

std::string BinaryMulDec(std::string value, int amount)
{
    if (amount == 0)
    {
        for (auto &s : value)
        {
            s = 0x30;
        }
        return value;
    }

    std::string result = value;
    for (int I = 0; I < amount - 1; ++I)
        result = BinaryAdd(result, value);

    return result;
}

std::int64_t CalcPowers(std::int64_t value)
{
    std::int64_t t = 1;
    while(t < value)
        t *= 10;

    return t;
}

std::string ToBinary(const std::string &value)
{
    std::vector<std::string> sets;
    std::vector<int> multipliers;

    int Len = 0;
    int Rem = value.size() % 4;

    for (auto it = value.end(), jt = value.end(); it != value.begin() - 1; --it)
    {
        if (Len++ == 4)
        {
            std::string t = std::string(it, jt);
            sets.push_back(std::bitset<16>(std::stoull(t)).to_string());
            multipliers.push_back(CalcPowers(std::stoull(t)));
            jt = it;
            Len = 1;
        }
    }

    if (Rem != 0 && Rem != value.size())
    {
        sets.push_back(std::bitset<16>(std::stoull(std::string(value.begin(), value.begin() + Rem))).to_string());
    }

    auto formula = [](std::string a, std::string b, int mul) -> std::string
    {
        return BinaryAdd(BinaryMulDec(a, mul), b);
    };

    std::reverse(sets.begin(), sets.end());
    std::reverse(multipliers.begin(), multipliers.end());
    std::string result = sets[0];

    for (std::size_t i = 1; i < sets.size(); ++i)
    {
        result = formula(result, sets[i], multipliers[i]);
    }

    return result;
}

void ConcatenateDecimals(std::int64_t* arr, int size)
{
    auto formula = [](std::int64_t a, std::int64_t b) -> std::int64_t
    {
        return (a * CalcPowers(b)) + b;
    };

    std::int64_t val = arr[0];

    for (int i = 1; i < size; ++i)
    {
        val = formula(val, arr[i]);
    }

    std::cout<<val;
}

int main()
{
    std::string decimal = "64497387062899840145";
    //6449738706289984014 = 0101100110000010000100110010111001100010100000001000001000001110

    /*
    std::int64_t arr[] = {644, 9738, 7062, 8998, 4014};
    ConcatenateDecimals(arr, 5);*/

    std::cout<<ToBinary(decimal);

    return 0;
}

- Brandon

Answer 4

我发现了解决竞技编程任务的旧代码：

ai -> aj

2 <= i,j <= 36; 0 <= a <= 10^1000

时间限制：1秒

在最坏情况下，执行时间约为0.039秒。由于使用10^9作为计数系统，乘法、加法和除法算法非常快，但是实现可以进行很好的优化。 源链接

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
#define sz(x) (int((x).size()))
typedef vector<int> vi;
typedef long long llong;
 
int DigToNumber(char c) {
   if( c <= '9' && c >= '0' )
      return c-'0';
   return c-'A'+10;
}

char NumberToDig(int n) {
   if( n < 10 )
      return '0'+n;
   return n-10+'A';
}
 
const int base = 1000*1000*1000;
 
void mulint(vi& a, int b) { //a*= b
   for(int i = 0, carry = 0; i < sz(a) || carry; i++) {
      if( i == sz(a) )
         a.push_back(0);
      llong cur = carry + a[i] * 1LL * b;
      a[i] = int(cur%base);
      carry = int(cur/base);
   }
   while( sz(a) > 1 && a.back() == 0 )
      a.pop_back();
}

int divint(vi& a, int d) { // carry = a%d; a /= d; return carry;
   int carry = 0;
   for(int i = sz(a)-1; i >= 0; i--) {
      llong cur = a[i] + carry * 1LL * base;
      a[i] = int(cur/d);
      carry = int(cur%d);
   }
   while( sz(a) > 1 && a.back() == 0 )
      a.pop_back();
   return carry;
}

void add(vi& a, vi& b) { // a += b
   for(int i = 0, c = 0, l = max(sz(a),sz(b)); i < l || c; i++) {
      if( i == sz(a) )
         a.push_back(0);
      a[i] += ((i<sz(b))?b[i]:0) + c;
      c = a[i] >= base;
      if( c ) a[i] -= base;
   }
}
 
int main() {
 
   ios_base::sync_with_stdio(0);
   cin.tie(0);
 
   int from, to; cin >> from >> to;
   string s; cin >> s;
   vi res(1,0); vi m(1,1); vi tmp;
   for(int i = sz(s)-1; i >= 0; i--) {
      tmp.assign(m.begin(), m.end());
      mulint(tmp,DigToNumber(s[i]));
      add(res,tmp); mulint(m,from);
   }
   vi ans;
   while( sz(res) > 1 || res.back() != 0 )
      ans.push_back(divint(res,to));
   if( sz(ans) == 0 )
      ans.push_back(0);
   for(int i = sz(ans)-1; i >= 0; i--)
      cout << NumberToDig(ans[i]);
   cout << "\n";
   
   return 0;
}

如何将字符串s从“from”转换为“to”：

1. 使用公式s[i]*from^(|s|-i-1)，其中i = |s|-1..0，将大数字（vector “res”）累加到“res”中
2. 通过将“res”除以“to”，直到res> 0，并将它们保存到另一个向量中来计算数字
3. 逐个按数字发送到输出（您可以使用ostringstream代替）

PS我注意到线程发起者的昵称是Denis。 我认为这link也可能有用。

- Ralor