一些常用位运算技巧
（给算法爱好者加星标，修炼编程内功）
作者：Liao Tonglang
https://quant67.com/post/C/bit-hack.html
1、整数的符号
int v; // 需要获得 v 的符号int sign; // 结果// CHAR_BIT 是一个字节的比特数// v < 0 则是 -1，否则 0sign = -( v < 0 );// 使用位运算更快sign = -(int)( (unsigned int)v >> sizeof(int) * CHAR_BIT - 1);// 或者更简单的写法sign = v >> (sizeof(int) * CHAR_BIT - 1);// 如果想要得到 -1 或 +1，只需要在最低位或 1sign = 1 | ( v >> sizeof(int) * CHAR_BIT -1 );// 如果想要 -1, 0 或 1， 则需要根据情况或 1 或 0sign = ( v != 0 ) | (v >> (sizeof(int) * CHAR_BIT - 1));// 或者更简单的写法sign = (v > 0) - (v < 0);// 如果要判断一个值是不是非负的sign = 1 ^ ((unsigned int) v >> (sizeof(int) * CHAR_BIT - 1)); // v < 0 则 0, 否则 1// 判断两个整数是不是符号相反，只需要将最高位异或int x, y; // 两个整数bool f = ((x ^ y) < 0); // 符号相反就是真，否则为假// 获得绝对值unsigned int r; // 绝对值int const mask = v >> sizeof(int) * CHAR_BIT - 1;r = (v + mask) ^ mask;// 或者r = (v ^ mask) - mask;
2、最大值和最小值
int x;int y;int r; // 结果// 最小值r = y ^ ((x ^ y) & -(x < y));// 最大值r = x ^ ((x ^ y) & -(x < y));
如果 x>=y 那么 -(x<y) 将是全 1，所以 r=y^(x^y)&~0=y^x^y=x ,否则， -(x<y) 将是全 0, 此时 r=y^((x^y) & 0)=y 。
也可以使用下面的运算，但下面的运算并不保险，因为 x-y 可能溢出
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)
3、判断是不是 2 的幂
只要确定最多只有一个比特是 1
unsigned int v;bool f; // 结果f = (v & (v - 1)) == 0;// 注意到 0 不是 2 的倍数，所以修正如下f = v && !(v & (v - 1));
4、b比特位的数值转换为整数
有时为了节省空间，我们使用几个比特表示一个整数，而不是直接用 int，比如 4 个比特表示一个整数。
当需要将这几个比特读出时，如果是正数没有什么问题， 如果是负数，1101 就要转换成 -3，而不是 13 。
unsigned b; // 整数 x 的比特位int x; // 低 b 位保存需要读取的整数值int r; // 结果int const m = 1U << (b - 1); // 原整数符号位x = x & ((1U << b) - 1); // 将无关比特清零r = (x ^ m) - m;
5、如果满足条件将第 b 位置 0 或 1
bool f; // 条件int b; // 设置第 b 位unsigned int m = 1 << b;// if (f) w |= m; else w &= ~m;w ^= (-f ^ w) & m;
6、条件满足取相反数
bool fDontNegate; // 为假时取反int v;int r;r = (fDontNegate ^ (fDontNegate - 1)) * v;
如果需要条件为真时取反
bool fNegate;int v;int r;r = (v ^ -fNegate) + fNegate;
7、统计 1 的数量，也就是 Hamming weight
先将比特位两两分组，组内两个比特累加获得组内的 Hamming weight。
此后再 计算每相邻两组 Hamming weight 的和，获得按照每组 4bit 分组后各组的 Hamming weight。以此类推不断求和即可得到总的 Hamming weight。
例如，要计算数字 372063667 的 Hamming weight，需要如下图所示依次对相邻 两个数字相加即可。
00010110001011010011110110110011
0 1 1 1 0 1 2 1 0 2 2 1 1 2 0 2
1 2 1 3 2 3 3 2
3 4 5 5
7 10
17
要高效的实现这个过程，需要一些位运算的技巧。下面将使用 C 语言实现这个 过程，并一步步减少需要的运算量。
下面假设需要计算一个 uint64_t 的 Hamming weight。为了保护我的手指，先定义一些需要用到的常量：
const uint64_t m1 = 0x5555555555555555; //binary: 0101...const uint64_t m2 = 0x3333333333333333; //binary: 00110011..const uint64_t m4 = 0x0f0f0f0f0f0f0f0f; //binary: 4 zeros, 4 ones ...const uint64_t m8 = 0x00ff00ff00ff00ff; //binary: 8 zeros, 8 ones ...const uint64_t m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...const uint64_t m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 onesconst uint64_t hff = 0xffffffffffffffff; //binary: all onesconst uint64_t h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...
首先是第一个实现，需要 24 个运算：
int popcount64a(uint64_t x){x = (x & m1 ) + ( (x 1) & m1 ); //put count of each 2 bits into those 2 bitsx = (x & m2 ) + ( (x 2) & m2 ); //put count of each 4 bits into those 4 bitsx = (x & m4 ) + ( (x 4) & m4 ); //put count of each 8 bits into those 8 bitsx = (x & m8 ) + ( (x 8) & m8 ); //put count of each 16 bits into those 16 bitsx = (x & m16) + ( (x 16) & m16); //put count of each 32 bits into those 32 bitsx = (x & m32) + ( (x 32) & m32); //put count of each 64 bits into those 64 bitsreturn x;}
这个实现复用了变量 x 的内存区域，将累加的中间结果也存储在 x 中。首先是 m1 这一行， (x & m1) 获得 x 的奇数比特位， (x >> 1) & m1 获得 x 的偶数 比特位，两者累加的结果就是将 x 的比特两两分组，组内累加得到的结果存储 在各个组内两个比特的位置。
m2 行也是一样的道理，累加相邻的 m1 分组中累 加和，存储在原来两个相邻分组的 4bit 空间中。以此类推，最终获得 Hamming weight。这有点像线段树区间求和的过程。
第二个实现使用 17 个运算，是对上一个实现的改进：
int popcount64b(uint64_t x){x -= ( x 1) & m1; //put count of each 2 bits into those 2 bitsx = ( x & m2) + ((x 2) & m2); //put count of each 4 bits into those 4 bitsx = ( x + (x 4)) & m4; //put count of each 8 bits into those 8 bitsx += x 8; //put count of each 16 bits into their lowest 8 bitsx += x 16; //put count of each 32 bits into their lowest 8 bitsx += x 32; //put count of each 64 bits into their lowest 8 bitsreturn x & 0x7f;}
m1 行与上一个实现的 m1 行做的是一样的事情，这需要一点解释：
可以看到 m1 行就是是比特位两两分组后组内累加结果保存在本组对应两个比特 位，与上一个实现的 m1 行相同。
m2 行和上一个实现是一样的，下面看 m4 行。因为 8 比特的 Hamming weigth 绝对不会超过 8，所以最后累加只会存储到最多 4 比特的空间内，所以直接移 位相加取后四位就是这个分组的累加和。
因为 64 比特的 Hamming weight 存储空间绝对不会超过 8 比特，后面三行代 码将目前所有分组 (8 bit 一组) 的值都累加到最右边的 8 个比特中，最后直 接与 0x7f 返回最右边的一个字节即可。此处最后与 0xFF 或许更明白，但 7 比特的存储空间已经足够了。
第三个实现更加简单，使用 12 个运算，但其中有一个是乘法。这是使用运算最 少的实现。
int popcount64c(uint64_t x){x -= (x 1) & m1; //put count of each 2 bits into those 2 bitsx = ( x & m2) + ((x 2) & m2); //put count of each 4 bits into those 4 bitsx = ( x + (x 4)) & m4; //put count of each 8 bits into those 8 bitsreturn (x * h01) 56; //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...}
与上一个实现不一样的地方只有最后一行。
(x * h01) 意思是将目前所有 8 比 特一组的分组都累加到最左边的一个字节上, 使用小学提到的竖式乘法表示，很 容易哈先 x*h01 就是 x + (x<<8) + (x<<16) + (x<<24) + ... 。
最后右移 56 比特得到最左边的 8 比特就是结果，将其返回。
8、交换两个整数值
int a, b;a ^= b;b ^= a;a ^= b;
9、判断整数中有没有某个字节全 0
对于每个字节减 1，再观察是不是字节内最高位是不是进位所得。
10、枚举整数位图表示的集合的子集
依次减 1 直到 0 为止，这里包括空集，所以到 -1 为止
t = s;do {t = (t - 1) & t;} while (t != s);
如果要枚举所有大小为 k 的子集
comb = (1 << k) - 1while (comb < 1 << n) {x = comb & -comb;y = comb + x;comb = ((comb & ~y) / x >> 1) | y;comb 就是大小为 k 的子集}
- EOF -
1、
2、
3、
觉得本文有帮助？请分享给更多人
推荐关注「算法爱好者」，修炼编程内功
点赞和在看就是最大的支持??
