如何除以9使用仅使用轮班/加法/分？

Question

上周我参加了一次面试，有一次这样的考试：

计算N/9 (假定N是正整数)，只使用左移、右移位、加法、SUBSTRACT指令。

Answer 1

首先，在二进制0,0001110001110001中找到1/9的表示形式。

表示为(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

(目前无法测试此，可能是错误的)

Answer 2

1. 你可以用不动点的数学技巧. 所以你只需把重要的分数部分放大到整数范围，做你需要的分数数学运算，然后缩小。 a/9 =(a*10000)/9)/10000 如您所见，我使用10000进行缩放。现在，10000/9=1111的整数部分足够大了，所以我可以写： a/9 = ~a*1111/10000
2. 2比例尺功率 如果你使用2级的能量，那么你只需要使用位移位而不是除法。您需要在精度和输入值范围之间进行折衷。我经验性地发现，在32 bit算法中，最好的尺度是1<<18，所以： (a+1)<<18)/9)>>18= ~a/9； (a+1)将舍入错误纠正回正确的范围。
3. 硬编码乘法 将乘法常数重写为二进制 Q= (1<<18)/9 = 29127 =01110001 1100 0111桶 现在，如果您需要计算c=(a*q)，可以使用硬编码二进制乘法:对于q的每个1，您可以将a<<(position_of_1)添加到c中。如果您看到类似于111的内容，您可以将其重写为1000-1，以最小化操作的数量。 如果将所有这些放在一起，您应该得到类似于我的C++代码的东西： DWORD div9(DWORD a) { // ((a+1)*q)>>18 =(a+1)<<18)/9)>>18=a/9；// Q= (1<<18)/9 = 29127 = 0111 0001 1100 0111 bin //有效a=<0,147455 > DWORD c；c = (a<< 3)-(a )；// c= a*29127 c+=(a<< 9)-(a<< 6)；c+=(a<<15)-(a<<12)；a<<；// c= (a+1)*29127 c>>=18；// c= ((a+1)*29127)>>18返回c；} 现在，如果您看到二进制形式，模式111000正在重复，这样yu可以进一步改进代码： DWORD div9(DWORD a) { DWORD c；c =(a<<3)-a；//第一模式c+=(c<<6)+(c<<12)；//和其他2.c+=29127；c>>=18；返回c；}