为什么有必要在有符号除法的红利上加2的偏倚? [英] 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:

在下面的C函数中，我们保留了操作的定义OP不完整:

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

在编译时，gcc会生成以下汇编代码:

When compiled, gcc generates the following assembly code:

arith:
  leaq    15(%rdi), %rax
  testq   %rdi, %rdi
  cmovns  %rdi, %rax
  sarq    $4, %rax
  ret

OP是什么操作?

后来，这本书给出了以下答案:

Later, the book gives the following answer:

运算符为"/".我们看到这是除以幂的一个例子通过右移4位(请参阅第2.3.7节).在移动k = 4之前当股息为负时，我们必须添加(2 ^ k)− 1 = 15的偏差.

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.

我知道编译器在这里使用优化，创建一个等于x + 15的临时变量，如果x小于零，则有条件地将该变量重新设置为x.我想知道的是为什么首先需要使用偏见.如果这样的代码遗漏了前3个汇编步骤，会发生什么情况?

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

我认为的答案是，我们需要摆脱负数的二进制补码符号位，才能得出正确的答案为零.例如，如果x = -12(即11110100)，并且我们想除以4，则向右移4位而不先添加偏差将等于11111111(或十进制形式的-1)，这不是我将-12除以16所期望的0的预期答案.相反，我们将-12加15以获得3(又称00000011)，然后我们可以将其右移4位以获得00000000，亦即十进制形式的正确答案0.

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?

推荐答案

使用二进制补码表示的负数右移算术运算将整数除以2的幂，并朝负无穷大舍入.这不是C中整数除法的语义，在整数除法中必须向0舍入.

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.

为了实现16的有符号除法，编译器在分子为负数时将分子偏差为15，并执行算术右移4:

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

代码等效于此:

short div16(short num) {
    return (num < 0 ? num + 15 : num) >> 4;
}

这篇关于为什么有必要在有符号除法的红利上加2的偏倚?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！