1

我是一名学习 C++ 的初学者（自学）程序员，最近我决定实现一个二进制编码的十进制 (BCD) 类作为练习，因此我可以在Project Euler上处理非常大的数字。我想尽可能地从头开始正确地做这件事。

我开始使用一个整数数组，其中输入数字的每个数字都保存为一个单独的整数。我知道每个 BCD 数字只能用 4 位编码，所以我认为为此使用整个 int 有点矫枉过正。我现在正在使用一组 bitset<4>。

  1. 是否也在使用像这样的库类？
  2. 你会认为这是作弊吗？
  3. 有一个更好的方法吗？

编辑：这样做的主要原因是作为一个练习——我不想使用像 GMP 这样的库，因为重点是我自己来上课。有没有办法确保每个十进制数字只使用 4 位？

4

6 回答 6

4

请注意，使用 's 数组bitset<4>将需要与 long 数组相同的空间量。bitset 通常是通过将字大小的整数数组作为位的后备存储来实现的，因此按位操作可以使用按位字操作，而不是字节操作，因此一次可以完成更多操作。

另外，我质疑你的动机。在系统之间发送数字时，BCD 通常用作数字字符串的打包表示。通常与算术没有任何关系。你真正想要的是一个任意大小的整数算术库，比如GMP。

于 2009-01-16T14:41:04.810 回答
1

是否也在使用像这样的库类？

我会将它与一系列整数进行基准测试，看看哪个整数表现更好。如果 bitset<4> 数组更快，那么不，这不是矫枉过正。每一点都有助于解决一些 PE 问题

你会认为这是作弊吗？

一点都不。

有一个更好的方法吗？

就像 Greg Rogers 建议的那样，任意精度库可能是更好的选择，除非您只是想从自己的滚动中学习。从这两种方法中都可以学到一些东西（使用库与编写库）。我很懒，所以我通常使用 Python。

于 2009-01-16T14:44:22.400 回答
1

就像 Greg Rogers 所说，使用 bitset 可能不会为 int 节省任何空间，也不会真正提供任何其他好处。我可能会改用向量。它是需要的两倍大，但您可以更简单、更快地为每个数字建立索引。

如果你想使用打包的 BCD，你可以编写一个自定义索引函数并在每个字节中存储两个数字。

于 2009-01-16T17:24:50.343 回答
1
  1. 是否也在使用像这样的库类？
  2. 你会认为这是作弊吗？
  3. 有一个更好的方法吗？

1&2：不是真的

3：每个字节有 8 位，您可以在每个无符号字符中存储 2 个 BCD。

于 2009-01-16T19:55:39.277 回答
0

一般来说，位运算是在整数的上下文中应用的，因此从性能方面来看，没有真正的理由去使用位。

如果您想通过bit方法获得经验，那么这可能会有所帮助

#include <stdio.h>
int main
(
    void
)
{
    typedef struct
    {
        unsigned int value:4;

    } Nibble;

    Nibble nibble;

    for (nibble.value = 0; nibble.value < 20; nibble.value++)
    {
        printf("nibble.value is %d\n", nibble.value);
    }

    return 0;
}

问题的要点是，在该struct内部，您正在创建一个短整数，即 4 位宽。实际上，它仍然是一个整数，但对于您的预期用途，它看起来和行为就像一个 4 位整数。

for循环清楚地表明了这一点，它实际上是一个无限循环。当半字节值达到 16 时，该值实际上为零，因为只有 4 位可以使用。结果nibble.value < 20永远不会变为真。

如果您查看 K&R 白皮书，其中一个注释是这样的位操作不可移植，因此如果您想将程序移植到另一个平台，它可能会或可能不会工作。

玩得开心。

于 2009-01-27T21:54:10.497 回答
0

您正在尝试获取 base-10 表示（即数组的每个单元格中的十进制数字）。这样，空间（每个数字一个 int）或时间（每个 dgit 4 位，但存在打包/解包的开销）都被浪费了。

例如，为什么不尝试使用 base-256 并使用字节数组？甚至是带有整数数组的base-2 ^ 32？这些操作的实现方式与 base-10 相同。唯一不同的是将数字转换为人类可读的字符串。

它可能是这样工作的：假设 base-256，每个“数字”有 256 个可能的值，所以数字 0-255 都是单个数字值。比 256 写成 1:0 （我将使用冒号分隔“数字”，我们不能使用 base-16 中的字母），base-10 中的类比是 9 之后有 10。同样 1030（base -10) = 4 * 256 + 6 = 4:6 (base-256)。1020 (base-10) = 3 * 256 + 252 = 3:252 (base-256) 也是 base-256 中的两位数。

现在让我们假设我们把数字放在字节数组中，首先是最低有效位：

unsigned short digits1[] = { 212, 121 }; // 121 * 256 + 212 = 31188
int len1 = 2;
unsigned short digits2[] = { 202, 20  }; // 20 * 256 + 202 = 5322
int len2 = 2;

然后添加将像这样（警告：前面的记事本代码，可能会被破坏）：

unsigned short resultdigits[enough length] = { 0 };
int len = len1 > len2 ? len1 : len2; // max of the lengths
int carry = 0;
int i;
for (i = 0; i < len; i++) {
    int leftdigit = i < len1 ? digits1[i] : 0;
    int rightdigit = i < len2 ? digits2[i] : 0;
    int sum = leftdigit + rightdigit + carry;
    if (sum > 255) {
        carry = 1;
        sum -= 256;
    } else {
        carry = 0;
    }
    resultdigits[i] = sum;
}
if (carry > 0) {
    resultdigits[i] = carry;
}

在第一次迭代中，它应该是这样的：

  1. 总和 = 212 + 202 + 0 = 414
  2. 414 > 256，所以进位 = 1 和 = 414 - 256 = 158
  3. 结果数字[0] = 158

在第二次迭代中：

  1. 总和 = 121 + 20 + 1 = 142
  2. 142 < 256，所以进位 = 0
  3. 结果数字[1] = 142

所以最终结果digits[] = { 158, 142 }，即142：158（base-256）= 142 * 256 + 158 = 36510（base-10），正好是31188 + 5322

请注意，将此数字转换为人类可读的形式绝非易事——它需要乘以 10 或 256，如果没有适当的研究，我无法将代码作为示例提供。优点是可以使“加法”、“减法”和“乘法”操作非常有效，并且在开始时和计算结束后只进行一次与 base-10 的大量转换。

说了这么多，就个人而言，我会在字节数组中使用以 10 为底的值，而不关心内存丢失。这需要将上面的常数 255 和 256 分别调整为 9 和 10。

于 2009-02-11T12:03:40.107 回答