割られる数をnとおきます

• 最下位ビットを別途取っておきます(n0 = n & 1)
• nを1ビット右シフト(n >>= 1)
• 残りを4ビットごとに区切って和を取ります
  • n = ((0xf0f0f0f0 & n) >> 4) + (0x0f0f0f0f & n)
  • n = (n >> 16) + n
  • n = (n >> 8) + n
  • n &= 0xf
• 残りが0-15になるのですが5で割った剰余を求めます
  • 表引きでもよし (tmpres = 0x0432104321043210 >> (n << 2))
  • if (((n >> 2) & 3) > (n & 3)) {
            tmpres = 5 + (n & 3) - ((n >> 2) & 3);
    } else {
            tmpres = (n & 3) - ((n >> 2) & 3);
    }
• 上記でfloor(n/2)を5で割ったあまりが求まるので、10で割ったあまりにするには
  2倍してn0を足します (return (tmpres << 1) | n0)

これ5が2²+1であるというところに鍵があったりします。

• x ≡ 1 (mod yz) のとき x ≡ 1 (mod y)
• x ≡ 1 (mod (x-1))
• x ≡ 1 (mod y) ならば x² ≡ 1 (mod y)

なので
2^2k ≡ 1 (mod (2^2k) - 1)
2^2k ≡ 1 (mod (2^k + 1))、ゆえに
2⁴ (=16) ≡ 1 (mod 2² + 1 (=5))、さらに
2^{4 x 2} ≡ 1 (mod 5)
ということで4ビットごとに区切って足していけば剰余が求まるというわけです。

もひとつ

• x ≡ -1 (mod x+1)

すなわち4 ≡ -1 (mod 5)なのが最後の if 文の表現であります。

剰余が出るだけで商は出ないので無能