C - 对数不是 2 的幂的模数按位运算的算法
C - Algorithm for Bitwise operation on Modulus for number of not a power of 2
我知道可以使用按位运算符计算 2 的模数
x % 2^n == x & (2^n - 1).
但我想知道是否存在任何通用的按位算法来找到任何数字的模数不是 2 的幂。例如，
7%5
提前谢谢你。
不，没有一种通用的方法可以在不实际进行除法的情况下找到除法余数。
二的幂是一个例外，因为二进制表示允许您使用移位除以二。与让您将十进制数除以 10 的幂的原理相同，只需将末尾的数字去掉即可。
显然，没有什么能阻止您编码 division using bit operations。您还需要编写减法代码，因为算法需要它作为 "primitive operation"。可以想象，这会非常慢。
有一对，针对特殊情况，包括5个。
因为 16 ≡ 1 (mod 5)，你可以做的一个技巧是将变量分成 4 位半字节，在 [=62 中查找每个半字节的 modulus =]，并将这些值相加得到原始数字的 modulus。
此程序使用位域、table 查找和加法。它也适用于 modulo 3 或 15，并且可以通过更大的查找扩展到更大的块 table。
#include <assert.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
typedef struct bitfield64_t {
uint64_t b0 : 4;
uint64_t b1 : 4;
uint64_t b2 : 4;
uint64_t b3 : 4;
uint64_t b4 : 4;
uint64_t b5 : 4;
uint64_t b6 : 4;
uint64_t b7 : 4;
uint64_t b8 : 4;
uint64_t b9 : 4;
uint64_t b10 : 4;
uint64_t b11 : 4;
uint64_t b12 : 4;
uint64_t b13 : 4;
uint64_t b14 : 4;
uint64_t b15 : 4;
} bitfield64_t;
typedef union pun64_t {
uint64_t u;
bitfield64_t b;
} pun64_t;
/* i%5 for i in [0,19]. The upper bound guarantees that nibble_mod5[a+b] is
* valid whenever a<16 and b<5.
*/
const unsigned nibble_mod5[20] = {
0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4
};
unsigned add_mod5( const unsigned a, const unsigned b )
/* Returns (a + b) % 5, where
* a < 16
* b < 5
*/
{
assert(a < 16);
assert(b < 5);
return nibble_mod5[a + b];
}
int main( const int argc, const char* argv[] )
{
int64_t n;
if ( argc != 2 ) {
fprintf( stderr,
"Call this program with an unsigned number as its argument.\n" );
return EXIT_FAILURE;
}
if ( 1 != sscanf( argv[1], "%lld", &n ) || n < 0 ) {
fprintf( stderr,
"The argument must be an unsigned number.\n" );
return EXIT_FAILURE;
}
const pun64_t p = { .u = (uint64_t)n };
const unsigned result =
add_mod5( p.b.b15,
add_mod5( p.b.b14,
add_mod5( p.b.b13,
add_mod5( p.b.b12,
add_mod5( p.b.b11,
add_mod5( p.b.b10,
add_mod5( p.b.b9,
add_mod5( p.b.b8,
add_mod5( p.b.b7,
add_mod5( p.b.b6,
add_mod5( p.b.b5,
add_mod5( p.b.b4,
add_mod5( p.b.b3,
add_mod5( p.b.b2,
add_mod5( p.b.b1,
nibble_mod5[p.b.b0] )))))))))))))));
printf( "%u\n", result );
assert( result == n % 5 );
return EXIT_SUCCESS;
}
为了找到一个 bignum 的 modulus，您可以利用 16 的任何次方都等于 1 modulo 5 的事实。因此，您的单词大小 w 是 2⁸、2ⁱ⁶、2³² 或 2⁶⁴，您可以将大数写为 a₀w⁰ + a₁w¹ + a₂w² + ... ≅ a₀1⁰ + a₁1¹ + a₂1² + ... ≡ a₀ + a₁ + a₂ + ...（mod 5）。这也是为什么任意数的小数位数之和与原数全等的原因 modulo 3 or 9: 10 ≡ 1 (mod 3).
这也适用于字节的 3、5、15 和 17，16 位字的因数 255 和 257，以及 32 位字的因数 65,535 和 65,537。如果您注意到该模式，那是因为 b²ⁿ = (bⁿ+1)(bⁿ-1) + 1，其中 b = 2 且 n = 2、4、8 或 16。
您可以将此方法的变体应用于任何 n，使您的块大小与 -1 (mod n) 一致：交替加法和减法。它起作用是因为 a₀w⁰ + a₁w¹ + a₂w² + ... ≡ a₀(-1)⁰ + a₁(-1)¹ + a₂(-1)² + ... ≡ a₀ - a₁ + a₂ - ... (mod n)，但用处不大，因为许多这样的 n 值都是梅森素数。这类似于通过从右到左对数字进行加、减、加和减，可以得到任何小数的 mod 11，例如144 ≅ 4 - 4 + 1 ≡ 1 (mod 11)。就像数字一样，你可以用五位块做同样的把戏，因为 32 和 10 一样，也等于 -1 modulo 11.
另一个有用的特殊情况发生在 w ≡ w² ≡ c (mod b) 时。然后你有 a₀w⁰ + a₁w¹ + a₂w² + ... ≡ a₀·1 + a₁c + a₂c + ... ≡ a₀ + c(a₁ + a₂ + ...) (mod b)。这类似于 10 ≡ 100 ≡ 1000 ≡ ... ≡ 4 (mod 6)，因此任何数字都等于其最后一位数字加上其剩余数字之和的四倍，modulo 6. 计算可以是每个字节的查找和加法，以及乘以一个小常数，您可以通过一两个位移位来完成。比如取mod 20，可以把除最低位以外的所有字节相加 mod 20，和乘以256 mod 20 = 16，也就是左移4、然后加上最后一个字节。这可能非常方便：不计算余数为 1 或 0 的数字，这适用于半字节 modulo 6、10 和 12，以及字节 modulo 这些值和 20、24、30 , 34, 40, 48, 60, 68, 80, 96, 102, 120, 136, 160, 170, 192, 204 和 240。
如果一个数可以表示为特殊情况的乘积，可以用中国剩余定理求解。比如77 = 11×7, 32 ≡ -1 mod 11, 8 ≡ 1 mod 7, 所以可以求出除以11和7的余数, 就是除以77的余数. 大多数小质数都属于前面讨论的一种特殊情况。
许多后来的 RISC 架构有硬件划分但没有 modulus，并告诉程序员通过计算 a-(a/b)*b 来计算 a%b。 ARM A64 是当今使用最多的一种。如果你也没有硬件划分，check out this answer. An example of another approach when the base is a small constant is given here，在CISC架构上被广泛使用
还有一种算法 written by Sean Anderson in 2001 but probably discovered earlier 可以通过小于 2 的幂的一个数来计算 modulus。它类似于我在上面使用的技术，但依赖于位移位和可以扩展到 (1<<s)-1 的任何因子。这几乎就是您要找的！
通常，您的优化编译器应该使用最有效的方法在您的硬件上实现 %。在您的示例中，任何体面的编译器只会折叠常量并将 7%5 优化为 2.
我知道可以使用按位运算符计算 2 的模数
x % 2^n == x & (2^n - 1).
但我想知道是否存在任何通用的按位算法来找到任何数字的模数不是 2 的幂。例如，
7%5
提前谢谢你。
不，没有一种通用的方法可以在不实际进行除法的情况下找到除法余数。
二的幂是一个例外，因为二进制表示允许您使用移位除以二。与让您将十进制数除以 10 的幂的原理相同，只需将末尾的数字去掉即可。
显然，没有什么能阻止您编码 division using bit operations。您还需要编写减法代码，因为算法需要它作为 "primitive operation"。可以想象，这会非常慢。
有一对，针对特殊情况，包括5个。
因为 16 ≡ 1 (mod 5)，你可以做的一个技巧是将变量分成 4 位半字节，在 [=62 中查找每个半字节的 modulus =]，并将这些值相加得到原始数字的 modulus。
此程序使用位域、table 查找和加法。它也适用于 modulo 3 或 15，并且可以通过更大的查找扩展到更大的块 table。
#include <assert.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
typedef struct bitfield64_t {
uint64_t b0 : 4;
uint64_t b1 : 4;
uint64_t b2 : 4;
uint64_t b3 : 4;
uint64_t b4 : 4;
uint64_t b5 : 4;
uint64_t b6 : 4;
uint64_t b7 : 4;
uint64_t b8 : 4;
uint64_t b9 : 4;
uint64_t b10 : 4;
uint64_t b11 : 4;
uint64_t b12 : 4;
uint64_t b13 : 4;
uint64_t b14 : 4;
uint64_t b15 : 4;
} bitfield64_t;
typedef union pun64_t {
uint64_t u;
bitfield64_t b;
} pun64_t;
/* i%5 for i in [0,19]. The upper bound guarantees that nibble_mod5[a+b] is
* valid whenever a<16 and b<5.
*/
const unsigned nibble_mod5[20] = {
0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4
};
unsigned add_mod5( const unsigned a, const unsigned b )
/* Returns (a + b) % 5, where
* a < 16
* b < 5
*/
{
assert(a < 16);
assert(b < 5);
return nibble_mod5[a + b];
}
int main( const int argc, const char* argv[] )
{
int64_t n;
if ( argc != 2 ) {
fprintf( stderr,
"Call this program with an unsigned number as its argument.\n" );
return EXIT_FAILURE;
}
if ( 1 != sscanf( argv[1], "%lld", &n ) || n < 0 ) {
fprintf( stderr,
"The argument must be an unsigned number.\n" );
return EXIT_FAILURE;
}
const pun64_t p = { .u = (uint64_t)n };
const unsigned result =
add_mod5( p.b.b15,
add_mod5( p.b.b14,
add_mod5( p.b.b13,
add_mod5( p.b.b12,
add_mod5( p.b.b11,
add_mod5( p.b.b10,
add_mod5( p.b.b9,
add_mod5( p.b.b8,
add_mod5( p.b.b7,
add_mod5( p.b.b6,
add_mod5( p.b.b5,
add_mod5( p.b.b4,
add_mod5( p.b.b3,
add_mod5( p.b.b2,
add_mod5( p.b.b1,
nibble_mod5[p.b.b0] )))))))))))))));
printf( "%u\n", result );
assert( result == n % 5 );
return EXIT_SUCCESS;
}
为了找到一个 bignum 的 modulus，您可以利用 16 的任何次方都等于 1 modulo 5 的事实。因此，您的单词大小 w 是 2⁸、2ⁱ⁶、2³² 或 2⁶⁴，您可以将大数写为 a₀w⁰ + a₁w¹ + a₂w² + ... ≅ a₀1⁰ + a₁1¹ + a₂1² + ... ≡ a₀ + a₁ + a₂ + ...（mod 5）。这也是为什么任意数的小数位数之和与原数全等的原因 modulo 3 or 9: 10 ≡ 1 (mod 3).
这也适用于字节的 3、5、15 和 17，16 位字的因数 255 和 257，以及 32 位字的因数 65,535 和 65,537。如果您注意到该模式，那是因为 b²ⁿ = (bⁿ+1)(bⁿ-1) + 1，其中 b = 2 且 n = 2、4、8 或 16。
您可以将此方法的变体应用于任何 n，使您的块大小与 -1 (mod n) 一致：交替加法和减法。它起作用是因为 a₀w⁰ + a₁w¹ + a₂w² + ... ≡ a₀(-1)⁰ + a₁(-1)¹ + a₂(-1)² + ... ≡ a₀ - a₁ + a₂ - ... (mod n)，但用处不大，因为许多这样的 n 值都是梅森素数。这类似于通过从右到左对数字进行加、减、加和减，可以得到任何小数的 mod 11，例如144 ≅ 4 - 4 + 1 ≡ 1 (mod 11)。就像数字一样，你可以用五位块做同样的把戏，因为 32 和 10 一样，也等于 -1 modulo 11.
另一个有用的特殊情况发生在 w ≡ w² ≡ c (mod b) 时。然后你有 a₀w⁰ + a₁w¹ + a₂w² + ... ≡ a₀·1 + a₁c + a₂c + ... ≡ a₀ + c(a₁ + a₂ + ...) (mod b)。这类似于 10 ≡ 100 ≡ 1000 ≡ ... ≡ 4 (mod 6)，因此任何数字都等于其最后一位数字加上其剩余数字之和的四倍，modulo 6. 计算可以是每个字节的查找和加法，以及乘以一个小常数，您可以通过一两个位移位来完成。比如取mod 20，可以把除最低位以外的所有字节相加 mod 20，和乘以256 mod 20 = 16，也就是左移4、然后加上最后一个字节。这可能非常方便：不计算余数为 1 或 0 的数字，这适用于半字节 modulo 6、10 和 12，以及字节 modulo 这些值和 20、24、30 , 34, 40, 48, 60, 68, 80, 96, 102, 120, 136, 160, 170, 192, 204 和 240。
如果一个数可以表示为特殊情况的乘积，可以用中国剩余定理求解。比如77 = 11×7, 32 ≡ -1 mod 11, 8 ≡ 1 mod 7, 所以可以求出除以11和7的余数, 就是除以77的余数. 大多数小质数都属于前面讨论的一种特殊情况。
许多后来的 RISC 架构有硬件划分但没有 modulus，并告诉程序员通过计算 a-(a/b)*b 来计算 a%b。 ARM A64 是当今使用最多的一种。如果你也没有硬件划分，check out this answer. An example of another approach when the base is a small constant is given here，在CISC架构上被广泛使用
还有一种算法 written by Sean Anderson in 2001 but probably discovered earlier 可以通过小于 2 的幂的一个数来计算 modulus。它类似于我在上面使用的技术，但依赖于位移位和可以扩展到 (1<<s)-1 的任何因子。这几乎就是您要找的！
通常，您的优化编译器应该使用最有效的方法在您的硬件上实现 %。在您的示例中，任何体面的编译器只会折叠常量并将 7%5 优化为 2.