除以 2 的幂并向零舍入

Question

我需要仅使用按位运算符（例如 ! & ^ ~ 和移位）来计算数字 (a/(2**b)。我得到了以下提示，但我是 C 新手，我不知道代码的含义:

int bias = x>0 ? 0 : ((1<<n)-1);

谁能给我解释一下吗？

我认为 a>>b 会起作用，但我认为它不适用于负数。

Answer 1

如果 x 为正数，该特定代码位会给您带来 0 的偏差。否则，它会生成低 n 位的掩码。

x = a ? b : c;

模式在 C 中称为 三元运算符（从技术上讲，显然是“条件运算符”）。

n      (1<<n)    (1<<n)-1     binary
0        0x01       0x00     00000000
1        0x02       0x01     00000001
2        0x04       0x03     00000011
3        0x08       0x07     00000111
4        0x10       0x0F     00001111
5        0x20       0x1F     00011111
6        0x40       0x3F     00111111
7        0x80       0x7F     01111111
           ...

Answer 2

嗯，

x<<n

对于正数可以正确工作。那么你为什么不使用类似的东西

result=if sign=1 then (x<<n) else(-x<<n)

（用符号位进行一些屏蔽来替换 iftehenelse）

Answer 3

正如已经回答的那样，

? :

运算符是“三元运算符”。

?

的左侧是一个条件。 如果条件为真，则块返回

?

和

:

之间的内容，如果条件为假，则返回

:

右侧的内容。

在有符号除以 2 舍入为零的情况下。 如果分子为正，则逻辑右移给出正确的结果。 对于负（二进制补码）整数，需要做更多的工作。 第一步是用算术移位替换逻辑移位。 对于 2 的精确倍数，仍给出正确答案，但其他值向负无穷大舍入。 在这里，添加“偏差”可以纠正这个问题。

因此，对于正整数，不需要偏置，但对于负整数，必须在分子上添加 2^b - 1 的偏置。 完整的代码如下所示：

int div2(int x, int b)
{
  int bias = x>0 ? 0 : ((1<<b)-1);
  return (x+bias)>>b; // Note this only works if >> is an arithmetic shift.
}

请注意，如果 b 等于或大于 32，则必须小心，因为

(1<<b)

可能不会产生您期望的结果（下面的示例也是如此）。

在 x86 汇编语言中，您可能需要类似以下内容（我希望我的汇编知识仍然很好！）：

  ; Assume the numerator is in ECX and the value of b is in EDX for this example

  ; Prologue to preserve some extra registers
  PUSH  EBX
  PUSH  ESI

  ; Register rearrangement (only CL is valid for variable shifts)
  MOV   EAX, ECX
  MOV   CL,  DL

  ; Prepare bias mask
  MOV   ESI, 1
  SHL   ESI, CL
  SUB   ESI, 1

  ; Apply bias if numerator is negative
  XOR   EBX, EBX
  TEST  EAX, EAX
  CMOVS EBX, ESI ; Sets EBX to ESI if the sign bit is set by TEST, otherwise EBX is left as is (equal to 0)

  ; Perform arithmetic shift with bias
  ADD   EAX, EBX
  SAR   EAX, CL

  ; Epilogue
  POP   ESI
  POP   EBX

  ; Result in EAX
  RET

这是一个类似家庭作业的问题，但在编译器开发领域也很有用。

Answer 4

叹息...这是一个家庭作业问题。 该学生正在寻求有关程序员视角教科书《计算机系统》作业的帮助。

供将来参考，任何时候有人说“我只允许使用 XYZ 运算符做某事”，这可能是一个家庭作业问题。

我不认为有什么办法可以剥夺那些在家庭作业问题上寻求帮助的人的声誉，不是吗？