algorithm - 如何仅使用 shifts/add/sub 除以 9？

Question

上周我在面试，有一个测试是这样的:

计算N/9(假定N为正整数)，仅使用左移、右移、加、减指令。

Answer 1

首先，求出1/9的二进制表示0,0001110001110001
表示它是 (1/16) + (1/32) + (1/64) + (1/1024) + (1/2048) + (1/4096) + (1/65536)
所以 (x/9) 等于 (x>>4) + (x>>5) + (x>>6) + (x>>10) + (x>>11 )+ (x>>12)+ (x>>16)

可能的优化(如果允许循环):
如果你循环遍历 0001110001110001b 并在每个循环中右移它，
每当在此类次上设置进位时，将“x”添加到您的结果寄存器然后每次都改变你的结果，你的结果是 x/9

        mov cx, 16     ; assuming 16 bit registers
        mov bx, 7281   ; bit mask of 2^16 * (1/9)
        mov ax, 8166   ; sample value, (1/9 of it is 907)
        mov dx, 0      ; dx holds the result

    div9:
        inc ax         ; or "add ax,1" if inc's not allowed :) 
                       ; workaround for the fact that 7/64 
                       ; are a bit less than 1/9
        shr bx,1
        jnc no_add
        add dx,ax
    no_add:
        shr dx,1
        dec cx
        jnz div9

(目前无法测试，可能有误)