How to divide by 9 using just shifts/add/sub?

Question

Last week I was in an interview and there was a test like this:

Calculate N/9 (given that N is a positive integer), using only SHIFT LEFT, SHIFT RIGHT, ADD, SUBSTRACT instructions.

Answer 1

first, find the representation of 1/9 in binary 0,0001110001110001
means it's (1/16) + (1/32) + (1/64) + (1/1024) + (1/2048) + (1/4096) + (1/65536)
so (x/9) equals (x>>4) + (x>>5) + (x>>6) + (x>>10) + (x>>11)+ (x>>12)+ (x>>16)

Possible optimization (if loops are allowed):
if you loop over 0001110001110001b right shifting it each loop,
add "x" to your result register whenever the carry was set on this shift and shift your result right each time afterwards, your result is 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

( currently cannot test this, may be wrong)

Answer 2

1. you can use fixed point math trick.

   so you just scale up so the significant fraction part goes to integer range, do the fractional math operation you need and scale back.

   a/9 = ((a*10000)/9)/10000
   

   as you can see I scaled by 10000. Now the integer part of 10000/9=1111 is big enough so I can write:

   a/9 = ~a*1111/10000
   

2. power of 2 scale

   If you use power of 2 scale then you need just to use bit-shift instead of division. You need to compromise between precision and input value range. I empirically found that on 32 bit arithmetics the best scale for this is 1<<18 so:

   (((a+1)<<18)/9)>>18 = ~a/9;
   

   The (a+1) corrects the rounding errors back to the right range.

3. Hardcoded multiplication

   Rewrite the multiplication constant to binary

   q = (1<<18)/9 = 29127 = 0111 0001 1100 0111 bin
   

   Now if you need to compute c=(a*q) use hard-coded binary multiplication: for each 1 of the q you can add a<<(position_of_1) to the c. If you see something like 111 you can rewrite it to 1000-1 minimizing the number of operations.

   If you put all of this together you should got something like this C++ code of mine:

   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;
       }
   

   Now if you see the binary form the pattern 111000 is repeating so yu can further improve the code a bit:

   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;
       }