シフトと加算と乗算だけで整数を3で割る

p.561

Hacker's Delight (邦訳: ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか)に載っているとの由。理窟はまったく分からない。

↓ テキストのVHDLPythonに書き換えた。

def div_by_3(dividend):
    d = dividend
    q = 0
    r = 0
    
    q = (d >> 2) + (d >> 4)
    q = q + (q >> 4)
    q = q + (q >> 8)
    q = q + (q >> 16)
    r = d - q * 3
    q = q + (5 * (r + 1) >> 4)
    return q
    
dividends = list(range(50))
for dividend in dividends:
    print(dividend, "÷ 3 =", div_by_3(dividend))