Bit-Twiddling整理

所谓Bit-Twiddling,指的就是通过直接操作数据的字节来实现对数据的修改功能。例如,如果我们要将int类型的变量value的值变为原来的两倍,那我们既可以使用语句value *= 2,也可以使用value <<= 1的方法,后者就是Bit-Twiddling,大多数情况下,使用Bit-Twiddling的程序可以运行的更快。本文收集了一些常用的Bit-Twiddling方法。

原文链接:http://graphics.stanford.edu/~seander/bithacks.html

什么时候可以使用Bit-Twiddling?

一般来说,使用Bit-Twiddling可以加快运行速度,有时候,通过一些巧妙的设计,我们可以避免类似于ifelse的分支语句(对于CPU指令来说,分支的开销远大于普通运算指令的开销,而且分支的存在不利于CPU进行指令级的优化)。不过Bit-Twiddling的缺点就是其可读性较差,因此使用时需要仔细斟酌。

判断两个整数是否拥有不同的符号

int x, y;
bool f; // 如果x和y异号,则为true

f = ((x * y) < 0); // 常用方法

f = ((x ^ y) < 0); // 将乘法替换为异或操作,需要CPU执行的指令更少

计算一个整数的绝对值

int v;           // 计算变量v的绝对值
unsigned int r; // 保存结果

// 在这里CHAR_BIT表示一个char类型的位数(通常为8位)
int const mask = v >> sizeof(int) * CHAR_BIT - 1;

// 常规方法,使用了分支
r = v > 0 ? v : -v;

// 下面两种方法均可以直接计算出绝对值
r = (v + mask) ^ mask;
r = (v ^ mask) - mask;

上面的方法把分支的逻辑隐藏在计算mask的过程中了。如果v > 0,那么最终mask == 0xffffffff,否则mask == 0x0。借助异或的性质,巧妙的完成了绝对值的求解过程。感兴趣的读者可以自己代入一些数值来试一试。具体为什么这样写可以计算绝对值,就需要大家好好推敲了,这篇文章主要以收集和整理为主要目的。

判断一个整数是否是2的幂

unsigned int v;     // 需要判断v是否是2的幂,例如1,2,4,8,16等
bool f; // 如果v是2的幂,则为true

f = (v & (v - 1)) == 0;
// 上面的方法在v==0时也成立(0不是2的幂),为了排除0值,我们可以使用下面的方法
f = v && !(v & (v - 1));

v & (v - 1)这个操作会将变量v的最低位的1置为0。在bit-twidding种,会遇到很多类似的方法。

计算一个整数和另一个2次幂整数的余数

我们可以注意到大多数人在决定数组的长度时都喜欢使用2次幂的值,例如256,1024。这是因为对于这些数,求模运算变得很简单。

const unsigned int n;           // 需要求模的数
const unsigned int d = 1U << s; // 在这里d是2次幂的整数,例如1,2,4,8,16,32等
unsigned int m; // m = n % d
m = n & (d - 1);

使用异或的方式来交换两个变量的值

#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))

上面的方法可以避免申请额外的空间,也是借助了异或的性质

对于整数v,计算大于v的最小2次幂数

这类需求最常见于分配空间时,例如有时候我们需要向系统申请1000字节的空间,但是系统为了让数据对齐,实际上给我们分配了1024字节的空间,也就是$2^{10}$字节。类似这样的需求都需要计算大于整数v的最小2次幂数。

unsigned int v; // 计算变量v的下一个2次幂数

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

上面的方法适用于32-bit的无符号整数,对于64-bit字节的整数,只需要额外添加语句v |= v >> 32就可以了。

此文有用? 求鼓励!

显示 Gitment 评论