这篇文章转自http://graphics.stanford.edu/~seander/bithacks.html,作者收集了一系列巧妙的bit运算技巧,并亲自验证通过,转载于此并做了部分精简

·获得整数的符号

int v;      // 我们想获得v的符号,并把结果放入sign中
int sign;   
 
//CHAR_BIT是一个字节的bit数,在IA32架构中是8
 
// if v < 0 then -1, else 0.
sign = –(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT1));
// if v < 0 then -1, else +1
sign = +1 | (v >> (sizeof(int) * CHAR_BIT1))
// -1, 0, or +1
sign = (v != 0) | –(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT1));
// if v < 0 then 0, else 1
sign = 1 ^ ((unsigned int)v >> (sizeof(int) * CHAR_BIT1));

·不用分支计算绝对值(abs)

int v;           // 需要计算绝对值的变量
unsigned int r// 结果
int const mask = v >> (sizeof(int) * CHAR_BIT1);
 
r = (v + mask) ^ mask;
r = (v ^ mask)mask//这两个版本效果是等同的

·不用分支计算最大或者最小值

int x,y// 我们需要计算的变量
int r// 结果
 
r = y ^ ((x ^ y) & –(x < y)); // min(x, y)
r = x ^ ((x ^ y) & –(x < y)); // max(x, y)
//如果你确保 INT_MIN <= x-y <= INT_MAX,那么可以用下面的方法,速度更快
r = y + ((xy) & ((xy) >> (sizeof(int) * CHAR_BIT1))); // min(x, y)
r = x((xy) & ((xy) >> (sizeof(int) * CHAR_BIT1))); // max(x, y)

·判断是否是2的幂方

unsigned int v; // 我们要检测的数据
bool f;         // 结果
 
f = ((v & (v1)) == 0);
//需要注意的是,上面的方法对于0得到的结果是错误的,0不应该时为2的幂方,修正后的算法如下
f = v && !(v & (v1));

·扩展变量的bit位

变量所占用的bit位扩展其实属于编译器的内置功能,比如我们经常会碰到char、short、int变量互相变换,但有时候我们在一些特殊场合可能会用到一些奇怪长度的变量,比如用4个bit来表示一个整数,距离来说,-3在8bit的时候的值是11111101,但如果用4个bit,那么就是1101,下面这段代码展示的是如何把5bit长度的数据扩展为一个int.

int x; // 需要转换的5bit长度的数据
int r; // 转换后的结果
struct {signed int x:5;} s;
r = s.x = x;
 
//利用C++的模板特性的代码
template <typename T, unsigned B>
inline T signextend(const T x)
{
 
struct {T x:B;} s;
 
return s.x = x;
}
 
int r = signextend<signed int,5>(x)// 将5bit长度的带符号整数赋值个r

·动态扩展变量的bit位

某些情况下变量的bit长度不是编译期间决定的,那么就需要动态的扩展

unsigned b; // 需要扩展的变量
int x;      // 变量b的bit长度
int r;      // 结果
int const m = 1U << (b1);
 
x = x & ((1U << b)1)//如果变量b除了有效bit之外已经全都是0,那么可以忽略这一步
r = (x ^ m)m;

·根据条件设置变量特定bit位的值

如果我们需要根据某种条件设置一个变量中某个特定bit位置的值,比如用一个int来保存32个开关状态,那么可以用到下面的代码

bool f;         // 输入条件
unsigned int m; // 需要设置的bit位的mask
unsigned int w; // 需要进行设置的变量,最终我们要得到这样的结果:  if (f) w |= m; else w &= ~m;
 
w ^= (f ^ w) & m;
 
// 或者用下面的代码,可以被编译器优化为并行代码
w = (w & ~m) | (f & m);

·根据条件对某个变量取负值

bool f// 决定是否该取负值的条件标志
int v;   // 输入的变量
int r;   // 结果
 
r = (f^ (f1)) * v;   // result = f? v : -v;
r = (v ^ –f) + f;      // result = f? -v : v;

·根据mask合并两个数值

unsigned int a;    // 原有的变量
unsigned int b;    // 需要根绝mask合并的变量
unsigned int mask; // mask中设为1表示b对应位置的数据合并到a上,否则不合并
unsigned int r;    // 结果
 
r = (a & ~mask) | (b & mask); //原始方法
r = a ^ ((a ^ b) & mask)//这个方法减少了一个op,但如果mask是一个编译期间确定的数值,那么优势就没有了

·计算变量中bit位是1的个数(原始方法)

unsigned int v; // 需要计算变量v的二进制形式里1的个数,例如如果v=105(1101001),那么结果是4
unsigned int c; // 结果
 
for (c = 0; v; v >>= 1)
{
 
c += v & 1;
}

·计算变量中bit位是1的个数(查表法)

static const unsigned char BitsSetTable256[256] =
{
#   define B2(n) n,     n+1,     n+1,     n+2
#   define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#   define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
    
B6(0), B6(1), B6(1), B6(2)
};
 
unsigned int v; // 需要计算变量v的二进制形式里1的个数
unsigned int c; // 结果
 
// 方法 1:
c = BitsSetTable256[v & 0xff] +
    
BitsSetTable256[(v >> 8) & 0xff] +
    
BitsSetTable256[(v >> 16) & 0xff] +
    
BitsSetTable256[v >> 24];
 
// 方法 2:
unsigned char * p = (unsigned char *) &v;
c = BitsSetTable256[p[0]] +
    
BitsSetTable256[p[1]] +
    
BitsSetTable256[p[2]] +   
    
BitsSetTable256[p[3]];
 
 
// 使用算法初始化BitsSetTable256表
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++)
{
 
BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}

·计算变量中bit位是1的个数(Brian Kernighan法)

这个方法出现在1988年第二版的《C Programming Language》的练习题里,作者Brian Kernighan和Dennis Ritchie

unsigned int v; // 需要计算变量v的二进制形式里1的个数
unsigned int c; // 结果
for (c = 0; v; c++)
{
 
v &= v1; // 清掉最后一个为1的bit位
}

·计算变量中bit位是1的个数(利用64位指令)

unsigned int v; // 需要计算变量v的二进制形式里1的个数
unsigned int c; // 结果
 
// 方法1, 适用于14bit长度的整数
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;
 
// 方法2, 适用于24bit长度的整数
c((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
 
// 方法3, 适用于32bit长度的整数
c((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

这些方法需要64位CPU的支持,方法1编译后是3个指令,方法2是10个指令,方法3是15个指令,

·计算变量中bit位是1的个数(并行法)

unsigned int v; // 需要计算变量v的二进制形式里1的个数
unsigned int c; // 结果
static const int S[] = {1, 2, 4, 8, 16};
static const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};
 
c = v((v >> 1) & B[0]);
c = ((c >> S[1]) & B[1]) + (c & B[1]);
c = ((c >> S[2]) + c) & B[2];
c = ((c >> S[3]) + c) & B[3];
c = ((c >> S[4]) + c) & B[4];
 
//经过优化,上面的代码可以变成下面的形式
v = v((v >> 1) & 0x55555555);                    // 利用输入的变量作为临时内存
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // 结果
//上面的代码可以视为速度最快的针对32bit整数的算法了,因为它编译后只有12个指令,和查表法等同,但又避免了内存操作,只用寄存器就可以完成

·计算变量中非零bit位的奇偶性(原始方法)

这个算法的结果是获得一个变量转换成二进制之后,bit位为1的个数的奇偶性,比如9转换为二进制位1001,那么结果应该是偶数

unsigned int v; // 需要计算变量v的二进制形式里1的个数的奇偶性
bool parity = false// 结果,true表示为奇数
 
while (v)
{
 
parity = !parity;
 
v = v & (v1);
}

这个算法其实利用了上面的Brian Kernighan法算法

·计算变量中非零bit位的奇偶性(查表法)

static const bool ParityTable256[256] =
{
#   define P2(n) n, n^1, n^1, n
#   define P4(n) P2(n), P2(n^1), P2(n^1), P2(n)
#   define P6(n) P4(n), P4(n^1), P4(n^1), P4(n)
    
P6(0), P6(1), P6(1), P6(0)
};
 
unsigned char b//需要计算变量v的二进制形式里1的个数的奇偶性
bool parity = ParityTable256[b];
 
//对于32位整数
unsigned int v;
v ^= v >> 16;
v ^= v >> 8;
bool parity = ParityTable256[v & 0xff];
 
//或者用下面的方法
unsigned char * p = (unsigned char *) &v;
parity = ParityTable256[p[0] ^ p[1] ^ p[2] ^ p[3]];

·计算变量中非零bit位的奇偶性(乘除法)

unsigned char b//需要计算变量v的二进制形式里1的个数的奇偶性,
bool parity = (((b * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1;
 
//以上代码利用了64bit的CUP指令,但只针对byte类型的变量,对于32位变量,使用下面的代码
unsigned int v; // 32-bit
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x11111111U) * 0x11111111U;
return (v >> 28) & 1;
 
//对于64bit变量
unsigned long long v; // 64-bit
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x1111111111111111UL) * 0x1111111111111111UL;
return (v >> 60) & 1;

·计算变量中非零bit位的奇偶性(并行法)

unsigned int v//需要计算变量v的二进制形式里1的个数的奇偶性,
v ^= v >> 16;
v ^= v >> 8;
v ^= v >> 4;
v &= 0xf;
return (0x6996 >> v) & 1;

·交换变量

//加减法
#define SWAP(a, b) ((&(a) == &(b)) || (((a) -= (b)), ((b) += (a)), ((a) = (b)(a))))
//异或法
#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))
//上面的异或法有一个缺陷,就是当a,b指向同一个变量时,这个宏的执行结果会把变量清0,所以下面是一个修正后的方法
#define SWAP(a, b) (((a) == (b)) || (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b))))

·交换变量中特定的bit位

unsigned int i, j; // 需要交换的bit位的起始位置
unsigned int n;    // 需要交换的bi位的长度
unsigned int b;    // 需要交换的数据
unsigned int r;    // 结果
 
unsigned int x = ((b >> i) ^ (b >> j)) & ((1U << n)1); // 临时变量
r = b ^ ((x << i) | (x << j));

这个算法用来将变量中特定的bit位交换,例如当b=47时,二进制数据b=00101111,我们需要交换是n=3,i=1(也就是从右数第二个位置开始的3个bit),交换到j=5的位置,也就是将红色的绿色的位置交换,最后得到的结果是11100011

·翻转变量中的bit位(原始方法)

unsigned int v;     // 需要翻转的变量
unsigned int r = v; // 结果
int s = sizeof(v) * CHAR_BIT1;
 
for (v >>= 1; v; v >>= 1)
{   
 
r <<= 1;
 
r |= v & 1;
 
s–;
}
r <<= s; // shift when v’s highest bits are zero

·翻转变量中的bit位(查表法)

static const unsigned char BitReverseTable256[256] =
{
#   define R2(n)     n,     n + 2*64,     n + 1*64,     n + 3*64
#   define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
#   define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
    
R6(0), R6(2), R6(1), R6(3)
};
 
unsigned int v; // 需要翻转的变量
unsigned int r; // 结果
 
// 方法1:
r = (BitReverseTable256[v & 0xff] << 24) |
    
(BitReverseTable256[(v >> 8) & 0xff] << 16) |
    
(BitReverseTable256[(v >> 16) & 0xff] << 8) |
    
(BitReverseTable256[(v >> 24) & 0xff]);
 
//方法2:
unsigned char * p = (unsigned char *) &v;
unsigned char * q = (unsigned char *) &r;
q[3] = BitReverseTable256[p[0]];
q[2] = BitReverseTable256[p[1]];
q[1] = BitReverseTable256[p[2]];
q[0] = BitReverseTable256[p[3]];

·翻转变量中的bit位(乘除法)

unsigned char b; // 这个方法只适用于8-bit数据,并且利用了64位指令,只需要3个指令即可完成
 
b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;

·翻转变量中的bit位(乘法)

unsigned char b; // 这个方法只适用于8-bit数据,使用了4个64位指令,但避免了取模操作
 
b = ((b * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> 32;

下面演示了这个算法的计算过程,假设原先的二进制数据是abcd efgh

·翻转变量中的bit位(7个32位指令)

//适用于8bit数据
b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;

·其他特殊的翻转算法

//翻转奇偶位的数据,例如 10101010 -> 01010101
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
//翻转相邻的对,例如 11001100 -> 00110011
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
//翻转相邻的4bit,例如 1111000011110000 -> 0000111100001111
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
//翻转相邻的字节
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
//翻转相邻的双字节
v = ( v >> 16             ) | ( v               << 16);
 
//如果需要翻转的数据是非常长的数据,那么可以用下面的算法
unsigned int s = sizeof(v) * CHAR_BIT; // bit size; must be power of 2
unsigned int mask = ~0;         
while ((s >>= 1) > 0)
{
 
mask ^= (mask << s);
 
v = ((v >> s) & mask) | ((v << s) & ~mask);
}

发表评论

电子邮件地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据