69

我必须说我从来没有理由使用按位运算符，但我确信我执行的某些操作会更有效地完成。“shifting”和“OR-ing”如何帮助您更有效地解决问题？

4

11 回答 11

152

对字符串（字符）使用按位运算

将字母转换为小写：

  • OR按空间 =>(x | ' ')
  • 即使字母已经是小写，结果也总是小写
  • 例如。('a' | ' ') => 'a';('A' | ' ') => 'a'

将字母转换为大写：

  • AND通过下划线 =>(x & '_')
  • 即使字母已经是大写，结果也总是大写
  • 例如。('a' & '_') => 'A';('A' & '_') => 'A'

反转字母的大小写：

  • XOR按空间 =>(x ^ ' ')
  • 例如。('a' ^ ' ') => 'A';('A' ^ ' ') => 'a'

字母在字母表中的位置：

  • AND通过chr(31)/ binary('11111')/( hex('1F')=>(x & "\x1F")
  • 结果在 1..26 范围内，字母大小写不重要
  • 例如。('a' & "\x1F") => 1;('B' & "\x1F") => 2

获取字母在字母表中的位置（仅适用于大写字母）：

  • AND通过?=>(x & '?') 或 XOR通过@ =>(x ^ '@')
  • 例如。('C' & '?') => 3;('Z' ^ '@') => 26

获取字母在字母表中的位置（仅适用于小写字母）：

  • XOR通过反引号/ chr(96)/ binary('1100000')/ hex('60') =>(x ^ '`')
  • 例如。('d' ^ '`') => 4;('x' ^ '`') => 25

注意：使用除英文字母以外的任何内容都会产生垃圾结果

于 2013-04-23T17:51:33.607 回答
68
  • 整数的按位运算（int）

获取最大整数

int maxInt = ~(1 << 31);
int maxInt = (1 << 31) - 1;
int maxInt = (1 << -1) - 1;

获取最小整数

int minInt = 1 << 31;
int minInt = 1 << -1;

获得最大长

long maxLong = ((long)1 << 127) - 1;

乘以 2

n << 1; // n*2

除以 2

n >> 1; // n/2

乘以 2 的 m 次方

n << m; // (3<<5) ==>3 * 2^5 ==> 96

除以 2 的 m 次方

n >> m; // (20>>2) ==>(20/( 2^2) ==> 5

检查奇数

(n & 1) == 1;

交换两个值

a ^= b;
b ^= a;
a ^= b;

获取绝对值

(n ^ (n >> 31)) - (n >> 31);

获取两个值的最大值

b & ((a-b) >> 31) | a & (~(a-b) >> 31);

获取两个值的最小值

a & ((a-b) >> 31) | b & (~(a-b) >> 31);

检查两者是否具有相同的符号

(x ^ y) >= 0;

计算 2^n

2 << (n-1);

是否为2的阶乘

n > 0 ? (n & (n - 1)) == 0 : false;

对 m 取模 2^n

m & (n - 1);

获取平均值

(x + y) >> 1;
((x ^ y) >> 1) + (x & y);

获取n的第m位（从低到高）

(n >> (m-1)) & 1;

将 n 的第 m 位设置为 0（从低到高）

n & ~(1 << (m-1));

n + 1

-~n

n - 1

~-n

获取对比号

~n + 1;
(n ^ -1) + 1;

如果 (x==a) x=b; 如果 (x==b) x=a;

x = a ^ b ^ x;
于 2014-11-25T10:10:56.017 回答
47

查看著名的Bit Twiddling Hacks
大多数乘法/除法是不必要的 - 编译器会自动执行此操作，您只会迷惑人们。

但是，如果您使用硬件或通信协议，有一堆“检查/设置/切换位 N”类型的黑客非常有用。

于 2009-10-07T18:38:25.793 回答
15

我曾经以任何频率使用过的只有三个：

  1. 设置一点： a |= 1 << bit;

  2. 稍微清楚一点： a &= ~(1 << bit);

  3. 测试是否设置了位： a & (1 << bit);

于 2009-10-08T22:13:16.170 回答
10

Matters Computational: Ideas, Algorithms, Source Code, by Jorg Arndt (PDF)。这本书包含大量内容，我通过http://www.hackersdelight.org/的链接找到了它

平均无溢出

计算两个参数 x 和 y 的平均值 (x + y)/2 的例程是

static inline ulong average(ulong x, ulong y)
// Return floor( (x+y)/2 )
// Use: x+y == ((x&y)<<1) + (x^y)
// that is: sum == carries + sum_without_carries
{
    return (x & y) + ((x ^ y) >> 1);
}
于 2011-12-14T08:52:26.487 回答
2

1）除以/乘以2的幂

foo >>= x;（除以 2 的幂）

foo <<= x;（乘以 2 的幂）

2) 交换

x ^= y;
y = x ^ y;
x ^= y;
于 2009-10-07T17:51:37.217 回答
2

您可以压缩数据，例如整数集合：

  • 查看哪些整数值在集合中出现的频率更高
  • 使用短位序列表示出现频率较高的值（使用较长的位序列表示出现频率较低的值）
  • 连接位序列：例如，结果位流中的前 3 位可能表示一个整数，然后接下来的 9 位表示另一个整数，等等。
于 2009-10-07T18:30:25.233 回答
1

我使用位运算符来有效地实现位串的距离计算。在我的应用程序中，位串用于表示离散空间中的位置（如果您有兴趣，使用Morton ordering编码的octree）。距离计算需要知道网格上的点是否落在特定半径内。

于 2009-10-07T18:35:51.027 回答
1

计算设置位、查找最低/最高设置位、从顶部/底部查找第 n 个设置位等可能很有用，值得查看bit-twiddling hacks站点。

也就是说，这种事情并不重要。拥有一个库很有用，但即便如此，最常见的用途也是间接的（例如，使用 bitset 容器）。此外，理想情况下，这些将是标准库函数——在某些平台上，使用专门的 CPU 指令可以更好地处理其中的许多函数。

于 2009-10-07T18:37:47.403 回答
0

虽然通过移位进行乘法/除法看起来很漂亮，但我偶尔需要的只是将布尔值压缩为位。为此，您需要按位与/或，并且可能需要位移/反转。

于 2009-10-07T17:57:19.370 回答
0

我想要一个函数来将数字四舍五入到 2 的下一个最高幂，所以我访问了 Bit Twiddling 网站，该网站已经被多次提出并提出了这个：

i--;
i |= i >> 1;
i |= i >> 2;
i |= i >> 4;
i |= i >> 8;
i |= i >> 16;
i++;

我在一个size_t类型上使用它。它可能在签名类型上效果不佳。如果您担心到具有不同大小类型的平台的可移植性，请#if SIZE_MAX >= (number)在适当的地方使用指令散布您的代码。

于 2009-10-08T22:03:58.633 回答