问题 找出当前平台上最大的本机整数类型


我遇到的问题是创建一种大整数库。我想让它既跨平台又尽可能快。这意味着我应该尝试使用系统本机支持的大型数据类型进行数学运算。

我实际上并不想知道我是在编译32位还是64位系统;我需要的是根据可用的最大值创建64位或32位或任何位整数的方法。我会使用sizeof来表现不同,具体取决于它是什么。

以下是一些可能的解决方案及其问题:

使用sizeof(void *): 这给出了指向内存的指针的大小。有可能(尽管不太可能)系统可能具有更大的内存指针,而不是能够进行数学运算,反之亦然。

总是使用长: 虽然在几个平台上确实长整数是4个字节或8个字节,具体取决于体系结构(我的系统就是这样一个例子),但是一些编译器甚至在64位系统上实现了4个字节的长整数。

总是长时间使用: 在许多32位系统上,这是一个64位整数,可能效率不高(尽管可能比我编写的任何代码更有效)。这个问题的真正问题在于某些架构(例如为我的mp3播放器供电的架构)可能根本不支持它。

要强调的是,我的代码并不关心整数的实际大小一旦被选中(它依赖于sizeof()来处理大小重要的事情)。我只是想让它选择整数类型,这将导致我的代码最有效。


2596
2017-12-28 23:53


起源

我想到的第一件事就是以某种方式计算CPU寄存器的大小...... - BlackBear
你在现有的bignum图书馆中搜索过答案吗? sourceforge.net/projects/bignlibacbignum - mth
也许试图在其中移动一些内容然后添加一些内容并检查溢出标志 - BlackBear
在做这样一个有问题的任务之前,你看过GMP吗?因为它听起来像你正试图这样做。在性能方面,我怀疑你甚至可以接近GMP实施,因为它的性能是众所周知的。 - Milan
@Milan嗯,当你认为GMP有装配优化的bignums并且被认为是地球上最快的bignum图书馆之一时,你有一个公平的观点。但是,有时候这些事情只需要学习就可以了。


答案:


如果你真的想要一个原生大小的类型,我会用 size_tptrdiff_t, 要么 intptr_t 和 uintptr_t。在任何非病理系统中,这些都将是本机字大小。

另一方面,在简单性方面肯定有益于始终使用固定大小,在这种情况下我只会使用 int32_t 要么 uint32_t。我说它更简单的原因是你经常最终需要知道诸如“适合类型的10的最大功率”(用于十进制转换)和其他常量,这些常量在类型方面不能轻易表达为常量表达式你已经习惯了。如果您只选择固定数量的位,您还可以修复方便的常量(例如我的示例中为1000000000)。当然,通过这种方式,您可以在高端系统上牺牲一些性能。您可以采用相反的方法并使用更大的固定大小(64位),这在高端系统上是最佳的,并假设编译器在32位计算机上进行64位算术的代码至少与你的bignum代码处理2个32位字,在这种情况下它仍然是最佳的。


6
2017-12-29 02:54



谢谢,你答案的第一部分几乎就是我要找的东西。 - Collin
另一方面,我想我可能会使用GMP。 - Collin
警告: ptrdiff_t 保证足够大的指针减法,但没有人说它不能更大(虽然你不经常看到64位 ptrdiff_t 什么时候 size_t 是32位,即使这意味着跨越一半以上的地址空间的差异不能存储在a中 ptrdiff_t)。要小心你所依赖的标准。 - Mehrdad
我说非病态。当然,你可以在一个实现上故意制作类型荒谬的超大尺寸,但我认为没有人会选择使用这样的实现,除非他们别无选择。除了同一个对象之外的指针差异是未定义的行为,因此只要32位实现不允许大于2gb的单个对象,32位 ptrdiff_t 完全正确。 - R..
例外情况可能是16位嵌入式系统,其本机算术大小为16位,但是 size_t 可能是32位。或8位系统,其本机算术大小为8位,但是 int 仍然必须至少16位,并且 size_t 可能也是16位。 - Craig McQueen


最好的方法不是依赖于自动检测,而是针对特定的编译器 #if/#else 语句选择您已测试并知道最佳的类型。


4
2017-12-29 00:04



如果无法检测到编译器,可能会回退到uintptr_t。 - Charles


这里的 我们是怎么做到的 在 bsdnt

#if ULONG_MAX == 4294967295U

typedef uint32_t word_t;
typedef unsigned int dword_t __attribute__((mode(DI)));
#define WORD_BITS 32

#else

typedef uint64_t word_t;
typedef unsigned int dword_t __attribute__((mode(TI)));
#define WORD_BITS 64

#endif

如果有兴趣的话,发起该项目的人就写了一个 博客 写作bignum图书馆。

GMP / MPIR大大复杂化; gmp-h.in成为gmp.h post-configure,定义了这个:

#define GMP_LIMB_BITS                      @GMP_LIMB_BITS@

简而言之,长度被设置为构建过程的一部分,通过它来完成 config.guess (即autotools)。


0
2017-12-29 00:11



如果ULONG_MAX是2 ^ 48 - 1怎么办? - James K Polk
隐藏的gcc特定黑客.... - R..
@R确实。这确实是一项正在进行的工作。我建议你不要贪图 __attribute__ 在GMP来源然后......


使用int_fast32_t stdint.h 似乎是一种选择,尽管你受到决定者的摆布,对于“快速”意味着什么。


0
2017-12-29 00:46



如果32位访问没有惩罚,就像在x86_64上一样, int_fast32_t 应该是一个32位类型,但以64位为单位执行bignum算术肯定是更可取的... - R..
你可能是正确的,但在我的x86_64机器(Ubuntu 10.10)上,它是64位。我希望它与机器主数据寄存器的宽度相关,但我没有确切的证据。 - ergosys