c - 将方程转换为位移运算

Question

是否有任何标准方法可以将（任何）方程转换为位移运算？

我的意思是把任何不是 + 或 - 的东西转换成位移，所以结束方程只包含操作数<<、>>、+ 和 -。这是为了减少公式的处理器密集度。

显然，这些结果方程只是近似值，考虑的阶数越多（一阶、二阶等），精度越高。

我已经在网上搜索了有关此的任何信息，但找不到任何信息，除了特定公式（sin、cos、inv 等）的内容。

我正在设想类似多项式或泰勒展开过程的东西，然后将其转换为位移运算。

Answer 1

仅仅因为您将某些内容简化为更简单的指令，并不意味着它们会以某种方式执行得更快或更少密集。虽然您可能能够将许多事情简化为操作的简化子集，但您可能需要更多的操作来完成相同的任务。处理器每秒只能执行这么多操作，而您将首先遇到该操作。

通常，当尝试在低级别优化某些东西时，您会尝试使用更复杂的操作码，以便您需要更少的操作码。例如，您可以通过执行许多 ADD 指令来执行乘法。但是，除了最微不足道的例子之外，它所花费的 ADD 比单个 MUL 操作码要多得多，并且执行时间要长得多。

回到您的实际问题...完全忽略效率，只要您拥有的指令集是Turing Complete ，您就可以计算任何东西。如果您小心选择该指令，您实际上可以使用单个指令计算任何内容。我不相信有任何通用的方式可以说“将任意算法转换为仅使用这些指令”，这通常是编译器编写者的工作。

Answer 2

一般不会。

在大多数 CPU 上，乘法并不比其他算术运算慢很多，因此尝试将乘法转换为位移运算没有什么意义，除了乘以 2 的恒定幂。

就除法而言，有一些众所周知的方法可以将除以常数转换为乘以倒数，这些方法非常有效。请参阅http://www.flounder.com/multiplicative_inverse.htm了解如何操作。但是，除以非常量值并不能真正优化。

当然，将 2 的幂（或一个数除以 2 的幂）很容易转换为位移。但是，其他指数不容易转换。

大多数超越函数不能在位级别上合理地表示。无论如何，大多数都没有在整数上定义，这无济于事。

Answer 3

具有按位运算的软件乘法不太可能在现代 CPU 上击败硬件乘法。

如果允许避免 1) 循环，通常进行按位操作可以产生更好的性能；2) 分支。

一本很好的在线黑客食谱。否则会有黑客的喜悦。