「OI」OI 中的位运算和 bitset - 续

本文来继续介绍一下常见的位运算 /cy

获取一个数的符号

1
2
3
4
int v;
int sign; // 符号

sign = -(v < 0);

当然这样是不够的, 我们要处理分支预测 (

1
2
3
// 避免在带有标志寄存器的CPU上分支
// CHAR_BIT 是指占的字节数,(一般是 8
sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));

使用更少的指令

1
sign = v >> (sizeof(int) * CHAR_BIT - 1);

因为当有符号整数向右移位时,最左边的位的值被复制到其他位。 当值为负时,最左边的位为 11 ,否则为 00 ; 所有 11 位给出 1-1

不幸的是,这种行为是 特定于架构的

如果你感觉结果不是 1-1 或者 11 而感到很难过,你可以这样写

1
sign = +1 | (v >> (sizeof(int) * CHAR_BIT - 1));

你还想要判断 00 的话,你可以这样写 (

1
2
3
4
5
6
7
sign = (v != 0) | -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));

// 更快一些:
sign = (v != 0) | (v >> (sizeof(int) * CHAR_BIT - 1)); // -1, 0, or +1

// 或者是使用这种好记好看 更快(可能) 的写法
sign = (v > 0) - (v < 0); // -1, 0, or +1

检测两个整数是否有相反的符号

可以分别检验两个数的符号然后进行判断

当然有更为简洁的方法:

1
2
3
int x, y;               // 要比较的两个数

bool f = ((x ^ y) < 0); // 不同则为 true, 相同则为 false

计算数字的绝对值

1
a = (a > 0) ? a : -a;
1
2
3
4
5
6
int v;
unsigned int r; // 结果
const int mask = v >> sizeof(int) * CHAR_BIT - 1;

r = (v + mask) ^ mask;
// 或者是 : r = (v ^ mask) - mask;

某些 CPU 没有整数绝对值指令(或编译器无法使用它们)

在分治预测失败代价十分高的机器上,上述代码可能比第一段的方法更快,即使操作次数相同 (

计算两个整数的最小值或最大值

1
2
3
4
5
int x, y;   
int r;

r = y ^ ((x ^ y) & -(x < y)); // min(x, y)
r = x ^ ((x ^ y) & -(x < y)); // max(x, y)

在一些毒瘤的 CPU 上,分治预测失败代价十分高并且没有条件移动指令存在,上面的表达式可能比下一段代码更快

1
r = (x < y) ? x : y;

即使它涉及两个以上的指令(通常情况下,上面是最好的)

它的作用是因为如果 x<yx < y,则 (x<y)-(x < y) 将全部为1,因此 r = y ^ x ^ y = x 否则,如果 xyx \geq y,则 (x<y)-(x < y) 将全为零,因此 r = y ^ ((x ^ y) & 0) = y

在某些 CPU 上,计算 x<yx < y 的结果也需要分支指令,因此 可能没有任何优势

如果您知道 INT_MIN <= x - y <= INT_MAX,那么您可以使用以下更快的内容,因为xyx - y 只需要评估一次。

1
2
r = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // min(x, y)
r = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // max(x, y)

请注意,1989 ANSI C 规范未指定有符号右移的结果,因此这些 不可移植

判断是是否是 2 的整数次幂

1
2
3
4
unsigned int v;
bool f;

f = (v & (v - 1)) == 0;

这样写可能会有锅

如果 vv00 ,那么会得到错误的结果

可以采取这样的方式:

1
f = v && !(v & (v - 1));

二进制中 1 出现的奇偶性

暴力查询

1
2
3
4
5
6
7
unsigned int v;
bool parity = false; // 结果

while (v) {
parity = !parity;
v = v & (v - 1);
}

可以通过查表法来解决(

1
2
3
4
5
6
7
8
9
10
11
12
// 静态表
static const bool ParityTable256[256] = {
#define P2(n) n, n^1, n^1, n
#define P4(n) P2(n), P2(n^1), P2(n^1), P2(n)
#define P6(n) P4(n), P4(n^1), P4(n^1), P4(n)
P6(0), P6(1), P6(1), P6(0)
};

// 查询
unsigned int v; // 输入
unsigned char *p = (unsigned char *) &v;
parity = ParityTable256[p[0] ^ p[1] ^ p[2] ^ p[3]];

可以使用 6464 位乘法和模数除法计算 字节 的奇偶校验

1
2
unsigned char t;  // byte value to compute the parity of
bool parity = (((t * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1;

交换两个数字

首先就是经常用的 xor 交换法, 唯一的优点就是不使用额外空间

1
2
unsigned int i, j;
i ^= j ^= i ^= j;

当然也可以使用加减法, 虽然有时候并没有上面的快 (

1
2
unsigned int i, j;
&i == &j || (i -= j, j += i, i = j - i);

交换两个数字的单个位

1
2
3
4
5
6
7
unsigned int i, j;
unsigned int n; // 位数
unsigned int b; // 要交换的位
unsigned int r; // 位交换结果

unsigned int x = ((b >> i) ^ (b >> j)) & ((1U << n) - 1); // 临时变量
r = b ^ ((x << i) | (x << j));

将一个数的二进制翻转

暴力

1
2
3
4
5
6
7
8
9
10
11
unsigned int v;
unsigned int r = v;
int s = sizeof(v) * CHAR_BIT - 1;

for (v >>= 1; v; v >>= 1) {
r <<= 1;
r |= v & 1;
s--;
}

r <<= s;

查表法

继续查表 /cy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static const unsigned char BitReverseTable256[256] = {
# define R2(n) n, n + 2*64, n + 1*64, n + 3*64
# define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
# define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
R6(0), R6(2), R6(1), R6(3)
};

unsigned int v;
unsigned int c;

// 方法 1
c = (BitReverseTable256[v & 0xff] << 24) |
(BitReverseTable256[(v >> 8) & 0xff] << 16) |
(BitReverseTable256[(v >> 16) & 0xff] << 8) |
(BitReverseTable256[(v >> 24) & 0xff]);

// 方法 2
unsigned char *p = (unsigned char *) &v;
unsigned char *q = (unsigned char *) &c;
q[3] = BitReverseTable256[p[0]];
q[2] = BitReverseTable256[p[1]];
q[1] = BitReverseTable256[p[2]];
q[0] = BitReverseTable256[p[3]];

如果你的 CPU 可以轻松加载和存储字节,第一种方法需要大约 1717 次操作,第二种方法大约需要 1212

使用 6464 位乘法和取模来翻转 (单字节)

1
2
3
unsigned char b;

b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;

不使用取模操作

1
2
3
unsigned char b;

b = ((b * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> 32;

这个不是十分好理解 /cy

可以自己手算一下(?

栗子: 对于字节 (abcdefgh)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
                                                                                        abcd efgh (-> hgfe dcba)
* 1000 0000 0010 0000 0000 1000 0000 0010 (0x80200802)
-------------------------------------------------------------------------------------------------
0abc defg h00a bcde fgh0 0abc defg h00a bcde fgh0
& 0000 1000 1000 0100 0100 0010 0010 0001 0001 0000 (0x0884422110)
-------------------------------------------------------------------------------------------------
0000 d000 h000 0c00 0g00 00b0 00f0 000a 000e 0000
* 0000 0001 0000 0001 0000 0001 0000 0001 0000 0001 (0x0101010101)
-------------------------------------------------------------------------------------------------
0000 d000 h000 0c00 0g00 00b0 00f0 000a 000e 0000
0000 d000 h000 0c00 0g00 00b0 00f0 000a 000e 0000
0000 d000 h000 0c00 0g00 00b0 00f0 000a 000e 0000
0000 d000 h000 0c00 0g00 00b0 00f0 000a 000e 0000
0000 d000 h000 0c00 0g00 00b0 00f0 000a 000e 0000
-------------------------------------------------------------------------------------------------
0000 d000 h000 dc00 hg00 dcb0 hgf0 dcba hgfe dcba hgfe 0cba 0gfe 00ba 00fe 000a 000e 0000
>> 32
-------------------------------------------------------------------------------------------------
0000 d000 h000 dc00 hg00 dcb0 hgf0 dcba hgfe dcba
& 1111 1111
-------------------------------------------------------------------------------------------------
hgfe dcba

显示可能有锅, 可以看这个截图:

img

请注意,最后两个步骤可以组合在某些处理器上,因为 寄存器可以作为字节访问

只是乘以使寄存器存储结果的高 3232 位并取低字节。 因此,它可能只需要 66 次操作

不使用 6464 位进行翻转

1
b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;

确保将结果赋值或转换为 unsigned char 以删除较高位中的多余位

计算以二为底的对数

暴力计算

1
2
3
4
5
6
unsigned int v;
unsigned int r = 0; // lg(v)

while (v >>= 1) {
r++;
}

IEEE

1
2
3
4
5
6
7
8
int v;
int r; // lg(v)
union { unsigned int u[2]; double d; } t;

t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = v;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;

这种方法只需要 55 次操作,但是许多 CPU 在操作双精度方面都很慢,并且必须适应不同架构

查表法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static const char LogTable256[256] = 
{
#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
-1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
};

unsigned int v;
unsigned r; // lg(v)
register unsigned int t, tt;

if (tt = v >> 16) {
r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
} else {
r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}

查找表方法仅需要大约 77 个操作来查找 3232 位值的日志。 如果扩展为 6464 位,则大约需要9次操作。 可以使用四个表来替换另一个操作,每个表都包含可能的添加

如果输入比较分散,请考虑使用下面这种方法

1
2
3
4
5
6
7
8
9
if (tt = v >> 24) {
r = 24 + LogTable256[tt];
} else if (tt = v >> 16) {
r = 16 + LogTable256[tt];
} else if (tt = v >> 8) {
r = 8 + LogTable256[tt];
} else {
r = LogTable256[v];
}

lg 的复杂度实现

1
2
3
4
5
6
7
8
9
10
11
unsigned int v;
const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
const unsigned int S[] = {1, 2, 4, 8, 16};

register unsigned int r = 0; // lg(v)
for (register int i = 4; i >= 0; i--) { // 可以循环展开 (
if (v & b[i]) {
v >>= S[i];
r |= S[i];
}
}

如果你的 CPU 分支预测失败的代价很高,可以使用

1
2
3
4
5
6
7
8
9
unsigned int v;	         // 32-bit value to find the log2 of 
register unsigned int r; // result of log2(v) will go here
register unsigned int shift;

r = (v > 0xFFFF) << 4; v >>= r;
shift = (v > 0xFF ) << 3; v >>= shift; r |= shift;
shift = (v > 0xF ) << 2; v >>= shift; r |= shift;
shift = (v > 0x3 ) << 1; v >>= shift; r |= shift;
r |= (v >> 1);

向上取到 2 的整数次幂

找到一个最小的 22 的整数次幂 tt , 使得 tvt \geq v

暴力

1
2
3
4
unsigned int const v;
unsigned int r; // 结果

while (r <= v) r >>= 1;

时间复杂度 O(logn)O(\log n)

二分答案

可以使用二分答案进行操作

二分 tt, 也是 O(logn)O(\log n)

浮点数

1
2
3
4
5
6
7
8
9
10
unsigned int const v; 
unsigned int r; // 结果

if (v > 1) {
float f = (float)v;
unsigned int const t = 1U << ((*(unsigned int *)&f >> 23) - 0x7f);
r = t << (t < v);
} else {
r = 1;
}

上面的代码使用了 88 个操作,但适用于所有 v231v \le 2^{31}

还有更快的版本, 但是只适用于 v225v \le 2^{25}

1
2
float f = (float)(v - 1);  
r = 1U << ((*(unsigned int*)(&f) >> 23) - 126);

枚举

1
2
3
4
5
6
7
8
9
unsigned int v;

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;

直接枚举 3232 位(

注意到如果 vv00 的时候, 最终的 vv 就是 00 我们可以在后面加上 v += (v == 0) 来避免 00 的问题 (

确认一个字节是否有 0

1
2
unsigned int v;
bool hasZeroByte = ~((((v & 0x7F7F7F7F) + 0x7F7F7F7F) | v) | 0x7F7F7F7F);

下面是另外几种方法

1
2
3
4
5
bool hasNoZeroByte = ((v & 0xff) && (v & 0xff00) && (v & 0xff0000) && (v & 0xff000000))


unsigned char * p = (unsigned char *) &v;
bool hasNoZeroByte = *p && *(p + 1) && *(p + 2) && *(p + 3);

第一种如果将她扩展到 6464 位, 只需要将 0x7F7F7F7F 替换为 0x7F7F7F7F7F7F7F7F 即可

为了进一步改进,可以执行仅需要 44 次操作的快速预测试以确定该字是否可以具有零字节

1
2
3
4
bool hasZeroByte = ((v + 0x7efefeff) ^ ~v) & 0x81010100;
if (hasZeroByte) {
hasZeroByte = ~((((v & 0x7F7F7F7F) + 0x7F7F7F7F) | v) | 0x7F7F7F7F);
}

如果高字节为 0x80,则测试也返回true,因此偶尔会出现误报,但上面较慢且更可靠的版本可能会用于候选者,以便在正确输出的情况下全面提高速度

可以简化为

1
#define haszero(v) (((v) - 0x01010101UL) & ~(v) & 0x80808080UL)

确认一个字节是否等于 n

我们可能想知道任何字节是否具有特定值

注意到对自身进行异或运算导致零字节而非零,否则我们可以将结果传递给 haszero

1
#define hasvalue(x,n) (haszero((x) ^ (~0UL / 255 * (n))))

确认一个字节是否小于 n

1
#define hasless(x, n) (((x) - ~0UL / 255 * (n)) & ~(x) & ~0UL / 255 * 128)

确认一个字节是否大于 n

1
#define hasmore(x,n) (((x) + ~0UL / 255 * (127 - (n)) | (x)) & ~0UL / 255 * 128)

确认一个字节是否介于 m, n

1
2
#define likelyhasbetween(x, m, n) \
((((x) - ~0UL / 255 * (n)) & ~(x) & ((x) & ~0UL / 255 * 127) + ~0UL / 255 * (127 - (m))) & ~0UL / 255 * 128)

m<nm < n 时,该技术测试字 xx 是否包含无符号字节值,使得 m<x<nm <x<n 。 当 nnmm 为常数时,它使用 77 次算术/逻辑运算

注意:等于 nn 的字节可以通过可能误报,因此如果需要某个结果,应该按字符检查

这种方法适用于快速预处理。一个变量需要多一次操作(常量m和n总共8个),但提供的确切答案是

1
2
#define likelyhasbetween(x, m, n) \
((((x) - ~0UL / 255 * (n)) & ~(x) & ((x) & ~0UL / 255 * 127) + ~0UL / 255 * (127 - (m))) & ~0UL / 255 * 128)

计算余数

计算除以 2s2^s 的余数

1
2
3
4
5
const unsigned int n;
const unsigned int s;
const unsigned int d = 1U << s;
unsigned int m;
m = n & (d - 1);

大多数 OIer 很早就学会了这个技巧,但为了完整起见,我们还是放在这里了(

计算除以 2s12^s-1 的余数

1
2
3
4
5
6
7
8
9
10
11
12
unsigned int n;
const unsigned int s;
const unsigned int d = (1 << s) - 1;
unsigned int m; // n % d 的答案

for (m = n; n > d; n = m) {
for (m = 0; n; n >>= s) {
m += n & d;
}
}

m = m == d ? 0 : m;

这种方法最多花费 5+(4+5ceil(lgn/s))ceil(lg(lgn/s))5 + (4 + 5 * \text{ceil}(\lg n / s)) * \text{ceil}(\lg(\lg n / s)) 的时间, 所以说她的时间复杂度为 O(lgn×lglgn)O(\lg n\times \lg \lg n)

并行计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

// The following is for a word size of 32 bits!

static const unsigned int M[] =
{
0x00000000, 0x55555555, 0x33333333, 0xc71c71c7,
0x0f0f0f0f, 0xc1f07c1f, 0x3f03f03f, 0xf01fc07f,
0x00ff00ff, 0x07fc01ff, 0x3ff003ff, 0xffc007ff,
0xff000fff, 0xfc001fff, 0xf0003fff, 0xc0007fff,
0x0000ffff, 0x0001ffff, 0x0003ffff, 0x0007ffff,
0x000fffff, 0x001fffff, 0x003fffff, 0x007fffff,
0x00ffffff, 0x01ffffff, 0x03ffffff, 0x07ffffff,
0x0fffffff, 0x1fffffff, 0x3fffffff, 0x7fffffff
};

static const unsigned int Q[][6] =
{
{ 0, 0, 0, 0, 0, 0}, {16, 8, 4, 2, 1, 1}, {16, 8, 4, 2, 2, 2},
{15, 6, 3, 3, 3, 3}, {16, 8, 4, 4, 4, 4}, {15, 5, 5, 5, 5, 5},
{12, 6, 6, 6 , 6, 6}, {14, 7, 7, 7, 7, 7}, {16, 8, 8, 8, 8, 8},
{ 9, 9, 9, 9, 9, 9}, {10, 10, 10, 10, 10, 10}, {11, 11, 11, 11, 11, 11},
{12, 12, 12, 12, 12, 12}, {13, 13, 13, 13, 13, 13}, {14, 14, 14, 14, 14, 14},
{15, 15, 15, 15, 15, 15}, {16, 16, 16, 16, 16, 16}, {17, 17, 17, 17, 17, 17},
{18, 18, 18, 18, 18, 18}, {19, 19, 19, 19, 19, 19}, {20, 20, 20, 20, 20, 20},
{21, 21, 21, 21, 21, 21}, {22, 22, 22, 22, 22, 22}, {23, 23, 23, 23, 23, 23},
{24, 24, 24, 24, 24, 24}, {25, 25, 25, 25, 25, 25}, {26, 26, 26, 26, 26, 26},
{27, 27, 27, 27, 27, 27}, {28, 28, 28, 28, 28, 28}, {29, 29, 29, 29, 29, 29},
{30, 30, 30, 30, 30, 30}, {31, 31, 31, 31, 31, 31}
};

static const unsigned int R[][6] =
{
{0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000},
{0x0000ffff, 0x000000ff, 0x0000000f, 0x00000003, 0x00000001, 0x00000001},
{0x0000ffff, 0x000000ff, 0x0000000f, 0x00000003, 0x00000003, 0x00000003},
{0x00007fff, 0x0000003f, 0x00000007, 0x00000007, 0x00000007, 0x00000007},
{0x0000ffff, 0x000000ff, 0x0000000f, 0x0000000f, 0x0000000f, 0x0000000f},
{0x00007fff, 0x0000001f, 0x0000001f, 0x0000001f, 0x0000001f, 0x0000001f},
{0x00000fff, 0x0000003f, 0x0000003f, 0x0000003f, 0x0000003f, 0x0000003f},
{0x00003fff, 0x0000007f, 0x0000007f, 0x0000007f, 0x0000007f, 0x0000007f},
{0x0000ffff, 0x000000ff, 0x000000ff, 0x000000ff, 0x000000ff, 0x000000ff},
{0x000001ff, 0x000001ff, 0x000001ff, 0x000001ff, 0x000001ff, 0x000001ff},
{0x000003ff, 0x000003ff, 0x000003ff, 0x000003ff, 0x000003ff, 0x000003ff},
{0x000007ff, 0x000007ff, 0x000007ff, 0x000007ff, 0x000007ff, 0x000007ff},
{0x00000fff, 0x00000fff, 0x00000fff, 0x00000fff, 0x00000fff, 0x00000fff},
{0x00001fff, 0x00001fff, 0x00001fff, 0x00001fff, 0x00001fff, 0x00001fff},
{0x00003fff, 0x00003fff, 0x00003fff, 0x00003fff, 0x00003fff, 0x00003fff},
{0x00007fff, 0x00007fff, 0x00007fff, 0x00007fff, 0x00007fff, 0x00007fff},
{0x0000ffff, 0x0000ffff, 0x0000ffff, 0x0000ffff, 0x0000ffff, 0x0000ffff},
{0x0001ffff, 0x0001ffff, 0x0001ffff, 0x0001ffff, 0x0001ffff, 0x0001ffff},
{0x0003ffff, 0x0003ffff, 0x0003ffff, 0x0003ffff, 0x0003ffff, 0x0003ffff},
{0x0007ffff, 0x0007ffff, 0x0007ffff, 0x0007ffff, 0x0007ffff, 0x0007ffff},
{0x000fffff, 0x000fffff, 0x000fffff, 0x000fffff, 0x000fffff, 0x000fffff},
{0x001fffff, 0x001fffff, 0x001fffff, 0x001fffff, 0x001fffff, 0x001fffff},
{0x003fffff, 0x003fffff, 0x003fffff, 0x003fffff, 0x003fffff, 0x003fffff},
{0x007fffff, 0x007fffff, 0x007fffff, 0x007fffff, 0x007fffff, 0x007fffff},
{0x00ffffff, 0x00ffffff, 0x00ffffff, 0x00ffffff, 0x00ffffff, 0x00ffffff},
{0x01ffffff, 0x01ffffff, 0x01ffffff, 0x01ffffff, 0x01ffffff, 0x01ffffff},
{0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff},
{0x07ffffff, 0x07ffffff, 0x07ffffff, 0x07ffffff, 0x07ffffff, 0x07ffffff},
{0x0fffffff, 0x0fffffff, 0x0fffffff, 0x0fffffff, 0x0fffffff, 0x0fffffff},
{0x1fffffff, 0x1fffffff, 0x1fffffff, 0x1fffffff, 0x1fffffff, 0x1fffffff},
{0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff},
{0x7fffffff, 0x7fffffff, 0x7fffffff, 0x7fffffff, 0x7fffffff, 0x7fffffff}
};

unsigned int n; // numerator
const unsigned int s; // s > 0
const unsigned int d = (1 << s) - 1; // so d is either 1, 3, 7, 15, 31, ...).
unsigned int m; // n % d goes here.

m = (n & M[s]) + ((n >> s) & M[s]);

for (const unsigned int * q = &Q[s][0], * r = &R[s][0]; m > d; q++, r++)
{
m = (m >> *q) + (m & *r);
}
m = m == d ? 0 : m; // OR, less portably: m = m & -((signed)(m - d) >> s);

打表好啊(

这种求模数除以小于2的幂的整数的方法最多花费 O(lglgn)O(\lg \lg n) 时间

如果在编译时知道分母,表可能会被删除

只需提取几个相关条目并展开循环。它可以很容易地扩展到更多位

坚持原创技术分享,您的支持将鼓励我继续创作!