Why is it necessary to add a bias to the dividend for signed division by a power of 2?
I'm learning about assembly code in "Computer Systems- A Programmer's Perspective", and I encountered the following example:
In the following C function, we have left the definition of operation OP incomplete:
#define OP /* Unknown operator */ short arith(short x) { return x OP 16; }
When compiled, gcc generates the following assembly code:
arith: leaq 15(%rdi), %rax testq %rdi, %rdi cmovns %rdi, %rax sarq $4, %rax ret
What operation is OP?
Later, the book gives the following answer:
The operator is ‘/’. We see this is an example of dividing by a power of 4 by right shifting (see Section 2.3.7). Before shifting by k = 4, we must add a bias of (2^k) − 1 = 15 when the dividend is negative.
I get that the compiler is using an optimization here, creating a temporary variable equal to x + 15, and conditionally re-setting that variable back to x if x is less than zero. What I'm wondering is why it's necessary to use a bias in the first place. What would happen if the code left out the first 3 assembly steps, like so?
sarq $4, %rax
ret
I think the answer is that we need to get rid of the twos-complement sign bits from a negative number in order to arrive at the correct answer of zero. For example, if x = -12 (i.e. 11110100), and we wanted to divide by 4, then shifting right by 4 bits without adding the bias first would equal 11111111 (or -1 in decimal form), which is not the expected answer of 0 that I'd expect from dividing -12 by 16. Instead, we add 15 to -12 to get 3 (aka 00000011), which we can then shift right by 4 bits to get 00000000, aka the correct answer of 0 in decimal form.
Is the above explanation correct? Or am I missing the mark when it comes to how and why a bias is used?
UPDATE- apparently the example assembly code in the book I'm using isn't correct. Here's the correct assembly:
arith:
testw %di, %di
leal 15(%rdi), %eax
cmovns %edi, %eax
sarw $4, %ax
ret
My larger question about why the bias is needed still stands. Is it because shifting a negative number without first adding the bias produces the incorrect result that I mentioned?
Solution 1:
Right arithmetic shifting negative values represented using two's complement performs integer division by a power of 2 with rounding toward negative infinity. This is not the semantics of the integer division in C where rounding must be performed toward 0.
In order to implement signed division by 16, your compiler biasses the numerator by 15 if it is negative and performs an arithmetic right shift by 4:
arith:
testw %di, %di // testing numerator
leal 15(%rdi), %eax // computing numerator+15 into %eax, flags unchanged
cmovns %edi, %eax // conditional move depending if numerator was negative
sarw $4, %ax // arithmetic right shift by 4 positions
ret
The code is equivalent to this:
short div16(short num) {
return (num < 0 ? num + 15 : num) >> 4;
}
Solution 2:
As mentioned earlier in rounding section of book default behavior of shifting is rounding down but in C dividing the number result in rounding towards zero. This amounts to rounding up in case of negative numbers. Thus, bias is needed to be added beforehand for negative number to result in consist behavior with C. Having 2^k - 1 (k ones) as bias value leaves no effect if number has k zeros on right but will round the number up if there is one at any place in k digits.