Come dividere per 9 usando solo i turni/add/sub?

Question

La settimana scorsa ero in un'intervista e c'era un test come questo:

Calcolare N/9 (dato che N è un numero intero positivo), utilizzando solo sinistra shift, SHIFT DESTRA, addizioni, sottrazioni istruzioni.

Answer 1

1. è possibile utilizzare il trucco matematico a virgola fissa.

   in modo da scalare in modo che la parte significativa della frazione vada all'intervallo intero, eseguire l'operazione matematica frazionaria necessaria e ridimensionarla.

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

   come potete vedere ho scalato dal 10000. Ora la parte intera di 10000/9=1111 è abbastanza grande in modo da poter scrivere:

   a/9 = ~a*1111/10000 
   

2. potenza di 2 scala

   Se si utilizza il potere della scala 2 allora avete bisogno solo di utilizzare bit-shift, invece di divisione. È necessario scendere a compromessi tra precisione e intervallo di valori di input. Ho scoperto che empiricamente sulla 32 bit aritmetica la scala migliore per questo è così 1<<18:

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

   Il (a+1) corregge gli errori di arrotondamento torna alla gamma destra.

3. moltiplicazione Hardcoded

   riscrivere la costante moltiplicazione binaria

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

   Ora, se avete bisogno di calcolare c=(a*q) utilizzare hard-coded la moltiplicazione binaria: per ogni 1 del q è possibile aggiungere a<<(position_of_1) allo c. Se vedi qualcosa come 111 puoi riscriverlo a 1000-1 riducendo al minimo il numero di operazioni.

   Se mettete tutto questo insieme si dovrebbe ottenuto qualcosa di simile a questo codice C++ di 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; 
       } 
   

   Ora se si vede la forma binaria il modello 111000 sta ripetendo in modo yu può migliorare ulteriormente il codice un po ':

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

Answer 2

primo luogo, trovare la rappresentazione di 1/9 in binario 0,0001110001110001
significa che è (1/16) + (1/32) + (1/64) + (1/1024) + (1/2048) + (1/4096) + (1/65536)
so (x/9) uguale a (x >> 4) + (x >> 5) + (x >> 6) + (x >> 10) + (x >> 11) + (x >> 12) + (x >> 16)

Possibile ottimizzazione (se i cicli sono consentiti):
se un ciclo su diritto 0001110001110001b spostandolo ogni ciclo,
add "x" per il risultato registrarsi ogni volta che il bagaglio è stato impostato su questo spostare e spostare il risultato giusto ogni volta successivo, il risultato è 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 

(attualmente non si può verificare ciò, può essere sbagliato)