按位运算符（移位除外）在以 10 为基数时有任何数学意义吗？

Question

根据 wiki 移位可用于计算 2 的幂：

算术左移 n 为 相当于乘以 2^n （前提是该值不 溢出），而正确的算术 将二进制补码值移位 n 相当于除以 2^n 并且 向负无穷大舍入。

我一直想知道是否还有其他按位运算符（~、|、&、^）可以进行数学运算应用于以 10 为基数时有意义吗？我了解它们是如何工作的，但是此类运算的结果可以用来计算十进制世界中有用的东西吗？

Answer 1

"yep base-10 is what I mean"

在这种情况下，是的，它们可以通过多种方式扩展到以 10 为基数，尽管它们并不像二进制那样有用。

一种想法是 &、| 等与对各个二进制数字进行算术 mod-2 相同。如果 a 和 b 是单个二进制数字，那么

a & b = a * b (mod 2)
a ^ b = a + b (mod 2)
   ~a = 1-a   (mod 2)
a | b = ~(~a & ~b) = 1 - (1-a)*(1-b) (mod 2)

以 10 为基数的等价物将是 （再次注意，这些应用于每个数字，而不是整个数字） number）

a & b = a * b (mod 10)
a ^ b = a + b (mod 10)
   ~a = 9-a   (mod 10)
a | b = ~(~a & ~b) = 9 - (9-a)*(9-b) (mod 10)

前三个在设计使用 BCD 的电路时很有用（< code>~a 是 9 的补码），例如非- 图形计算器，尽管我们在编写方程时只使用 * 和 + 而不是 & 和 ^。第一个显然也用于一些旧密码。

Answer 2

在没有临时变量的情况下交换两个整数的一个有趣技巧是使用按位 XOR：

void swap(int &a, int &b) {
   a = a ^ b;
   b = b ^ a; //b now = a
   a = a ^ b; //knocks out the original a
}

这有效，因为 XOR 是可交换的，所以 a ^ b ^ b = a。

Answer 3

是的，还有其他有用的运算，但它们往往面向涉及 2 的幂的运算（出于明显的原因），例如测试奇数/偶数、测试 2 的幂、向上/向下舍入到最接近的 2 的幂等 。

请参阅 Henry S. Warren 的黑客之乐

Answer 4

在我使用过的每种语言中（诚然，几乎都是 C 语言和 C 派生语言），按位运算符都是整数运算（当然，除非您重写该运算）。

虽然您可以调整十进制数的位（毕竟它们有自己的位），但它不一定会得到与调整整数位相同的结果。请参阅单精度和双精度 用于描述十进制数中的位。请参阅快速平方反根，了解位旋转十进制数的有利用法的示例。

编辑

对于整数，按位运算总是有意义的。按位运算是为整数设计的。

n << 1 == n * 2
n << 2 == n * 4
n << 3 == n * 8

n >> 1 == n / 2
n >> 2 == n / 4
n >> 3 == n / 8

n & 1 == {0, 1}       // Set containing 0 and 1
n & 2 == {0, 2}       // Set containing 0 and 2
n & 3 == {0, 1, 2, 3} // Set containing 0, 1, 2, and 3

n | 1 == {1, n, n+1}
n | 2 == {2, n, n+2}
n | 3 == {3, n, n+1, n+2, n+3}

等等。

Answer 5

您可以仅使用按位运算符计算对数...

使用按位运算求 n = 2**x 的指数 [n 以 2 为底的对数]

Answer 6

有时您可以用按位运算代替布尔运算。例如，以下代码：

if ((a < 0) && (b < 0)
{
  do something
{

在 C 中，可以将其替换为： 这是

if ((a & b) < 0)
{
  do something
{

有效的，因为整数中的一位用作符号位（1 表示负）。与运算（a & b）将是一个无意义的数字，但其符号将是数字符号的按位与，因此检查结果的符号将起作用。

这可能会也可能不会有利于性能。在许多架构和编译器上进行两个布尔测试/分支会更糟。即使使用正常语法，现代 x86 编译器也可能使用一些较新的指令生成单个分支。

与往常一样，如果它确实导致性能提高...注释代码 - 即在注释中添加“正常”的执行方式，并说它是等效的但更快。

同样，〜|和 ^ 可以以类似的方式使用，只要所有条件都是（x＜0）。
对于比较条件，您通常可以使用减法：

if ((a < b) | (b < c))
{
}

变为：，

if (((a-b) | (b-c)) < 0)
{
}

因为仅当 a 小于 b 时 ab 才会为负数。如果您的值在 max int 的 2 倍之内，即算术溢出，则可能会出现问题，因此请小心。

在某些情况下，这些优化是有效的，但在其他情况下则毫无用处。并且变得非常丑陋，浮点数也有符号位......;-)

示例：
举个例子，假设您想根据 a、b、c 的顺序采取行动。您可以执行一些嵌套的 if/else 构造，或者您可以这样做：

x = ((a < b) << 2) | ((b < c) << 1) | (c < a);
switch (x):

我在代码中使用了最多 9 个条件，并且还使用上面提到的减法和额外的逻辑来隔离符号位而不是小于。它比等效的分支更快。但是，您不再需要进行减法和符号位提取，因为标准很久以前就已更新，将 true 指定为 1，并且通过条件移动等，现在实际的小于可以非常有效。