CODEWITHSUNDEEP
c++assemblyvisual-c++x86integer-division
sharptooth
sharptooth

Reputation: 170479

Why is such complex code emitted for dividing a signed integer by a power of two?

When I compile this code with VC++10:

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

I get this disassembly:

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

which is clean and concise and replaced a division by a power of two with a logical right shift.

Yet when I compile this code:

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

I get this disassembly:

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

that performs some manipulations before doing a right arithmetic shift.

What's the need for those extra manipulations? Why is an arithmetic shift not enough?

Upvotes: 44

Views: 3387

Answers (3)

Paul R
Paul R

Reputation: 212929

The reason is that unsigned division by 2^n can be implemented very simply, whereas signed division is somewhat more complex.

unsigned int u;
int v;

u / 4096 is equivalent to u >> 12 for all possible values of u.

v / 4096 is NOT equivalent to v >> 12 - it breaks down when v < 0, as the rounding direction is different for shifting versus division when negative numbers are involved.

Upvotes: 91

pmdj
pmdj

Reputation: 23428

From the C standard:

When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded.105) If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a; otherwise, the behavior of both a/b and a%b is undefined.

It's not hard to think of examples where negative values for a don't follow this rule with pure arithmetic shift. E.g.

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

which satisfies the equation, whereas

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

is not division with truncation, and therefore -2 * 4096 - 4095 is most certainly not equal to -8191.

Note that shifting of negative numbers is actually implementation-defined, so the C expression (-8191) >> 12 does not have a generally correct result as per the standard.

Upvotes: 11

Stephen Canon
Stephen Canon

Reputation: 106117

the "extra manipulations" compensate for the fact that arithmetic right-shift rounds the result toward negative infinity, whereas division rounds the result towards zero.

For example, -1 >> 1 is -1, whereas -1/2 is 0.

Upvotes: 35

Related Questions