当前位置：文江博客话题详情

math c++ 128-bit

在 C++ 中表示 128 位数字

发布于 2024-07-29 08:58:47 字数 232 浏览 13 评论 0 原文

在 C++ 中表示 128 位数字的最佳方式是什么？它的行为应该尽可能接近内置数字类型（即支持所有算术运算符等）。

我正在考虑构建一个具有 2 个 64 位或 4 个 32 位数字的类。或者可能只是创建一个 128 位内存块并自己完成所有事情。

是否有一些更简单/更标准的方法，或者我自己实现时不太可能搞砸的方法？ :)

如果可以扩展到 256 位、512 位等，那就太好了……

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

心作怪 2024-08-05 08:58:47

编辑：当我第一次写这个boost::multi precision::uint128_t 还没有出现。由于历史原因保留这个答案。

我之前做过一个uint128类，你可以在以下位置查看： http://www.codef00 .com/code/uint128.h。

它依赖于 boost 自动提供数学运算符的所有变体，因此它应该支持本机 unsigned int 类型所做的一切。

内置类型有一些小的扩展，例如使用如下字符串初始化它：

uint128_t x("12345678901234567890");

有一个方便的宏，其工作方式与 C99 中的宏类似，您可以像这样使用：

uint128_t x = U128_C(12345678901234567890);

EDIT: when I first wrote this boost::multiprecision::uint128_t wasn't a thing yet. Keeping this answer for historical reasons.

I've made a uint128 class before, you can check it out at: http://www.codef00.com/code/uint128.h.

It is dependent on boost for automatically providing all of the variants of the math operators, so it should support everything a native unsigned int type does.

There are some minor extensions to built in types such as initializing it with a string like this:

uint128_t x("12345678901234567890");

There is a convenience macro which works similary to the ones in C99 which you can use like this:

uint128_t x = U128_C(12345678901234567890);

回复收藏 0 原文

孤千羽 2024-08-05 08:58:47

这是一种特殊情况，特别是因为您没有指定您要寻找的平台，但是使用 GCC，您可以使用所谓的模式（TI）来获取（合成的）128 位操作，例如实例：

   typedef unsigned int uint128_t __attribute__((mode(TI)));

   uint64_t x = 0xABCDEF01234568;
   uint64_t y = ~x;

   uint128_t result = ((uint128_t) x * y);

   printf("%016llX * %016llX -> ", x, y);

   uint64_t r1 = (result >> 64);
   uint64_t r2 = result;

   printf("%016llX %016llX\n", r1, r2);

不过，这只适用于 64 位处理器。

不管怎样，您正在寻找多精度算术来解决这个问题。 mode(TI) 将导致编译器为您生成操作，否则必须显式编写它们。

可以使用通用的bigint包；我所知道的 C++ 包括数论包 LiDIA 和 < a href="http://www.shoup.net/ntl/" rel="noreferrer">NTL，以及 Crypto++ 和 Botan）。当然还有 GnuMP，它是规范的 C MPI 库（它也有一个 C++ 包装器，尽管我上次查看时似乎记录得很差）。所有这些都设计得很快，但也可能针对更大（1000 位以上）的数字进行调整，因此在 128 位时，您可能会处理大量开销。（另一方面，你没有说这是否重要）。所有这些（与 bigint-cpp 包不同，它是 GPL，不是 BSD 就是 LGPL） - 不确定它是否重要 - 但它可能很重要。

您还可以编写自定义 uint128_t 类型；通常，这样的类将实现与常规 MPI 类几乎相同的算法，只是硬编码为只有 2 或 4 个元素。如果您好奇如何实现此类算法，一个很好的参考是第 14 章。

当然，如果您实际上不需要所有算术运算（特别是除法和取模，相当棘手），那么手动执行此操作会更容易例如，如果您只需要跟踪一个假设可能溢出 64 位的计数器，您可以将其表示为一对 64 位长整型并手动进行进位：

unsigned long long ctrs[2] = { 0 };

void increment() {
   ++ctrs[0];
   if(!ctrs[0]) // overflow
     ++ctrs[1];
}

这当然会简单得多比一般 MPI 包或自定义 uint128_t 类处理。

This is somewhat of a special case, especially since you didn't specify what platform(s) you're looking for, but with GCC you can use what is called mode(TI) to get (synthesized) 128-bit operations, for instance:

   typedef unsigned int uint128_t __attribute__((mode(TI)));

   uint64_t x = 0xABCDEF01234568;
   uint64_t y = ~x;

   uint128_t result = ((uint128_t) x * y);

   printf("%016llX * %016llX -> ", x, y);

   uint64_t r1 = (result >> 64);
   uint64_t r2 = result;

   printf("%016llX %016llX\n", r1, r2);

This only works on 64-bit processors, though.

One way or another, you're looking at multiple precision arithmetic to solve this. mode(TI) will cause the compiler to generate the operations for you, otherwise they have to be written explicitly.

You can use a general bigint package; ones in C++ I know of include the number theory packages LiDIA and NTL, and the bigint packages used for cryptographic code in Crypto++ and Botan). Plus of course there is GnuMP, which is the canonical C MPI library (and it does have a C++ wrapper as well, though it seemed poorly documented last time I looked at it). All of these are designed to be fast, but are also probably tuned for larger (1000+ bit) numbers, so at 128 bits you may be dealing with a lot of overhead. (On the other hand you don't say if that matters or not). And all of them (unlike the bigint-cpp package, which is GPL, are either BSD or LGPL) - not sure if it matters - but it might matter a lot.

You could also write a custom uint128_t kind of type; typically such a class would implement much the same algorithms as a regular MPI class, just hardcoded to have only 2 or 4 elements. If you are curious how to implement such algorithms, a good reference is Chapter 14 of the Handbook of Applied Cryptography

Of course doing this by hand is easier if you don't actually need all the arithmetic operations (division and modulo, in particular, are rather tricky). For instance, if you just need to keep track of a counter which might hypothetically overflow 64 bits, you could just represented it as a pair of 64 bit long longs and do the carry by hand:

unsigned long long ctrs[2] = { 0 };

void increment() {
   ++ctrs[0];
   if(!ctrs[0]) // overflow
     ++ctrs[1];
}

Which of course is going to be a lot simpler to deal with than a general MPI package or a custom uint128_t class.

回复收藏 0 原文

醉生梦死 2024-08-05 08:58:47

Boost 的数据类型为 多精度 库，适用于 128 到 1024 位的类型。

#include <boost/multiprecision/cpp_int.hpp>

using namespace boost::multiprecision;

int128_t mySignedInt128 = -1;
uint128_t myUnsignedInt128 = 2;
int256_t mySignedInt256 = -3;
uint256_t myUnsignedInt256 = 4;
int512_t mySignedInt512 = -5;
uint512_t myUnsignedInt512 = 6;
int1024_t mySignedInt1024 = -7;
uint1024_t myUnsignedInt1024 = 8;

Boost has data types in multiprecision library for types ranging from 128 to 1024 bits.

#include <boost/multiprecision/cpp_int.hpp>

using namespace boost::multiprecision;

int128_t mySignedInt128 = -1;
uint128_t myUnsignedInt128 = 2;
int256_t mySignedInt256 = -3;
uint256_t myUnsignedInt256 = 4;
int512_t mySignedInt512 = -5;
uint512_t myUnsignedInt512 = 6;
int1024_t mySignedInt1024 = -7;
uint1024_t myUnsignedInt1024 = 8;

回复收藏 0 原文

无力看清 2024-08-05 08:58:47

GCC 支持支持 128 位整数类型的处理器。您可以使用以下方式访问它：

__int128          a;
unsigned __int128 b;

02020-02-10 更新：根据这个：GCC、Clang 和 Intel ICC 都支持内置的 __int128 类型。

GCC supports a 128-bit integer type for processors which support it. You can access it using:

__int128          a;
unsigned __int128 b;

02020-02-10 Update: according to this: GCC, Clang, and Intel ICC all support a built-in __int128 type.

回复收藏 0 原文

笑咖 2024-08-05 08:58:47

您可能想尝试 GMP

回复收藏 0 原文

衣神在巴黎 2024-08-05 08:58:47

这是我在谷歌上找到的一个图书馆。

http://sourceforge.net/projects/cpp-bigint/

回复收藏 0 原文

魂归处 2024-08-05 08:58:47

您可能会更好地使用无限精度的整数类，而不是大小不断增加的序列。有些语言（例如 Common Lisp 和 IIRC Python）本身就有它们。我暂时不确定 C++ 有什么可用的；最后我看了看没有 Boost 版本。

回复收藏 0 原文

漫雪独思 2024-08-05 08:58:47

cairo 图形库有两个实现可移植 128 位整数运算的文件：cairo-wideint-private.h、cairo-wideint.c。我们在项目中仅包含这两个以获得 128 位。

回复收藏 0 原文

攀登最高峰 2024-08-05 08:58:47

在 Visual Studio C++ 中，有一个类型 FLOAT128 用于表示 128 位整数。它的实现方式是：

#if defined(_M_IA64) && !defined(MIDL_PASS)
__declspec(align(16))
#endif
typedef struct _FLOAT128 {
    __int64 LowPart;
    __int64 HighPart;
} FLOAT128;

所以我不确定为其实现了哪些数学运算

In Visual Studio C++ there is a type FLOAT128 that is used to represent 128-bit integers. It is implemented as:

#if defined(_M_IA64) && !defined(MIDL_PASS)
__declspec(align(16))
#endif
typedef struct _FLOAT128 {
    __int64 LowPart;
    __int64 HighPart;
} FLOAT128;

so I'm not sure about what math operations are implemented for it

回复收藏 0 原文

~没有更多了~

关于作者

无畏

暂无简介

0 文章

0 评论

23 人气

关注发私信

友情链接

文江博客

在 C++ 中表示 128 位数字

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（9）

关于作者

相关话题

热门标签

推荐作者

1CH1MKgiKxn9p

ゞ记忆︶ㄣ

JackDx

信远

yaoduoduo1995

霞映澄塘

友情链接

在 C++ 中表示 128 位数字

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（9）

关于作者

相关话题

热门标签

推荐作者

1CH1MKgiKxn9p

ゞ记忆︶ㄣ

JackDx

信远

yaoduoduo1995

霞映澄塘

友情链接

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。