c语言 - 为什么这个算法来确定是可分割的还是无效的?

Question

static inline bool is_divisible(uint32_t n, uint64_t M) {
return n * M <= M - 1;
}
static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1;
....
uint8_t div3 = is_divisible(17, M3);

如标题中所述，此函数可以确定n是否可以被 3 整除。 我唯一弄清楚的是M与d为 3 的ceil((1<<64)/d)相同。

有没有人打电话解释为什么is_divisible工作？ 谢谢！

Answer 1

将 n 除以 3以求商 q 和余数 r，允许我们将 n 表示为n= 3q+ r，其中 0 ≤r<<em>3。

直观地说，将 3 q + r 乘以 (2⁶⁴−1)/3 + 1 会导致q部分消失，因为它包裹模 2 64，使余数部分位于 [0， 2⁶⁴) 的三个段之一，具体取决于r的值。与M3的比较确定它是否在第一段中，这意味着r为零。接下来是证明。

请注意，M3是 (2⁶⁴−1)/3 + 1。

则 n•M3 = (3 q + r)•((2 64−1)/3 + 1) = q•(2 64−1)+3 q+r•((2 64−1)/3 + 1) = q•2 64+2q+r•((2⁶⁴−1)/3 + 1)。

当用uint64_t算术计算时，q•2⁶⁴项由于包装模 2⁶⁴而消失，因此计算结果为 2q+r•((2⁶⁴−1)/3 + 1)。

假设n是 3 的倍数。则r= 0。由于n是uint32_t值，q<2³²，因此 2q+r•((2⁶⁴−1)/3 + 1) = 2 q <233<<sup>M3。

假设n不是 3 的倍数。则r = 1 或r= 2。如果 r = 1，则r•((2 64−1)/3 + 1) = (2⁶⁴−1)/3 + 1>M3−1。当然，如果 r =2，r•((2⁶⁴−1)/3 + 1) 甚至更大，也超过M3−1。但是，我们需要关注uint64_t算术的包装。同样，由于q<2 32，当r= 2 时，我们有 2q+r•((2 64−1)/3 + 1) <2•2³²+ 2•((2 64−1)/3 + 1) = 2 33 + 2/3•2 64 − 2/3 + 2 = 2 64 − 1/3•2 64 + 2³³+ 4/3，这显然小于 2⁶⁴，因此不会发生换行。