Pourquoi un code aussi complexe est-il émis pour diviser un entier signé par une puissance de deux?

Question

Quand je compile ce code avec VC++10:

DWORD ran = rand();
return ran / 4096;

Je reçois ce démontage:

299: {
300:    DWORD ran = rand();
  00403940  call        dword ptr [__imp__rand (4050C0h)]  
301:    return ran / 4096;
  00403946  shr         eax,0Ch  
302: }
  00403949  ret

qui est propre et concis et remplacé une division par une puissance de deux, avec une logique de décalage à droite.

Pourtant, quand je compile ce code:

int ran = rand();
return ran / 4096;

Je reçois ce démontage:

299: {
300:    int ran = rand();
  00403940  call        dword ptr [__imp__rand (4050C0h)]  
301:    return ran / 4096;
  00403946  cdq  
  00403947  and         edx,0FFFh  
  0040394D  add         eax,edx  
  0040394F  sar         eax,0Ch  
302: }
  00403952  ret

qui effectue quelques manipulations avant de faire un droit de décalage.

Quel est le besoin pour ces manipulations? Pourquoi un décalage pas assez?

Answer 1

La raison en est que non signé de la division par 2^n peut être mis en œuvre très simplement, alors que signée de la division est un peu plus complexe.

unsigned int u;
int v;

u / 4096 est équivalent à u >> 12 pour toutes les valeurs possibles de l' u.

v / 4096 est PAS équivalent à v >> 12 - il se décompose lors de l' v < 0, comme l'arrondi de la direction est différent pour un changement de rapport de division lorsque les nombres négatifs sont impliqués.

Answer 2

les "manipulations supplémentaires" compensent le fait que l'arithmétique «décalage à droite» arrondit le résultat à l'infini négatif, alors que la division arrondit le résultat à zéro.

Par exemple, -1 >> 1 est -1 , alors que -1/2 est 0 .

Answer 3

Du C standard:

Lorsque les entiers sont divisés, le résultat de l'opérateur / est le algébrique quotient avec toute partie fractionnaire jeté.105) Si le le quotient a/b est représentable, l'expression (a/b)*b + a%b est égal à un; sinon, le comportement des deux a/b et a%b est indéfini.

Il n'est pas difficile de penser à des exemples où des valeurs négatives pour ne pas suivre cette règle avec de la pure arithmétique maj. E. g.

(-8191) / 4096 -> -1
(-8191) % 4096 -> -4095

qui satisfait à l'équation, alors que

(-8191) >> 12 -> -2 (assuming arithmetic shifting)

n'est pas de la division de la troncature, et, par conséquent, -2 * 4096 - 4095 est certainement pas égale à -8191.

Notez que le changement de nombres négatifs est effectivement mise en œuvre définies, de sorte que le C de l'expression (-8191) >> 12 n'ont généralement un résultat correct, conformément à la norme.