C/C++ 位操作技巧

Question

为了遵循graphics.stanford.edu/~seander/bithacks.html的精神，我需要解决以下问题：

int x; 
int pow2; // always a positive power of 2
int sgn;  // always either 0 or 1
// ...
// ...
if(sgn == 0)
    x -= pow2;
else
    x += pow2;

当然我需要避免使用条件语句。到目前为止，我想出的最好方法是

x -= (1|(~sgn+1))*pow2

但那涉及到一个我也想避免的乘法。提前感谢。

编辑：谢谢大家。

x -= (pow2^-sgn) + sgn

看起来这个方法可以解决问题！

- fs.

---

当乘法不是问题时，我们还可以使用以下公式：x -= (1-2*sgn)*pow，其中映射关系为 0 -> 1 和 1 -> -1，等价于 x -> (1-2x)。 - rafak

再一次，括号的作用！^ 的优先级低于 +，因此 x -= pow2^-sgn + sgn 就是 x -= pow2^(-sgn+sgn) 等同于 x -= pow2。 - lijie

Answer 1

我会尝试。

x -= (pow2 ^ (~sgn+1)) + sgn

或者，如评论中lijie所建议的

x -= (pow2 ^ -sgn) + sgn

如果 sgn 是 0，那么 ~sgn+1 也是 0，所以有 pow2 ^ (~sgn+1) == pow2。如果 sgn 是 1，那么 (~sgn+1) 就是 0xFFFFFFFF，并且 (pow2 ^ (~sgn+1)) + sgn == -pow2。

- Sven Marnach

---

你可以将~sgn+1改为-sgn。 - lijie

哦，是的。^ 的优先级低于 +，因此我建议使用括号。 - lijie

@steve314：是的，我同意2的补码并非强制要求。然而，整个表达式（不仅是~sgn+1部分）都是基于2的补码前提的（否则条件无法替换）。建议替换是基于“一个操作比两个操作更好”的推理；取反可能与加法一样快，所以倒置是浪费时间。 - lijie

@lijie：即使平台不使用二进制补码，条件语句也可以被替换--请参考Paul和EboMike的答案。 - Sven Marnach

@sven：我同意。然而，保罗和ebomike的答案都依赖于-1被表示为所有的1。但是，例如，x += (sgn*2-1)*pow2可以去掉条件语句。那么，除非假定涉及的数字的某些表示形式，否则说乘法是不可避免的，这是一个有效的陈述吗？ - lijie

Answer 2

mask = sgn - 1; // generate mask: sgn == 0 => mask = -1, sgn == 1 => mask = 0

x = x + (mask & (-pow2)) + (~mask & (pow2)); // use mask to select +/- pow2 for addition

- Paul R

---

@Sven：不，& 是一个按位运算符。 - Paul R

@Sven：不是的-如果你不相信我，请查看编辑历史记录-有一个“|”，我用“+”替换了它，但没有条件语句。 - Paul R

@Sven：首先(sgn == 0)不是条件语句，而是一个（无分支）测试操作。其次，当我重新阅读问题并看到sgn只能取值0和1时，我将其删除，从而使测试操作变得不必要。所以正如我所说，从来没有任何条件语句，也没有人玩任何游戏——你只是犯了一个简单的错误。 - Paul R

我称之为“模棱两可”- ==经常被称为条件运算符，但显然不是（编辑：本身）有选择性执行的条件运算符。 - user180247

@Steve314：任何称==为条件运算符的人都是误导 - 它的正确名称是等于运算符。它肯定不意味着分支，这是此上下文中性能的主要问题。 - Paul R

Answer 3

我随口说一下：

int subMask = sgn - 1;
x -= pow2 & subMask;
int addMask = -sgn;
x += pow2 & addMask;

无法保证其是否有效或是否明智，这只是我突然想到的一个随机想法。

编辑：让它更加紧凑（也就是更加简洁）：

x += (pow2 & -sgn) - (pow2 & (sgn-1)); 

- EboMike

Answer 4

我会改变接口，用左移位代替乘法。（使用指数而非 pow2）

- stacker

Answer 5

你可以像这样做（来自链接）： x += ((pow2 ^ -sgn) + sgn)

- Rajivji