不用“/”运算如何除以13

Question

有什么不用实际除法运算就可以除以13的方法吗？

我只找到检查可被 13 整除的测试。

我正在寻找类似于这个除以 10 的东西：

static A_UINT32 div_10(A_UINT32 duration)
{
    A_UINT64 invDivisor = 0x1999999A;
    return (A_UINT32)((invDivisor * duration) >> 32);
}

或者除以 3:

static A_UINT32 div_3(A_UINT32 duration)
{
    duration += (duration + 0x2) >> 2;
    duration += (duration + 0x8) >> 4;
    duration += (duration + 0x80) >> 8;
    duration += (duration + 0x8000) >> 16;
    return duration >>= 2;
}

Answer 1

您正在寻找两个正整数 k 和 m，s.t。

[n*k/2^m] = [n/13],  0 <= n < 2^32

其中[x]表示"rounding down"有理数x和n贯穿所有32位无符号整数。这2^32个方程可以简化为两个不等式：

k > 2^m/13
k < 2^m*N/(13N-1)

其中 N = [2^32/13]。所以我们必须寻找 m s.t 的值。 2^m/13 和 2^m*N/(13N-1) 之间有一个整数值。由于我们用 64 位进行计算，我们必须确保 n*k 代表 table 所有有趣的 n 的 64 位，因此我们需要 (2^32-1)*k < 2^64，即 k < 2^32 .从第一个不等式我们得到 2^m/13 < 2^32-1，这意味着 m <= 35。现在计算 k 对于 m 最多 35 的下边界和上边界，我们得到以下 table:

 m      2^m/13      2^m*N/(13N-1)
        ....
31   165191049.85    165191049.88
32   330382099.69    330382099.77
33   660764199.38    660764199.54
34  1321528398.77   1321528399.08
35  2643056797.54   2643056798.15

当m < 34时k的范围内没有整数值。但是对于 m=34 和 m=35 范围内只有一个整数。因此可能的解决方案：k = 1321528399, m = 34 或 k = 2643056798, m = 35.

其他除数的解法如下：

 d   m      k
 3  33  2863311531
 5  34  3435973837
 6  34  2863311531
 9  35  3817748708
10  35  3435973837
11  35  3123612579
12  35  2863311531
13  35  2643056798
15  35  2290649225
17  36  4042322161

如果想要用 64 位计算对所有 32 位无符号整数的正确结果，似乎没有这种形式的除以 7、14、19、21（和更多）的解决方案。

不用“/”运算如何除以13

How to divide by 13 without "/" operation

c

math

division