位运算的一些小技巧，C语言描述，翻译自bithacks
计算一个整数（integer）的符号
int v; //我们想计算的数
int sign; //结果
//CHAR_BIT是每个字节的位数，一般为8
sign = -(v < 0);//if v<0 then -1,else 0;
// or, to avoid branching on CPUs with flag registers (IA32):
sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));
// 更高效（可移植性低）
sign = v >> (sizeof(int) * CHAR_BIT - 1);
上面最后一个语句使用右移31位计算了一个32位整数的符号位，这种做法要比第一种做法更快。当有符号位的整数右移时，左侧的位被复制到其他位。当为负数时，最左侧的位为1，正数为0，负数右移31位过后，所有的位数都为1，所以得到-1，不过这种做法依赖已具体的架构。
另外，如果比较喜欢用-1和+1来表示，可以这样做:
sign = +1 | (v >> (sizeof(int) * CHAR_BIT - 1)); // if v < 0 then -1, else +1
如果喜欢-1,0,+1表示：
sign = 1 ^ ((unsigned int)v >> (sizeof(int) * CHAR_BIT - 1)); // if v < 0 then 0, else 1
检测两个整数符号位是否不同
int x, y; // 两个要比较符号位的值
bool f = ((x ^ y) < 0); //当且仅当符号位不同时为true
注：上面代码中的bool类型为C99标准新引入，在编写代码时需要添加#include <stdbool.h>头文件
不使用分支计算一个整数的绝对值
int v; //要计算绝对值的数
unsigned int r; //结果
int const mask = v >> sizeof(int) * CHAR_BIT -1;
r = (v + mask) ^ mask;
一些cpu没有整数绝对值指令（或者是编译器无法使用）。分支指令的代价较高，上面的语句比一般的做法要好，比如：r=(v<0)?-(unsigned)v:v，即使操作数目相同。
不使用分支计算两个整数的最大值或最小值
int x, y;
int r;
r = y ^ ((x ^ y)) & - (x < y); //min(x, y)
在某些罕见的机器上，分支的代价很高并且没有条件移动指令，上面的语句业余会比常见得做法好，比如：r = (x < y) ? x : y，尽管多了两条指令
r = x ^ ((x ^ y) & -(x < y)); // max(x, y)
计算一个整数是否是2的倍数
unsigned int v;
bool f;
f = (v & (v-1)) ==0;
在这里0也被计算为2的倍数，解决：
f = v && !(v & (v - 1));
从一个恒定的位宽中扩展符号
注：符号扩展wiki ,关于符号扩展
对于内置类型，符号扩展是自动的，比如说字符型和整型。但假设有一个带符号的二进制补码x，只用b位来储存，我们想把x转换为一个int型，超过了b位。当x是正数时，只需要进行简单的复制，但如果是负数，就必须扩展符号。比如，我们只用4位来存储一个数字，那么-3用二进制表示就是1101，若用8位，那么-3是11111101。当我们转化为更多位表示时，高4位直接被复制到目的地中，这是就符号扩展。在C语言中，恒定位宽的符号扩展是微不足道的，因为可以在结构体或者联合体中指定位字段。比如，将5位转化为一个完整的整数。
int x; //将此数从5位转化为int
int r; //结果
struct {signed int x:5} s;
r =s.x = x;
下面是一个C++模板函数，它使用相同的语言功能在一个操作（尽管编译器会做更多）中从B位进行转换
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);
从可变位宽中扩展符号
有时我们需要扩展一个数字的符号位，但是我们并不知道这个数所代表的位数b。
unsigned b; //x代表的位数
int x; //扩展此b位数到r
int r;
int const m = 1U << (b - 1); //若b是固定的则可以预先计算出mask
x = x & ((1U << b) - 1);//如果x中的bits在b位置上已经是0了，则跳过此步
r = (x ^ m) -m;
上面的代码需要需要4个操作，但是当位宽是恒定的而不是可变时，假设高位已经为0，只需要两个快速的操作。
不依赖于x位数在b位置以上为0的方法会稍微快点，但是可移植性比较低：
int const m = CHAR_BIT * sizeof(x) - b;
r = (x << m) >> m;
三步操作从可变位宽中扩展符号
下面的方法在某些机器上可能会比较慢，由于乘法和除法的影响，这个版本需要4步操作。如果你知道b的初始位宽大于1，你可以使用r = (x * multipliers[b]) / multipliers[b]在3个操作中执行此类型的符号扩展只需要进行一次数组查找。
unsigned b; //代表x的位数
int x; //扩展此b位数到r
#defined M(b) (1U << ((sizeof(x) * CHAR_BIT -B )) //CHAR_BIT=bits/byte
static int const multipliers[] =
{
0, M(1), M(2), M(3), M(4), M(5), M(6), M(7),
M(8), M(9), M(10), M(11), M(12), M(13), M(14), M(15),
M(16), M(17), M(18), M(19), M(20), M(21), M(22), M(23),
M(24), M(25), M(26), M(27), M(28), M(29), M(30), M(31),
M(32)
}; // (如果使用超过64位，则添加更多)
static int const divisors[] =
{
1, ~M(1), M(2), M(3), M(4), M(5), M(6), M(7),
M(8), M(9), M(10), M(11), M(12), M(13), M(14), M(15),
M(16), M(17), M(18), M(19), M(20), M(21), M(22), M(23),
M(24), M(25), M(26), M(27), M(28), M(29), M(30), M(31),
M(32)
}; // (为64位添加更多)
#undef M
r = (x * multipliers[b]) / divisors[b];
下面这个版本不可移植，但是在使用算数右移的架构中会更快。
const int s = -b; // 或者: sizeof(x) * CHAR_BIT - b;
r = (x << s) >> s;
不使用分支来有条件的设置或者清除位
bool f; //条件标志
unsigned int m; //位掩码
unsigned int w; //需要修改的语句：if (f) w |= m; else w &= ~m;
w ^= (-f ^ w) & m;
或者，对于超标量处理器：
w = (w & ~m) | (-f & m);
不使用分支来获取一个数的相反数
若你想在flag为false时获取一个相反数，使用下面的语句来避免使用分支：
bool fDontNegate; //标志位，不获取v的相反数
int v; //要获取相反数的值
int r; //结果，fDontNegate ? v : -v;
r = (fDontNegate ^ (fDontNegate - 1)) * v;
若你想在flag为true时获取一个相反数，可以使用：
bool fNegate;
int v;
int r;
r = (v ^ -fNegate) + fNegate;
通过掩码来从两个值中合并位
unsigned int a; //以非掩码位合并
unsigned int b; //以掩码位合并
unsigned int mask; //若位来自b，则是1，若从a中来，则是0
统计位设置（就是计算多少位为1，笨方法）
unsigned int v; //要统计的数
unsigned int c; //结果
for(c = 0;v; v >>= 1)
{
c += v & 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; // 要统计的数
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[0] = 0;
for (int i = 0; i < 256; i++)
{
BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}
统计位设置，Brian Kernighan的方法
unsigned int v;
unsigned int c;
for (c = 0; v; c++)
{
v &= v - 1;
}
在14,24或32位字中使用使用64位指令对统计位设置
unsigned int v;
unsigned int c;
// 最多统计v中的高14位:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;
// 最多统计v中的高24位:
c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL)
% 0x1f;
// 统计32位:
c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) %
0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
这种方法需要拥有快速模运算的64位cpu才能更高效，第一种选项只需要3步，第二种要10步，第3种需要15步
并行统计位设置
unsigned int v;
unsigned int c;
static const int S[] = {1, 2, 4, 8, 16}; //Magic Binary Numbers
static const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};
c = v - ((v >> 1) & B[0]); //32位
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];
B数组以二进制形式表示：
B[0] = 0x55555555 = 01010101 01010101 01010101 01010101
B[1] = 0x33333333 = 00110011 00110011 00110011 00110011
B[2] = 0x0F0F0F0F = 00001111 00001111 00001111 00001111
B[3] = 0x00FF00FF = 00000000 11111111 00000000 11111111
B[4] = 0x0000FFFF = 00000000 00000000 11111111 11111111
我们可以通过Binary Magic Numbers B,S的模式来为较大的整数调整此方法。如果存在k位，那么我们需要数组S和B的元素长度为ceil(lg(k))，并且我们必须计算相同数量的表达式，因为对于c,S或者B长。对于32位的v，需要16步操作。
统计一个32位整数v的位数的最好方法：
v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
统计位数的最好方法只需要12步操作，与查找表方法相同，但是避免了表的内存和潜在的高速缓存未命中。它是上诉存并行方法和先前使用乘法方法的混种（在本节中用来64位指令来统计位），尽管不使用64位指令。字节中设置的位的计数在并行完成，并且字节中所设置的总位数通过乘以0x1010101与右移24位完成。
注：缓存命中问题wiki上有相关说明。
将位设置从最高有效位计数到给定位置
下面的例子找出rank of bit，将返回最高位下降到低位的过程中被设置为1的位总数
uint64_t v;
unsigned int pos;
uint64_t r;
r = v >> (sizeof(v) * CHAR_BIT - pos);
// Count set bits in parallel.
// r = (r & 0x5555...) + ((r >> 1) & 0x5555...);
r = r - ((r >> 1) & ~0UL/3);
// r = (r & 0x3333...) + ((r >> 2) & 0x3333...);
r = (r & ~0UL/5) + ((r >> 2) & ~0UL/5);
// r = (r & 0x0f0f...) + ((r >> 4) & 0x0f0f...);
r = (r + (r >> 4)) & ~0UL/17;
// r = r % 255;
r = (r * (~0UL/255)) >> ((sizeof(v) - 1) * CHAR_BIT);
计算奇偶性（笨方法）
unsigned int v; //需要计算奇偶性的数
bool parity = false;
while (v)
{
parity = !parity;
v = v & (v - 1);
}
上面的代码时间花费为与位设置的个数成正相关
通过查表来计算奇偶性
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;
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]];
使用64位乘法和模数除法来计算一个byte的奇偶性
unsigned char b;
bool parity =
(((b * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1;
上面这种方法总共需要4步操作，但是只适用于bytes
用乘法计算word的奇偶性
下面的方法使用乘法计算一个32位的值，只需要8步
unsigned int v; // 32-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x11111111U) * 0x11111111U;
return (v >> 28) & 1;
对于64位的值，8步操作也足够了
unsigned long long v; // 64-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x1111111111111111UL) * 0x1111111111111111UL;
return (v >> 60) & 1;
并行计算奇偶性
unsigned int v;
v ^= v >> 16;
v ^= v >> 8;
v ^= v >> 4;
v &= 0xf;
return (0x6996 >> v) & 1;
上面这种方法需要9步，适用于32位。对于byte值，可以通过移除"unsigned int v;"语句下面的两行来使步数优化到5步。
