算术优化

Question

如何优化以下（将算术转换为位操作）？

优化：

• int A = B * 4
• int A = B * 72
• int A = B % 1
• int A = B % 16
• int A = (B + C) / 2
• int A = (B * 3) / 8
• int A = (B % 8) * 4

在面试中看到了这些问题。

Answer 1

面试官可能正在寻找您将算术转换为位运算的能力，并认为这会更快。编译器将执行优化，因此您无需优化任何内容。如果您没有优化编译器，那么正确的做法是分析您的代码以查看性能瓶颈所在并修复它们。算术不太可能成为你的性能瓶颈。

也就是说，这可能是面试官要找的：

• B * 4，乘以2的幂可以使用位移运算来执行，例如B << 2。这实现了相同的结果。
• B * 72，这个其实是B * 8 * 9，也就是B * 2^3 * (2^3 + 1) = (B*2^6) + (B*2^3)。同样，解决方案是找到 2 的幂并使用移位操作写入它们。 (B << 6) + (B << 3) 等同于 B * 72
• B % 16，始终是 0-15 范围内的数字（如果 B 为正数）这是要求整数的最后 4 位，可以使用位掩码找到：B & 0xF.
• 等等

请注意，在每种情况下，代码的含义都更难理解。 B * 72 比 (B << 6) + (B << 3) 更易读。这种试图挑剔代码性能而不实际分析任何东西的过程称为过早优化。如果你分析你的代码并发现它的性能瓶颈确实是这些数学运算，那么你可以以优化的形式重写它们，但是你必须记录代码的含义以便下一个看到它的人理解为什么代码如此混乱.

我会注意到，如果我是问这个问题的面试官（而且我不会问这个问题），我更愿意回答 "let the compiler do the optimizations" 而不是盲目地寻找表达算术的按位方式。

Answer 2

所有这些计算都可以通过位移来完成；但是，这只适用于正数。我们需要有一个负输入的特例，因为面试官没有指定是哪一个！

---

1. 乘以4 = 2²可以通过左移2位来完成

   int A = (B < 0) ? -((-B) << 2)) : B << 2;

   负数直接移位会溢出，结果不对，所以我们对负数进行运算

---

2. 72 = 64 + 8 = 2⁶ + 2³。因此：

   int A = (B < 0) ? -(((-B) << 6) + ((-B) << 3)) : (B << 6) + (B << 3)

---

3. C++标准中负数的模等价于：

   neg_number % N = -((-neg_number) % N);（自己测试）

   但这对模数加1没有影响！因此 int A = 0;

---

4. 使用 AND (&) 正如 Welbog 所说：

   int A = (B < 0) ? -((-B) & 0xF) : B & 0xF;

---

5. 和前面说的一样，但是求和；使用右移 1:

   int A = (B + C < 0) ? -((-(B+C)) >> 1) : (B + C) >> 1;

---

6. int A = (B < 0) ? -(((-B) << 1 - B) >> 3) : (B << 1 + B) >> 3;

---

7. int A = (B < 0) ? -(((-B) & 7) << 2) : (B & 7) << 2;