如何以 2³² 为基数表示数字？

如果我有一些基数 10 或基数 16，如何将其更改为基数 2³²？

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

它会与整数（以 10 为基数）相同，直到 2³² 吗？之后会发生什么？

您正在尝试查找以下形式

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

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

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

一个简单的方法是首先在你的数字系统中实现两个函数，乘法和加法。（即实现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);
}

免责声明：此方法在计算上不高效，但它至少可以让您入门。

注意：从 16 为基数进行转换要简单得多，因为 2³² 是 16 的精确倍数。因此，转换基本上归结为连接位。

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

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

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

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

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

我

刚刚把它写在了我的头顶上，我敢打赌有更有效的基本转换方案。

如果我有一些以 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中减去该幂的倍数，然后重复差值。

但是，您确定您问了正确的问题吗？

我怀疑你的意思是问一个不同的问题。我怀疑你的意思是问：如何将以 10 为数的数字解析为我的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。

Base 16

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

基数 10 更难。正如您所说，如果它小于 2³²，那么您只需将该值作为单个以 2 为³² 的"数字"。否则，我能想到的最简单的方法是使用长除法算法将基数 10 的值反复除以 2³²;在每个阶段，其余部分是下一个以 2 为基数的³²"数字"。也许比我更了解数论的人可以提供更好的解决方案。

我认为这是完全合理的做法。

您正在做的是在 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
  }
}

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

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

但这足以让你开始。

相关内容

最新更新

热门标签：