Bit运算技巧汇集（上）

Posted on by jinchao

这篇文章转自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_BIT – 1));
// if v < 0 then -1, else +1
sign = +1 | (v >> (sizeof(int) * CHAR_BIT – 1)); 
// -1, 0, or +1
sign = (v != 0) | –(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT – 1));
// if v < 0 then 0, else 1
sign = 1 ^ ((unsigned int)v >> (sizeof(int) * CHAR_BIT – 1));

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

int v;           // 需要计算绝对值的变量
unsigned int r;  // 结果
int const mask = v >> (sizeof(int) * CHAR_BIT – 1);
 
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 + ((x – y) & ((x – y) >> (sizeof(int) * CHAR_BIT – 1))); // min(x, y)
r = x – ((x – y) & ((x – y) >> (sizeof(int) * CHAR_BIT – 1))); // max(x, y)

·判断是否是2的幂方

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

·扩展变量的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 << (b – 1);
 
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^ (f– 1)) * 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 &= v – 1; // 清掉最后一个为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 & (v – 1);
}

这个算法其实利用了上面的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_BIT – 1;
 
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);
}

发表评论

邮箱地址不会被公开。

This site uses Akismet to reduce spam. Learn how your comment data is processed.