如何用32位二进制表示一个数字？

Question

如果我有一些十进制或十六进制的数字，如何将它转换成2³²进制？ 我之所以要这样做，是为了实现BigInt，正如其他成员在这里建议的那样为什么要使用更高的基数来实现BigInt？ 它会与整数（十进制）相同，直到2³²吗？之后会发生什么？

- questions

---

不，你不需要。我认为你不理解什么是N进制数系统，否则你就不会要求使用2^32进制。 - Ed S.

你是之前询问大整数（BigIntegers）的人吗？如果是，base 2^32 应该意味着你的设计中的主要单位是32位整数。你可以将一个 base 2^32 的整数表示为每个数字都是一个32位整数，实际上是创建一个整数链表。 - Spidey

"Base N" 的意思是，一个数字由一系列小于 N 的数字表示。因此，“base 2^32” 是有意义的：它表示大数字由一系列 32 位的数字表示。 - Mike Seymour

@EdS.：您所描述的是一个基于2^32的系统。OP希望将一个十进制表示转换为形如a0 + a1*(2^32) + a2*(2^32)^2 + ...的东西，因此他需要一个从十进制到基于2^32的转换器。我们恰好称之为“大整数”数据类型，但这并不否定OP的问题。 - Oliver Charlesworth

@EdS.：确实，32位值的组合用于表示数值范围大于32位值的数就是大数的2^32进制表示法，并且这正是原帖作者想要的。你为什么说这不是2^32进制表示法？ - Mike Seymour

Answer 1

你正在尝试找到一些形式为

的内容。

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

这恰好是一个2的32次方进制系统的定义，所以忽略所有告诉你问题没有意义的人！

无论如何，您所描述的被称为进制转换。有快速的方法和简单的方法来解决此问题。快速的方法非常复杂（整本书都有专门章节介绍此主题），我不打算在此处尝试解决它们（至少因为我从未尝试使用过它们）。

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

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

也可以写成：

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

所以如果您在输入字符串中从左到右移动，您可以一次取下一个十进制数字，并使用您的 add 和 mul 函数累加到您的 BigInt 中：

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

免责声明：这种方法在计算效率上并不高，但至少可以让你开始。

注意：从十六进制转换更加简单，因为2的32次方恰好是16的倍数。因此，转换基本上就是将位串连接起来。

- Oliver Charlesworth

---

+1 的反对票很奇怪。那些没有回答问题的答案却得到了很多赞同！但似乎这个问题容易被误解，这也是为什么好的答案会被负评的原因吧。 - David Heffernan

@OliverCharlesworth，你能给些建议如何更高效地进行转换吗？因为我尝试了这种方法，但速度太慢了（抱歉打扰了）。 - Akiiino

@Akiiino - 正如我在原始答案中暗示的那样，确实存在更有效的方法，但我只知道它们的存在，不知道具体细节！ - Oliver Charlesworth

Answer 2

假设我们正在讨论一个十进制数：

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

每个 a[i] 都是介于0到9之间的数字。

我假设您可以解析作为输入值的字符串并查找数组 a[]。一旦您能做到这一点，并假设您已经实现了具有 + 和 * 运算符的 BigInt 类，则您就完成了。您只需使用您的 BigInt 类的实例评估上述表达式即可。

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

我刚刚从头脑中写下了这些内容，我敢打赌，还有更加高效的进制转换方案。

- David Heffernan

Answer 3

如果我有一些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中减去该幂次方的倍数，并使用差异重复该过程。

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

我怀疑您想问一个不同的问题。我怀疑您想问：如何将一个十进制数解析为我的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语言的任务。

- jason

---

当n无法适应寄存器时，如何执行log(n)？！ - David Heffernan

@joeframbach 鸡，见到蛋；蛋，见到鸡。 - David Heffernan

+1 是因为你是目前唯一一个理解 OP 为什么提出这个问题的回答。然而，-1 是因为你并没有真正解决问题，所以最终得分为 0。 - Oliver Charlesworth

@David Heffernan：我的回答中没有代码。实际上，实现此解决方案不依赖于您所说的任何内容。这里不存在先有鸡还是先有蛋的问题。实现你的BigInteger类。我对你使用的表示方法持中立态度。在这个类上实现*和+。现在你想解析12312398712309417234123412312037。那么，只需这样做：BigInteger b = new BigInteger(0); foreach(char c in s) { b = b * 10 + (int)(c - '0'); } return b;。就像我在回答中说的那样：“但是，你确定你问对了问题吗？” - jason

你在评论中描述的算法与我的答案和Oli的一样。但是，在你的答案中，你没有这么说。相反，你建议从 k = floor(log(n) / (32 * log(2))) 开始，但我不知道 n 从哪里来，也不知道如何对大整数取对数。 - David Heffernan

Answer 4

十六进制很容易，因为2的32次方等于16的8次方，是一个精确的幂。所以，从最低有效数字开始，每次读取8个十六进制数字，将这些数字转换为32位值，那就是下一个基于2的32次方的“数字”。

十进制更加困难。正如你所说，如果它小于2的32次方，那么你只需将该值作为单个基于2的32次方的“数字”即可。否则，我能想到的最简单的方法是使用长除法算法来反复将十进制值除以2的32次方；在每个阶段，余数就是下一个基于2的32次方的“数字”。也许比我更懂数论的人可以提供更好的解决方案。

- Mike Seymour

Answer 5

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

你正在使用32位整数数组表示一个非常大的数字（比如加密密钥）。

基于16进制表示是基于2的4次方，或者每次4位一组。如果你收到了一串基于16进制的“数字”，填充第一个整数的低4位，然后是下一个更低的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 结尾，并跟踪您的数组中整数的数量。

还需要一些从十进制转换的工作。

但这已足以让您开始了。

- Marlin Pierce