7

如果我有一些以 10 为基数或以 16 为基数的数字，如何将其更改为以 2 32为基数？

我尝试这样做的原因是为了按照此处其他成员的建议实施 BigInt为什么要使用更高的基础来实施 BigInt？

它是否与整数（以 10 为底）相同，直到 2 32？之后会发生什么？

4

5 回答 5

12

你正试图找到某种形式的东西

a0 + a1 * (2^32) + a2 * (2^32)^2 + a3 * (2^32)^3 + ...

这正是base-2 32系统的定义，所以请忽略所有告诉您您的问题没有意义的人！

无论如何，您所描述的内容称为基本转换。有快速的方法，也有简单的方法来解决这个问题。快速方法非常复杂（有专门针对该主题的书籍的整章），我不打算在这里尝试解决它们（尤其是因为我从未尝试过使用它们）。

一种简单的方法是首先在数字系统中实现两个函数，乘法和加法。（即实施BigInt add(BigInt a, BigInt b)和BigInt mul(BigInt a, BigInt b)）。一旦你解决了这个问题，你会注意到一个以 10 为底的数字可以表示为：

b0 + b1 * 10 + b2 * 10^2 + b3 * 10^3 + ...

也可以写成：

b0 + 10 * (b1 + 10 * (b2 + 10 * (b3 + ...

因此，如果您在输入字符串中从左到右移动，您可以一次剥离一个以 10 为基数的数字，并使用您的add和mul函数累积到您的BigInt：

BigInt a = 0;
for each digit b {
    a = add(mul(a, 10), b);
}

免责声明：此方法计算效率不高，但至少可以帮助您入门。

注意：从 base-16 转换要简单得多，因为 2 32是 16 的精确倍数。所以转换基本上归结为连接位。

于 2012-04-16T19:58:47.467 回答
5

假设我们正在谈论一个以 10 为底的数字：

a[0]*10^0 + a[1]*10^1 + a[2]*10^2 + a[3]*10^3 + ... + a[N]*10^N

其中 eacha[i]是 0 到 9（含）范围内的一个数字。

我将假设您可以解析作为输入值的字符串并找到数组a[]。一旦你能做到这一点，并假设你已经用and运算符实现了你的BigInt类，那么你就回家了。您可以使用您的类的实例简单地评估上面的表达式。+*BigInt

您可以使用Horner 方法相对有效地评估此表达式。

我刚刚把这个写下来，我敢打赌，有更有效的基本转换方案。

于 2012-04-16T19:58:15.970 回答
4

如果我有一些以 10 为底或以 16 为底的数字，如何将其更改为以 2^32 为底的数字？

就像您将其转换为任何其他基础一样。您想将数字写n为

n = a_0 + a_1 * 2^32 + a_2 * 2^64 + a_3 * 2^96 + ... + a_k * 2^(32 * k).

因此，找到 2^32 的最大幂，除以n，从 中减去该幂的倍数n，然后用差值重复。

但是，你确定你问对了问题吗？

我怀疑你的意思是问一个不同的问题。我怀疑您的意思是要问：如何将 base-10 数字解析为 my 的实例BigInteger？这很容易。编写您的实现代码，并确保您已实现+和*. 我完全不知道您实际上如何在内部表示整数，但如果您想使用基数 2^32，那么可以。然后：

 BigInteger Parse(string s) {
      BigInteger b = new BigInteger(0);
      foreach(char c in s) { b = b * 10 + (int)c - (int)'0'; }
      return b;
 }

我会留给你把它翻译成C。

于 2012-04-16T19:43:23.970 回答
1

以 16 为底很容易，因为 2 32是 16 8，一个精确的幂。因此，从最低有效位开始，一次读取 8 个 base-16 数字，将这些数字转换为 32 位值，即下一个 base-2 32 “数字”。

Base 10 更难。正如您所说，如果它小于 2 32，那么您只需将该值作为单个 base-2 32 “数字”。否则，我能想到的最简单的方法是使用长除法算法将基数为 10 的值除以 2 32；在每个阶段，余数是下一个以 2 为底的32 “数字”。也许比我了解更多数论的人可以提供更好的解决方案。

于 2012-04-16T20:04:29.120 回答
0

我认为这是一件完全合理的事情。

您正在做的是在 32 位整数数组中表示一个非常大的数字（如加密密钥）。

以 16 为基数的表示是以 2^4 为基数的，或者一次是一系列 4 位。如果您正在接收以 16 个“数字”为基数的流，请填写数组中第一个整数的低 4 位，然后是下一个最低位，直到您读取 8 个“数字”。然后转到数组中的下一个元素。

long getBase16()
{
  char cCurr;

  switch (cCurr = getchar())
  {
  case 'A':
  case 'a':
    return 10;
  case 'B':
  case 'b':
    return 11;
  ...
  default:
    return cCurr - '0';
  }
}

void read_input(long * plBuffer)
{
  long * plDst = plBuffer;
  int iPos = 32;

  *(++plDst) = 0x00;

  long lDigit;
  while (lDigit = getBase16())
  {
     if (!iPos)
     {
       *(++plDst) = 0x00;
       iPos = 32;
     }

     *plDst >> 4;
     iPos -= 4;
     *plDst |= (lDigit & 0x0F) << 28
  }
}

有一些修复要做，比如通过将 *plDst 移动 iPos 来结束，并跟踪数组中的整数数量。

还有一些工作要从基数 10 转换。

但这足以让您入门。

于 2012-04-16T20:20:02.657 回答