CODEWITHSUNDEEP
assemblybinarydivisionsignedinteger-division
user200783
user200783

Reputation: 14348

Is there any similarity between the results of an unsigned and a signed division?

I have recently learned that for an m-bit x n-bit multiplication (producing an (m+n)-bit product), min(m,n) least-significant bits of the result are always the same whether the multiplication is unsigned or signed.

For an m-bit / n-bit division (producing an m-bit quotient and a n-bit remainder), are there any bits which are always the same for both an unsigned and a signed division, or (for some inputs) do the two division methods produce completely different results?

Upvotes: 1

Views: 520

Answers (2)

Johan
Johan

Reputation: 76567

If any operand has the MSB set (i.e. is negative), unsigned and signed division are markedly different.
If the MSB in both operands is zero (i.e. both numbers are positive), the result will be the same.

When using unsigned division all bits in the operands are interpreted as unsigned, i.e. negative numbers are interpreted as (very) large integers.

Results for div:

mov  eax, 1
xor  edx, edx    
mov  ecx, -1
div  ecx      ; -> EAX = 0 because the -1 is interpreted as a large positive number
              ; -> EDX = 1

mov  eax, -1
xor  edx, edx
mov  ecx, 2
div  ecx      ; -> EAX = $7FFFFFFF because div 2 shifts bits right by 1.
              ; -> EDX = 1

When using signed division the operands are first transformed to absolute numbers and then the signs of the operands are reapplied to the result of the division.

Results for idiv:

mov  eax, 1
xor  edx, edx ; XOR because EAX is positive
mov  ecx, -1
idiv ecx      ; -> EAX = -1 because 1 / -1 = -1
              ; -> EDX = 0

mov  eax, -1
cdq           ; CDQ because EAX is negative
mov  ecx, 2
idiv ecx      ; -> EAX = 0 because 1 shr 1 = 0 and -0 is still 0
              ; -> EDX = -1

In some processors div (with all positive operands) will be a cycle faster than idiv because it has to do less 'thinking'. However given the fact that division is a horribly slow operation anyway, this will hardly matter.

Upvotes: 3

old_timer
old_timer

Reputation: 71536

Did you not learn from the prior question one how to do this? Back to grade school math, long division (thats how old/slow (many clocks) division works anyway).

Lets take the bit pattern 0b10101010 / 0b101, which is either unsigned 0xAA / 5 or signed -0x56 / -3. I had to cheat and use my calculator. Anyway the easy one first

    -----------
101 ) 10101010


        100010
    -----------
101 ) 10101010
      101
      === 
        00101 
          101
          ===
            00

so the result is 0x22

But for the signed division to get the right answer we need to do unsigned which is how you would do it by hand in grade school, then apply the sign later so we are not dividing 0b101 into 0b10101010 we are instead dividing 0b11 into 0b1010110

        11100  
    ---------
 11 ) 1010110
       11 
      ===
       100
        11
       ===
         11
         11
         ==
          010

So the answer is 0x1C remainder 0x2 because both were negative the result is positive.

Similar to add/subtract and signed and unsigned multiply, you negate or not going in and negate or not something coming out. Division is not like multiply where it is just the same number added over and over again after being shifted. You start from the left not the right as well so I just cant see how it would generate any kind of common pattern between them. Above demonstrates that but also demonstrates that if you negate one you get a lot of common bits up front, that is probably dumb luck.

I am not going to attempt to divide the bit variables abc into def unlike addition/subtract and multiply it doesnt work like that which is why some percentage of processors dont have multiply or divide or some have multiply but not divide, you can make the multiply faster by using a lot of logic, the divide perhaps as well, that or a lot of clocks.

Maybe look at Hackers Delight to see division shortcuts and from that maybe a pattern will emerge that makes some percentage of the bits the same but I doubt it. You have to get the actual binary operand going into the divide logic and probably the upper bits in the numerator to be the same signed or unsigned, but that means they are two totally different numbers. As demonstrated above if you take the same bit patterns which have different signed representations and you feed those same bit patterns into unsigned or signed division you get different bit patterns in the numerator and/or denominator and thus a different result, no patterns expected to match. If both numbers are positive then both should give the same result sure.

Upvotes: 1

Related Questions