一些常用位运算技巧-数据与编程-热点资讯-野望文存-科技 
    欢迎来到野望文存-科技!
当前位置:野望文存-科技 > 热点资讯 > 数据与编程 >  一些常用位运算技巧

一些常用位运算技巧

发表时间:2020-11-29 19:51:00  来源:野望文存  浏览:次   【】【】【

(给算法爱好者加星标,修炼编程内功

作者:Liao Tonglang

https://quant67.com/post/C/bit-hack.html

1、整数的符号

int  v;     // 需要获得 v 的符号 int  sign;  // 结果 
// CHAR_BIT 是一个字节的比特数 // v < 0 则是 -1,否则 0 sign = -( v < 0 ); // 使用位运算更快sign = -(int)( (unsigned int)v >> sizeof(int) * CHAR_BIT - 1);// 或者更简单的写法 sign = v >> (sizeof(int) * CHAR_BIT - 1);
// 如果想要得到 -1 或 +1,只需要在最低位或 1 sign = 1 | ( v >> sizeof(int) * CHAR_BIT -1 );
// 如果想要 -1, 0 或 1, 则需要根据情况或 1 或 0 sign = ( 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 bits    x = (x & m2 ) + ( (x >>  2) & m2 ); //put count of each  4 bits into those  4 bits    x = (x & m4 ) + ( (x >>  4) & m4 ); //put count of each  8 bits into those  8 bits    x = (x & m8 ) + ( (x >>  8) & m8 ); //put count of each 16 bits into those 16 bits    x = (x & m16) + ( (x >> 16) & m16); //put count of each 32 bits into those 32 bits    x = (x & m32) + ( (x >> 32) & m32); //put count of each 64 bits into those 64 bits    return 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 bits    x = ( x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits    x = ( x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits    x += x >>  8;  //put count of each 16 bits into their lowest 8 bits    x += x >> 16;  //put count of each 32 bits into their lowest 8 bits    x += x >> 32;  //put count of each 64 bits into their lowest 8 bits    return 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 bits    x = ( x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits    x = ( x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits    return (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,再观察是不是字节内最高位是不是进位所得。

#define ahszero(v)  v - 0x01010101UL & ~v & 0x80808080UL


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、


觉得本文有帮助?请分享给更多人

推荐关注「算法爱好者」,修炼编程内功

点赞和在看就是最大的支持??

责任编辑:蔡学森