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)