为什么有必要为除以 2 的幂的有符号除法添加一个偏差?
Why is it necessary to add a bias to the dividend for signed division by a power of 2?
我在《Computer Systems-A Programmer's Perspective》学习汇编代码,遇到了如下例子:
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 , %rax
ret
What operation is OP?
后来书上给出了如下答案:
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 个组装步骤,会发生什么情况?
sarq , %rax
ret
我认为答案是我们需要从负数中去掉二进制补码符号位才能得到正确的零答案。例如,如果 x = -12(即 11110100),并且我们想除以 4,则右移 4 位 而不先添加偏置 将等于 11111111(或 -1 in十进制形式),这不是我期望将 -12 除以 16 得到的 0 的预期答案。相反,我们将 15 加到 -12 得到 3(又名 00000011),然后我们可以将其右移 4 位到得到 00000000,也就是十进制形式的 0 的正确答案。
以上解释是否正确?还是在谈到如何以及为何使用偏差时,我错过了标记?
更新-显然我正在使用的书中的示例汇编代码不正确。这是正确的程序集:
arith:
testw %di, %di
leal 15(%rdi), %eax
cmovns %edi, %eax
sarw , %ax
ret
我关于为什么需要偏见的更大问题仍然存在。是否因为在不先添加偏差的情况下移动负数会产生我提到的不正确结果?
使用二进制补码表示的负值右算术移位执行整数除以 2 的幂并向负无穷大舍入。这不是 C 中整数除法的语义,其中必须向 0 舍入。
为了实现除以 16 的有符号除法,如果分子为负数,您的编译器会将分子偏置 15,并执行算术右移 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 , %ax // arithmetic right shift by 4 positions
ret
代码等同于:
short div16(short num) {
return (num < 0 ? num + 15 : num) >> 4;
}
如前所述,在本书的默认舍入部分中,移位的默认行为是向下舍入,但在 C 中除以数字会导致向零舍入。这相当于在负数的情况下四舍五入。因此,需要预先为负数添加偏差,以导致与 C 一致的行为。
如果数字右边有 k 个零,则将 2^k - 1(k 个)作为偏置值不会产生任何影响,但如果 k 位数字中的任何位置都有一个,则会将数字向上舍入。
我在《Computer Systems-A Programmer's Perspective》学习汇编代码,遇到了如下例子:
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 , %rax ret
What operation is OP?
后来书上给出了如下答案:
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 个组装步骤,会发生什么情况?
sarq , %rax
ret
我认为答案是我们需要从负数中去掉二进制补码符号位才能得到正确的零答案。例如,如果 x = -12(即 11110100),并且我们想除以 4,则右移 4 位 而不先添加偏置 将等于 11111111(或 -1 in十进制形式),这不是我期望将 -12 除以 16 得到的 0 的预期答案。相反,我们将 15 加到 -12 得到 3(又名 00000011),然后我们可以将其右移 4 位到得到 00000000,也就是十进制形式的 0 的正确答案。
以上解释是否正确?还是在谈到如何以及为何使用偏差时,我错过了标记?
更新-显然我正在使用的书中的示例汇编代码不正确。这是正确的程序集:
arith:
testw %di, %di
leal 15(%rdi), %eax
cmovns %edi, %eax
sarw , %ax
ret
我关于为什么需要偏见的更大问题仍然存在。是否因为在不先添加偏差的情况下移动负数会产生我提到的不正确结果?
使用二进制补码表示的负值右算术移位执行整数除以 2 的幂并向负无穷大舍入。这不是 C 中整数除法的语义,其中必须向 0 舍入。
为了实现除以 16 的有符号除法,如果分子为负数,您的编译器会将分子偏置 15,并执行算术右移 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 , %ax // arithmetic right shift by 4 positions
ret
代码等同于:
short div16(short num) {
return (num < 0 ? num + 15 : num) >> 4;
}
如前所述,在本书的默认舍入部分中,移位的默认行为是向下舍入,但在 C 中除以数字会导致向零舍入。这相当于在负数的情况下四舍五入。因此,需要预先为负数添加偏差,以导致与 C 一致的行为。 如果数字右边有 k 个零,则将 2^k - 1(k 个)作为偏置值不会产生任何影响,但如果 k 位数字中的任何位置都有一个,则会将数字向上舍入。