我有一台只支持32位操作的机器,long long在这台机器上无法使用。
我有一个64位的量,表示为两个无符号int 32。
问题是如何对这个64位的量使用32位除数进行模运算。
r = a mod b
其中: a是64位值,b是32位值
我想通过以下方式表示模部分: a = a1 * (2 ^ 32) + a2(其中a1是顶部位,a2是底部位)
(a1 * (2 ^ 32) + a2) mod b = ((a1 * 2 ^ 32) mod b + a2 mod b) mod b
((a1 * 2 ^ 32) mod b + a2 mod b) mod b = (a1 mod b * 2 ^ 32 mod b + a2 mod b) mod b
但问题在于2 ^ 32 mod b有时可能等于2 ^ 32,因此乘法将会溢出。我尝试将乘法转换为加法,但这也需要我使用2 ^ 32,如果我进行模运算,将再次得到2 ^ 32 :) 因此,我不确定如何对一个64位值执行无符号模运算和32位值。
我想解决这个问题的简单方法是执行以下操作:
1. a / b = c 2. a = a - floor(c) * b 3. 执行1直到c等于0,并使用a作为答案。
但我不确定如何将这两个整数组合在一起形成64位值。
为了完整起见,这里有一些二进制除法和减法的链接: http://www.exploringbinary.com/binary-division/ 以及二进制除法算法的描述: http://en.wikipedia.org/wiki/Division_algorithm
r = a mod b
其中: a是64位值,b是32位值
我想通过以下方式表示模部分: a = a1 * (2 ^ 32) + a2(其中a1是顶部位,a2是底部位)
(a1 * (2 ^ 32) + a2) mod b = ((a1 * 2 ^ 32) mod b + a2 mod b) mod b
((a1 * 2 ^ 32) mod b + a2 mod b) mod b = (a1 mod b * 2 ^ 32 mod b + a2 mod b) mod b
但问题在于2 ^ 32 mod b有时可能等于2 ^ 32,因此乘法将会溢出。我尝试将乘法转换为加法,但这也需要我使用2 ^ 32,如果我进行模运算,将再次得到2 ^ 32 :) 因此,我不确定如何对一个64位值执行无符号模运算和32位值。
我想解决这个问题的简单方法是执行以下操作:
1. a / b = c 2. a = a - floor(c) * b 3. 执行1直到c等于0,并使用a作为答案。
但我不确定如何将这两个整数组合在一起形成64位值。
为了完整起见,这里有一些二进制除法和减法的链接: http://www.exploringbinary.com/binary-division/ 以及二进制除法算法的描述: http://en.wikipedia.org/wiki/Division_algorithm
uint64_t a,b,r; r = a % b;
- Jonathon Reinhartb <= (2 ^ 32 - 1)
,所以(2 ^ 32 mod b) < (2 ^ 32)
。 - chux - Reinstate Monica2^32 mod b
" --> 是的,但诀窍是2^32 mod b
==(2^32 - b) mod b
。我们知道至少可以从2^32
中减去1个b而结果不会变成负数。使用一次位移循环,就可以完成所有需要的操作。" - chux - Reinstate Monica