如何正确添加/减去 128 位数字(作为两个 uint64_t)?
我正在使用 C 语言,需要对 64 位数字和 128 位数字进行加法和减法。结果将保存在 128 位数字中。我使用整数数组来存储 128 位数字的上半部分和下半部分(即 uint64_t bigNum[2]
,其中 bigNum[0]
是最低有效位)。
任何人都可以帮助实现一个加法和减法函数,该函数可以接受 bigNum 并向其添加/减去一个 uint64_t 吗?
我在网上看到了很多不正确的例子,所以考虑一下:
bigNum[0] = 0;
bigNum[1] = 1;
subtract(&bigNum, 1);
此时 bigNum[0]
应该设置所有位,而 bigNum[1]
应该没有位放。
I'm working in C and need to add and subtract a 64-bit number and a 128-bit number. The result will be held in the 128-bit number. I am using an integer array to store the upper and lower halves of the 128-bit number (i.e. uint64_t bigNum[2]
, where bigNum[0]
is the least significant).
Can anybody help with an addition and subtraction function that can take in bigNum and add/subtract a uint64_t
to it?
I have seen many incorrect examples on the web, so consider this:
bigNum[0] = 0;
bigNum[1] = 1;
subtract(&bigNum, 1);
At this point bigNum[0]
should have all bits set, while bigNum[1]
should have no bits set.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(5)
在许多架构中,添加/减去任意长度的整数非常容易,因为有一个 进位标志和add/sub-with-flag指令。例如,在 x86 上,
rdx:rax += r8:r9
可以像这样完成。在 C 中,无法访问此进位标志,因此您必须自己计算该标志。最简单的方法是检查无符号总和是否小于任一操作数 像这样。例如,要做
a += b
,我们会这样做这就是确切在没有标志注册。例如,在 MIPS 中,它是这样完成的
这里有一些示例程序集输出
In many architectures it's very easy to add/subtract any arbitrarily-long integers because there's a carry flag and add/sub-with-flag instruction. For example on x86
rdx:rax += r8:r9
can be done like thisIn C there's no way to access this carry flag so you must calculate the flag on your own. The easiest way is to check if the unsigned sum is less than either of the operand like this. For example to do
a += b
we'll doThis is exactly how multi-word add is done in architectures that don't have a flag register. For example in MIPS it's done like this
Here's some example assembly output
在一年级或二年级,你应该已经学会了如何将 1 和 10 的加法分解为多个部分,将其分解为多个单独的十和个位的加法。当处理大数时,可以应用相同的原理来计算任意大数的算术运算,通过意识到你的单位现在是 2^bits 的单位,你的“十”大 2^bits 等等。
In grade 1 or 2, you should have learn't how to break down the addition of 1 and 10 into parts, by splitting it into multiple separate additions of tens and units. When dealing with big numbers, the same principals can be applied to compute arithmetic operations on arbitrarily large numbers, by realizing your units are now units of 2^bits, your "tens" are 2^bits larger and so on.
这应该适用于减法:
加法非常相似。当然,上面的内容也可以通过显式测试来表达,但我发现始终进行借用会更干净。优化留作练习。
对于等于
{ 0, 1 }
的bigNum
,减去 2 将使其等于{ ~0UL, ~0UL }
,这是正确的位模式来表示-1。这里,假设 UL 将整数提升为 64 位,这当然取决于编译器。This should work for the subtraction:
Addition is very similar. The above could of course be expressed with an explicit test, too, but I find it cleaner to always do the borrowing. Optimization left as an exercise.
For a
bigNum
equal to{ 0, 1 }
, subtracting two would make it equal{ ~0UL, ~0UL }
, which is the proper bit pattern to represent -1. Here, UL is assumed to promote an integer to 64 bits, which is compiler-dependent of course.如果您要减去的值小于或等于
bignum[0]
,则无需触摸bignum[1]
。如果不是,无论如何,您都需要从
bignum[0]
中减去它。此操作将环绕,但这是您此处需要的行为。此外,您还必须从bignum[1]
中减去 1。For the case the value that your are subtracting is less or equal to
bignum[0]
you don't have to touchbignum[1]
.If it isn't, you subtract it from
bignum[0]
, anyhow. This operation will wrap around, but this is the behavior you need here. In addition you'd then have to substact 1 frombignum[1]
.大多数编译器本质上支持 __int128 类型。
尝试一下,你可能会很幸运。
Most compilers support a __int128 type intrinsically.
Try it and you might be lucky.