检查数字的逻辑可以被3整除吗？

int isdivby3(int n) {
    if (n < 0) n = -n;

    while (n > 0) n -= 3;

    return n == 0;
}

但我们可以改善这一点.任何数字都可以这样表示:(“,”表示包括范围)：

Base2 (AKA binary)
(0,1) + 2*(0,1) + 4*(0,1)

Base4
(0,3) + 4*(0,3) + 16*(0,3)

BaseN
(0,N-1) + N*(0,N-1) + N*N*(0,N-1)

现在的诀窍是,当且仅当基数n中的x的数字可被n-1整除时,数字x才能被n-1整除.这个技巧以9为人所熟知：

1926 = 6 + 2*10 + 9*100 + 1*1000
6+2+9+1 = 8 + 1*10
8+1 = 9 thus 1926 is divisible by 9

现在我们也可以在base4中应用3.幸运的是,因为4是2的幂,我们可以进行二进制按位运算.我使用符号编号(基数).

27(10) = 123(4)
Digitsum
12(4)
Digitsum again
3(4) = Divisible!

现在让我们把它翻译成C：

int div3(int n) {
    if (n < 0) n = -n;
    else if (n == 0) return 1;

    while (n > 3) {
        int d = 0;

        while (n > 0) {
            d += n & 3;
            n >>= 2;
        }

        n = d;
    }

    return n == 3;
}

快速燃烧.