▶ 原文标题《Bit Twiddling Hacks》，地址：https://graphics.stanford.edu/~seander/bithacks.html
▶ 额外参考资料：https://leetcode.com/problems/sum-of-two-integers/discuss/84278/
▶ 计算 int v 的符号放入 int sign 。
// 方法零，(v >= 0) ? 0 : -1;
sign = -(v < ); // 方法一，(v >= 0) ? 0 : -1;
sign = -(int)((unsigned int)v >> (sizeof(int) * CHAR_BIT - )); // 方法二，(v >= 0) ? 0 : -1;
sign = v >> (sizeof(int) * CHAR_BIT - ); // 方法三，(v >= 0) ? 1 : -1;
sign = + | (v >> (sizeof(int) * CHAR_BIT - )); // 方法四，(v > 0) ? 1 : ((v == 0) ? 0 : -1);
sign = (v != ) | -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - )); // 方法五，(v > 0) ? 1 : ((v == 0) ? 0 : -1);，比方法四更快但移植性更差
sign = (v != ) | (v >> (sizeof(int) * CHAR_BIT - )); // 方法六，(v > 0) ? 1 : ((v == 0) ? 0 : -1);
sign = (v > ) - (v < ); // 方法七，(v >= 0) ? 1 : 0;
sign = ^ ((unsigned int)v >> (sizeof(int) * CHAR_BIT - ));
▶ 判断 int x 与 int y 是否有相反的符号，结果放入 bool f 。
f = ((x ^ y) < );
▶ 求 int x 的绝对值放入 int r 。
// 方法零
r = (v < ) ? -(unsigned)v : v; // 方法一
int const mask = v >> sizeof(int) * CHAR_BIT - ;
r = (v + mask) ^ mask; // 方法二
int const mask = v >> sizeof(int) * CHAR_BIT - ;
r = (v ^ mask) - mask;
▶ 求 int x 与 int y 的较小者或较大者。
// 方法零
r = x > y ? y : x;
r = x > y ? x : y; // 方法一，两行分别对应 r = min(x, y); 和 r = max(x, y);
r = y ^ ((x ^ y) & -(x < y));
r = x ^ ((x ^ y) & -(x < y)); // 方法二，要求已知 INT_MIN <= x - y <= INT_MAX，两行分别对应 r = min(x, y); 和 r = max(x, y);
r = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - )));
r = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - )));
▶ 判定 int v 是否是 2 的整数次幂，结果放入 bool f 。
// 方法一，缺点是 0 会被判定成 true
f = (v & (v - )) == ; // 方法二，修正方法一的错误，多一步运算
f = v && !(v & (v - ));
▶ 判定 int v 是否是 4 的整数次幂，结果放入 bool f 。
f = (n & (n - )) && (n & 0x55555555);
▶ 将较短的整形 x（例子中为 5-bit）填充为 int 长度的整形放入 int r 。
// 方法一，C
struct {signed int x:;} 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;
}
r = signextend<signed int,>(x);
▶ 将长度可变的较短整形 x（例子中为 b-bit）填充为 int 长度的整形放入 int r 。
// 方法一
int const m = 1U << (b - );// 若 b 固定则 m 也可以提前计算
x = x & ((1U << b) - ); // 若 x 超出 b 位的高位已经归零，则可以跳过该步
r = (x ^ m) - m; // 方法二
int const m = CHAR_BIT * sizeof(x) - b;
r = (x << m) >> m; // 方法三，使用 64 位整数时需要相应扩充
#define M(B) (1U << ((sizeof(x) * CHAR_BIT) - B)) static int const multipliers[] =
{
, M(), M(), M(), M(), M(), M(), M(),
M(), M(), M(), M(), M(), M(), M(), M(),
M(), M(), M(), M(), M(), M(), M(), M(),
M(), M(), M(), M(), M(), M(), M(), M(),
M()
};
static int const divisors[] =
{
, ~M(), M(), M(), M(), M(), M(), M(),
M(), M(), M(), M(), M(), M(), M(), M(),
M(), M(), M(), M(), M(), M(), M(), M(),
M(), M(), M(), M(), M(), M(), M(), M(),
M()
};
#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 赋值或清除。
// 方法零
f ? w |= m : w &= ~m; // 方法一
w ^= (-f ^ w) & m; // 方法二
w = (w & ~m) | (-f & m);
▶ 按条件 bool f 决定是否需要对 int v 求相反数，结果放入 int r 。
// 方法零
r = f ? v : -v; // 方法一，f 为真时不取相反数
r = (f ^ (f - )) * v; // 方法二，f 为真时取相反数
r = (v ^ -f) + f;
▶ 依蒙版 unsigned int mask 按位合并 unsigned int a 和 unsigned int b，当 mask 该位为 0 时取 a 的相应位，当 mask 该位为 1 时取 b 的相应位，结果放入 unsigned int r 。
// 方法零
(a & ~mask) | (b & mask); // 方法一
r = a ^ ((a ^ b) & mask);
▶ 计算 unsigned int v 二进制表示中为 1 的位数，结果放入 unsigned int c 。
// 方法零
for (c = ; v; v >>= )
c += v & ; // 方法一，打表
#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) static const unsigned char BitsSetTable256[] = { B6(), B6(), B6(), B6() };
c = BitsSetTable256[v & 0xff] + BitsSetTable256[(v >> ) & 0xff] + BitsSetTable256[(v >> ) & 0xff] + BitsSetTable256[v >> ]; // 等价的 BitsSetTable256 的初始化方法
BitsSetTable256[] = ;
for (int i = ; i < ; i++)
BitsSetTable256[i] = (i & ) + BitsSetTable256[i / ]; // 等价的 c 的计算方法
unsigned char * p = (unsigned char *)&v;
c = BitsSetTable256[p[]] + BitsSetTable256[p[]] + BitsSetTable256[p[]] + BitsSetTable256[p[]]; // 方法三，每次迭代清除一个最低非零位
for (c = ; v; c++)
v &= v - ; // 方法四，适用于最高 14-bit 的整数
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf; // 方法五，适用于最高 24-bit 的整数
c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> ) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f; // 方法六，适用于最高 32-bit 的整数
c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> ) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += ((v >> ) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f; // 方法七，并行算法，可以扩展到更大尺寸的数上去
static const int S[] = { , , , , };
static const int B[] = { 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF };
c = v - ((v >> ) & B[]);
c = ((c >> S[]) & B[]) + (c & B[]);
c = ((c >> S[]) + c) & B[];
c = ((c >> S[]) + c) & B[];
c = ((c >> S[]) + c) & B[]; // 数组 B 的二进制表示
B[] = 0x55555555 =
B[] = 0x33333333 =
B[] = 0x0F0F0F0F =
B[] = 0x00FF00FF =
B[] = 0x0000FFFF = // 方法八，最快最简单
v = v - ((v >> ) & 0x55555555);
v = (v & 0x33333333) + ((v >> ) & 0x33333333);
c = ((v + (v >> ) & 0xF0F0F0F) * 0x1010101) >> ; // 方法九，方法八的扩展，最高支持 128-bit 整数（数据格式称为 T）
v = v - ((v >> ) & (T)~(T) / );
v = (v & (T)~(T) / * ) + ((v >> ) & (T)~(T) / * );
v = (v + (v >> )) & (T)~(T) / * ;
c = (T)(v * ((T)~(T) / )) >> (sizeof(T) - ) * CHAR_BIT;
▶ 提取二进制最后一位 1，如对 24 提取得 8 。
A & -A 或 A & ~(A - ) 或 A ^ (A & (A - ))
▶ 去掉二进制最后一位1，如对 24 去掉得 16 。
A & (A - )
▶ 求 int a 和 int b 的和
int getsum(int a, int b) { return b == ? a : getsum(a^b, (a&b) << ); }
▶ 计算 int m 到 int n 之间（闭区间）所有整数进行 & 运算的结果
int rangeBitwiseAnd(int m, int n)
{
int a;
for (a = ; m != n; m >>= , n >>= , a++);
return m << a;
}
▶ 给定 uint64_t v（uint64_t 等价于 unsigned long long），计算其二进制表示中左边起 unsigned int pos 位（从 1 开始计数，1 ≤ pos ≤ 64）之内有多少个非零位，结果放入 uint64_t r 。例如，v = 0ccccccc cccccccc，则当 pos 分别等于 1 ~ 16 时 r 分别等于 {0, 0, 0, 0, 1, 2, 2, 2, 3, 4, 4, 4, 5, 6, 6, 6, 7, 8, 8, 8} 。注释为该行的等价语句。
r = v >> (sizeof(v) * CHAR_BIT - pos);
r = r - ((r >> ) & ~0ULL / ); // r = (r & 0x5555555555555555) + ((r >> 1) & 0x5555555555555555);
r = (r & ~0ULL / ) + ((r >> ) & ~0ULL / ); // r = (r & 0x3333...) + ((r >> 2) & 0x3333...);
r = (r + (r >> )) & ~0ULL / ; // r = (r & 0x0f0f...) + ((r >> 4) & 0x0f0f...);
r = (r * (~0ULL / )) >> ((sizeof(v) - ) * CHAR_BIT);// r %= 255;
▶ 给定 uint64_t v（uint64_t 等价于 unsigned long long），计算其二进制表示中左边起第 unsigned int r 个非零位（从 1 开始计数，1 ≤ r ≤ 64）是 v 的第几位，结果放入 unsigned int s 。例如，v = 0ccccccc cccccccc，则当 r 分别等于 1 ~ 8 时 r 分别等于 {5, 6, 9, 10, 13, 14, 17, 18} 。注释为该行的等价语句。
unsigned long long a, b, c, d;
unsigned int t;
a = v - ((v >> ) & ~0ULL / ); // a = (v & 0x5555555555555555) + ((v >> 1) & 0x5555555555555555);
b = (a & ~0ULL / ) + ((a >> ) & ~0ULL / ); // b = (a & 0x3333333333333333) + ((a >> 2) & 0x3333333333333333);
c = (b + (b >> )) & ~0ULL / 0x11; // c = (b & 0x0f0f0f0f0f0f0f0f) + ((b >> 4) & 0x0f0f0f0f0f0f0f0f);
d = (c + (c >> )) & ~0ULL / 0x101; // d = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff);
t = (d >> ) + (d >> );
s = ;
s -= ((t - r) & ) >> ; r -= (t & ((t - r) >> )); t = (d >> (s - )) & 0xff; // if (r > t) {s -= 32; r -= t;}
s -= ((t - r) & ) >> ; r -= (t & ((t - r) >> )); t = (c >> (s - )) & 0xf; // if (r > t) {s -= 16; r -= t;}
s -= ((t - r) & ) >> ; r -= (t & ((t - r) >> )); t = (b >> (s - )) & 0x7; // if (r > t) {s -= 8; r -= t;}
s -= ((t - r) & ) >> ; r -= (t & ((t - r) >> )); t = (a >> (s - )) & 0x3; // if (r > t) {s -= 4; r -= t;}
s -= ((t - r) & ) >> ; r -= (t & ((t - r) >> )); t = (v >> (s - )) & 0x1; // if (r > t) {s -= 2; r -= t;}
s = + (((t - r) & ) >> ) - s; // if (r > t) s--;
▶ 判断 int v 二进制表示中非零位个数的奇（1）偶（0）性放入 bool partity 。
// 方法零
while (v)
{
parity = !parity;
v = v & (v - );
} // 方法一
#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) static const bool ParityTable256[] = { P6(), P6(), P6(), P6() };
parity = ParityTable256[(v & 0xff) ^ ((v >> ) & 0xff) ^ ((v >> ) & 0xff) ^ (v >> ) & 0xff]; // 方法二，方法一对 32-bit 整数的方法
#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) static const bool ParityTable256[] = { P6(), P6(), P6(), P6() };
v ^= v >> ;
v ^= v >> ;
parity = ParityTable256[v & 0xff]; // 方法三
unsigned int b = (v & 0xff) ^ ((v >> ) & 0xff) ^ ((v >> ) & 0xff) ^ (v >> ) & 0xff;
parity = (((b * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & ; // 方法四
v ^= v >> ;
v ^= v >> ;
v = (v & 0x1111111111111111ULL) * 0x1111111111111111ULL;
partity = (v >> ) & ; // 方法五，方法四对 32-bit 整数的方法
v ^= v >> ;
v ^= v >> ;
v = (v & 0x11111111UL) * 0x11111111UL;
partity = (v >> ) & ; // 方法六，并行算法
v ^= v >> ;
v ^= v >> ;
v ^= v >> ;
v &= 0xf;
partity = (0x6996 >> v) & ;
▶ 交换两个变量 a 和 b 的值而不使用临时变量
// 方法一，使用加减法
#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 ^= a ^= b;
▶ 交换 unsigned int b 的二进制表示从右数第 unsigned int i 位（个位是第 1 位，不要 0）起连续 unsigned int r 位（不含第 i 位），交换到从右数第 unsigned int j 位起连续 unsigned int r 位（不含第 j 位）。例如 b = 001011112，r = 3（移动连续的 3 位），i = 1（指向加粗的 111），j = 5（指向加粗的 001）。换完以后 b = 111000112 。
unsigned int temp = ((b >> i) ^ (b >> j)) & ((1U << n) - );
r = b ^ ((temp << i) | (x << j));
▶ 将 unsigned int v 的二进制表示反序排列放入 unisgned int r 。
// 传统方法，按顺序构造 r
int s = sizeof(v) * CHAR_BIT - ;// 记录高位的无效 0 个数
for (v >>= ; v; v >>= )
{
r <<= ;
r |= v & ;
s--;
}
r <<= s; // 方法一，打表
#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 ) static const unsigned char BitReverseTable256[] = { R6(), R6(), R6(), R6() };
r = (BitReverseTable256[v & 0xff] << ) | (BitReverseTable256[(v >> ) & 0xff] << ) | (BitReverseTable256[(v >> ) & 0xff] << ) | (BitReverseTable256[(v >> ) & 0xff]); // 等价的 r 的计算方法
unsigned char * p = (unsigned char *)&v;
unsigned char * q = (unsigned char *)&r;
q[] = BitReverseTable256[p[]];
q[] = BitReverseTable256[p[]];
q[] = BitReverseTable256[p[]];
q[] = BitReverseTable256[p[]]; // 方法二，可扩展的方法，依次为相邻位交换，连续两位一组交换，连续四位一组交换，连续八位一组交换，连续十六位一组交换
v = ((v >> ) & 0x55555555) | ((v & 0x55555555) << );
v = ((v >> ) & 0x33333333) | ((v & 0x33333333) << );
v = ((v >> ) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << );
v = ((v >> ) & 0x00FF00FF) | ((v & 0x00FF00FF) << );
r = (v >> ) | (v << ); // 方法三，可扩展的方法
unsigned int s = sizeof(v) * CHAR_BIT;// 要求 s 为 2 的整数次幂
unsigned int mask = ~;
while ((s >>= ) > )
{
mask ^= (mask << s);
v = ((v >> s) & mask) | ((v << s) & ~mask);
}
r = s;
▶ 将 unsigned char v 的二进制表示反序排列放入 unisgned char r （只对 1 Byte 的数据进行操作）。
// 方法一
r = (v * 0x0202020202ULL & 0x010884422010ULL) % ; // 方法二
r = ((v * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> ; // 方法三
r = ((r * 0x0802UL & 0x22110UL) | (b * 0x8020UL & 0x88440UL)) * 0x10101UL >> ;
▶ 计算 unsigned int n 模 2 的 unsigned int s 次幂，结果放入 unsigned int m 。
m = n & (1U << s - );
▶ 计算 unsigned int n 模（2 的 unsigned int s 次幂减 1），结果放入 unsigned int m 。
// 方法一
const unsigned int d = (1U << s) - ;
for (m = n; n > d; n = m)
{
for (m = ; n; n >>= s)
m += n & d;
}
m = (m == d) ? : m; // 方法二
static const unsigned int M[] =
{
0x00000000, 0x55555555, 0x33333333, 0xc71c71c7,
0x0f0f0f0f, 0xc1f07c1f, 0x3f03f03f, 0xf01fc07f,
0x00ff00ff, 0x07fc01ff, 0x3ff003ff, 0xffc007ff,
0xff000fff, 0xfc001fff, 0xf0003fff, 0xc0007fff,
0x0000ffff, 0x0001ffff, 0x0003ffff, 0x0007ffff,
0x000fffff, 0x001fffff, 0x003fffff, 0x007fffff,
0x00ffffff, 0x01ffffff, 0x03ffffff, 0x07ffffff,
0x0fffffff, 0x1fffffff, 0x3fffffff, 0x7fffffff
};
static const unsigned int Q[][] =
{
{ , , , , , },{ , , , , , },{ , , , , , },
{ , , , , , },{ , , , , , },{ , , , , , },
{ , , , , , },{ , , , , , },{ , , , , , },
{ , , , , , },{ , , , , , },{ , , , , , },
{ , , , , , },{ , , , , , },{ , , , , , },
{ , , , , , },{ , , , , , },{ , , , , , },
{ , , , , , },{ , , , , , },{ , , , , , },
{ , , , , , },{ , , , , , },{ , , , , , },
{ , , , , , },{ , , , , , },{ , , , , , },
{ , , , , , },{ , , , , , },{ , , , , , },
{ , , , , , },{ , , , , , }
};
static const unsigned int R[][] =
{
{ 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000 },
{ 0x0000ffff, 0x000000ff, 0x0000000f, 0x00000003, 0x00000001, 0x00000001 },
{ 0x0000ffff, 0x000000ff, 0x0000000f, 0x00000003, 0x00000003, 0x00000003 },
{ 0x00007fff, 0x0000003f, 0x00000007, 0x00000007, 0x00000007, 0x00000007 },
{ 0x0000ffff, 0x000000ff, 0x0000000f, 0x0000000f, 0x0000000f, 0x0000000f },
{ 0x00007fff, 0x0000001f, 0x0000001f, 0x0000001f, 0x0000001f, 0x0000001f },
{ 0x00000fff, 0x0000003f, 0x0000003f, 0x0000003f, 0x0000003f, 0x0000003f },
{ 0x00003fff, 0x0000007f, 0x0000007f, 0x0000007f, 0x0000007f, 0x0000007f },
{ 0x0000ffff, 0x000000ff, 0x000000ff, 0x000000ff, 0x000000ff, 0x000000ff },
{ 0x000001ff, 0x000001ff, 0x000001ff, 0x000001ff, 0x000001ff, 0x000001ff },
{ 0x000003ff, 0x000003ff, 0x000003ff, 0x000003ff, 0x000003ff, 0x000003ff },
{ 0x000007ff, 0x000007ff, 0x000007ff, 0x000007ff, 0x000007ff, 0x000007ff },
{ 0x00000fff, 0x00000fff, 0x00000fff, 0x00000fff, 0x00000fff, 0x00000fff },
{ 0x00001fff, 0x00001fff, 0x00001fff, 0x00001fff, 0x00001fff, 0x00001fff },
{ 0x00003fff, 0x00003fff, 0x00003fff, 0x00003fff, 0x00003fff, 0x00003fff },
{ 0x00007fff, 0x00007fff, 0x00007fff, 0x00007fff, 0x00007fff, 0x00007fff },
{ 0x0000ffff, 0x0000ffff, 0x0000ffff, 0x0000ffff, 0x0000ffff, 0x0000ffff },
{ 0x0001ffff, 0x0001ffff, 0x0001ffff, 0x0001ffff, 0x0001ffff, 0x0001ffff },
{ 0x0003ffff, 0x0003ffff, 0x0003ffff, 0x0003ffff, 0x0003ffff, 0x0003ffff },
{ 0x0007ffff, 0x0007ffff, 0x0007ffff, 0x0007ffff, 0x0007ffff, 0x0007ffff },
{ 0x000fffff, 0x000fffff, 0x000fffff, 0x000fffff, 0x000fffff, 0x000fffff },
{ 0x001fffff, 0x001fffff, 0x001fffff, 0x001fffff, 0x001fffff, 0x001fffff },
{ 0x003fffff, 0x003fffff, 0x003fffff, 0x003fffff, 0x003fffff, 0x003fffff },
{ 0x007fffff, 0x007fffff, 0x007fffff, 0x007fffff, 0x007fffff, 0x007fffff },
{ 0x00ffffff, 0x00ffffff, 0x00ffffff, 0x00ffffff, 0x00ffffff, 0x00ffffff },
{ 0x01ffffff, 0x01ffffff, 0x01ffffff, 0x01ffffff, 0x01ffffff, 0x01ffffff },
{ 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff },
{ 0x07ffffff, 0x07ffffff, 0x07ffffff, 0x07ffffff, 0x07ffffff, 0x07ffffff },
{ 0x0fffffff, 0x0fffffff, 0x0fffffff, 0x0fffffff, 0x0fffffff, 0x0fffffff },
{ 0x1fffffff, 0x1fffffff, 0x1fffffff, 0x1fffffff, 0x1fffffff, 0x1fffffff },
{ 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff },
{ 0x7fffffff, 0x7fffffff, 0x7fffffff, 0x7fffffff, 0x7fffffff, 0x7fffffff }
};
const unsigned int d = (1U << s) - ; // so d is either 1, 3, 7, 15, 31, ...).
m = (n & M[s]) + ((n >> s) & M[s]);
for (const unsigned int * q = &Q[s][], *r = &R[s][]; m > d; q++, r++)
m = (m >> *q) + (m & *r);
m = m == d ? : m;// 等价于 m = m & -((signed)(m - d) >> s);