开发人员应该知道哪些有用的位运算符代码技巧?[关闭]

看到著名的 Bit Twiddling Hacks
大多数乘法/除法运算都是不必要的——编译器会自动执行,你只会把人弄糊涂。

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

对字符串(字符)使用位操作

将字母转换为 小写字母 :

• OR 作者space=> (x | ' ')
• 结果总是小写的,即使字母已经是小写的
• 如。 ('a' | ' ') => 'a' ; ('A' | ' ') => 'a'

将字母转换为 大写字母 :

• AND 按下划线=> (x & '_')
• 结果始终为大写,即使字母已为大写
• 如。 ('a' & '_') => 'A' ; ('A' & '_') => 'A'

使转化 信函案:

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

信 位置 字母表:

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

收到信 位置 字母表(用于 大写字母 仅限字母):

• 和 通过 ? = & gt; (x & '?') 或 异或 通过 @ = & gt; (x ^ '@')
• 如。 ('C' & '?') => 3 ; ('Z' ^ '@') => 26

收到信 位置 字母表(用于 小写字母 仅限字母):

• 异或 背靠背/ chr(96) / binary('1100000') / hex('60') = & gt; (x ^ '`')
• 如。 ('d' ^ '`') => 4 ; ('x' ^ '`') => 25

注意:使用英文字母以外的任何字符都会产生垃圾结果。

• 整数的位运算(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;

除以2的m次幂

n >> m;

检查奇数

(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;

模2^n对m

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;

我只使用过三种频率:

1. 设置一点: A=1位

2. 澄清一点: A&=~(1位);

3. 测试是否设置了位: A&(1位)

Matters Computational: Ideas, Algorithms, Source Code, by Jorg Arndt (PDF) . 这本书有很多东西,我是通过一个链接找到的。 http://www.hackersdelight.org/

无溢出的平均值

一种计算平均值(x+y)/2的程序。 参数x和y是

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);
}

您可以压缩数据,例如整数集合:

• 查看哪些整数值在集合中出现得更频繁
• Use short bit-sequences to represent the values which appear more frequently (以及表示出现频率较低的值的较长位序列)
• 连接位序列:例如,结果位流中的前3位可能表示一个整数,然后接下来的9位表示另一个整数,等等。

我使用位运算符有效地实现了 bitstrings . 在我的应用程序中,位串被用来表示离散空间中的位置(一个 octree ,如果你感兴趣,用 Morton ordering )需要进行距离计算,以了解网格上的点是否在特定半径内。

计算集合位、查找最低/最高集合位、从顶部/底部集合位和其他位中查找n是有用的,值得一看 bit-twiddling hacks 站点。

这就是说,这种事情并不重要。有一个库很有用,但即使这样,最常见的用法也是间接的(例如使用位集容器)。此外,理想情况下,这些将是标准的库函数——许多函数在某些平台上使用专门的CPU指令更好地处理。

1)除以/乘以2的幂

foo >>= x; (除以2的幂)

foo <<= x; (乘以2的幂)

2)互换

x ^= y;
y = x ^ y;
x ^= y;

虽然乘/除移位看起来很漂亮,但我偶尔只需要把布尔压缩成比特。为此,您需要位和/或,以及位移位/反转。

我想用一个函数把数字四舍五入到下一个最大的二次幂,所以我访问了几次被提到的Bit Twidling网站,并提出了这个问题:

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

我用它 size_t 类型。它在签名类型上可能不太好用。如果您担心不同大小类型的平台的可移植性,请在代码中添加 #if SIZE_MAX >= (number) 在适当的地方发布指令。