如何使用加减乘除来实现位运算？

Question

网上有很多位运算来实现加减乘除的例子。但有没有一种算法能够只通过加减乘除来实现位运算（AND、XOR、OR、NOT、左移、右移）？

Answer 1

以二进制为基础的计算机中一切运算基于位运算，而位运算又基于与或非三种逻辑运算。
所以只要能造出这三个逻辑算符，就能够实现各种位运算，我把它命名为“吃饱了撑的”算符集，各算符可以表示如下：

ML: A => UINT (UINT A + UINT A);  // 左移
MR: A => UINT (UINT A / 2);  // 右移

SBIT: A => UINT A - (ML (MR A)) ;  // 先除以二再乘二、再减原数值，可以将无符号数二值化，
// 当然， SBIT 在我所接触的多个库中都有提供，所以这个算符可能有点多余。

NOT: (SBIT A) => SBIT (A + 0B00000001);  // 取反
AND: (SBIT A, SBIT B) => SBIT (A * B);  // 任一为 FALSE 则返回 FALSE
OR: (SBIT A, SBIT B) => NOT((NOT A) AND (NOT B));  // 任一为 TRUE 则返回 TRUE

XOR: (SBIT A, SBIT B) => SBIT (A + B);  // 异或就是不带进位的加法，所以把进位视为溢出即可

其他所有无须中间值的算符都可以由以上算符组成。