如何使用shift/add/sub除以9？

Question

上周我接受了采访,有一个这样的测试:

使用SHIFT LEFT,SHIFT RIGHT,ADD,SUBSTRACT指令计算N/9(给定N为正整数) .

Answer 1

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 = 0111 0001 1100 0111 bin
   

   现在，如果您需要计算，c=(a*q)请使用硬编码的二进制乘法：对于每个，1您q可以添加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
       // valid for a = < 0 , 147455 >
       DWORD c;
       c =(a<< 3)-(a    ); // c= a*29127
       c+=(a<< 9)-(a<< 6);
       c+=(a<<15)-(a<<12);
       c+=29127;           // c= (a+1)*29127
       c>>=18;             // c= ((a+1)*29127)>>18
       return c;
       }
   

   现在，如果您看到二进制形式，则该模式111000正在重复，因此您可以进一步改进代码：

   DWORD div9(DWORD a)
       {
       DWORD c;
       c =(a<<3)-a;        // first pattern
       c+=(c<<6)+(c<<12);  // and the other 2...
       c+=29127;           
       c>>=18;             
       return c;
       }