位运算的一般应用
功能 例子 运算 去掉最后一位 1110101->111010 x>>1 在最后加0 1110101->11101010 x<
通过如下的例子，来看看位运算在底层的应用：
1.判断是否是2的整数次幂(来自Linux kernel)
uint32_t is_power_two(uint32_t x){
return !(x&(x-1));
}
uint32_t is_power_two(uint32_t x){
return x==x&~x+1;
}
方法一
对于无符号数的编码，可以做出如下解释:
[x=\sum _{i=0} ^{w-1} x_i *2^i ]
显然,若该数是2的整数次幂,显然二进制形式是[00…0100…0]的形式,设第 k位为1(从第0位计数),则有:
[x-1=2^k-1=\sum_{i=0}^{k-1}2^i ]
显然,该数的表达方式为 [00...00111...1],与原数进行按位与,结果为0.
方法二
x&~x+1即 x&-x,首先关于补码的非运算.任意非0的 x总可以找到最后边的1,即可以将 x表示为:
[[x_{w-1},x_{w-2},…,x_{k+1},1,0,0,…,0] ]
从而有:
[-x=[～ x_{w-1},～x_{w-2},…,～x_{k+1},1,0,0,…,0] ]
显然,若 x是2的整数次幂则有 x==x&-x为真.
2.对2的整数次幂取余(来自HashMap)
uint32_t mod_power_two(uint32_t x,uint32_t bucket){
return x&(bucket-1);
}
对于一个无符号数 x, xmod2^w的作用等价于丢掉该数二进制表示的从w+1位开始的高位,即将该二进制数进行类似截断.例如:
[25\% 16=9—>11001\&01111=01001_2=9_{10} ]
16=2^4,因此取余会将第5位开始的位均设为0,只保留后4位,因此:
[x\ mod\ 2^n=x\&(2^n-1) ]
3.向上取整到2的整数次幂
uint32_t next_power_two(uint32_t x){
--x;
x|=x>>1;
x|=x>>2;
x|=x>>4;
x|=x>>8;
x|=x>>16;
return ++x;
}
--x是为了保证,这个数不是2的整数次幂. 设这个数可以表示为 1.....,则右移1位得 01......或运算得 11......,继续右移2位,得 0011......或运算得 1111......,最后一次位运算后得 111...111最后返回时 +1遍得到了向上的一个2的整数次幂.
4.判断是否含有奇数个1
bool is_oddones(uint32_t x){
x^=x>>1;
x^=x>>2;
x^=x>>4;
x^=x>>8;
x^=x>>16;
return x&0x1;
}
总的思想: 奇数个1进行异或结果位1,因为只需想方法,将这个数二进制位的所有数进行异或就知道是否有奇数个1了.举了例子,下面这个 数是某个数二进制的低几位.
第一次运算:
1110 1101 1000
0111 0110 1100
^——————————
1001 1011 0100
最右边的0是第0位与第1位异或所得,依次可得 从右往左位 0^1 1^2 2^3 3^4.....(此处的数字为第位数,下同)
第二次运算:
1001 1011 0100
0010 0110 1101
^—————————–
1011 1101 1001
第二排数字的结果分别是 2^3 3^4 4^5 5^6...,故最右边的0是 0^1^2^3,依次再有 1^2^3^4,…
第三次运算:
1011 1101 1001
1011 1101
^—————————–
0110 0100
第二排的数字从最右边开始为 4^5^6^7,依次…….从而结果中,最右边的数代表 0^1^2^3^4^5^6^7
因而,若原数字在原始数据中是第 i位,在最终的结果中,该位代表的即是:
[i\oplus (i+1)\oplus (i+2)\oplus \cdots \oplus (i+30)\oplus (i+31) ]
因为,令 i=0,即最低位的值,即为结果,故最终 x&0x1
5. 1的个数
uint32_t count_one(uint32_t x){
x=(x&0x55555555)+(x>>1&0x55555555);
x=(x&0x33333333)+(x>>2&0x33333333);
x=(x&0x0f0f0f0f)+(x>>4&0x0f0f0f0f);
x=(x&0x00ff00ff)+(x>>8&0x00ff00ff);
x=(x&0x0000ffff)+(x>>16&0x0000ffff);
return x;
}
思想: 分而治之
先将32位数分成16份,每份俩部分:
0x55555555= 0101......01
故 x&0x55555555得到每个小份的第二部分的1情况, x>>1&0x55555555得到每个小份中第一部分的1的情况,相加得到的2位二进制数即为,该小份中1的个数.现在的任务就是将这些数都加起来 .
10 11 01 00 ……
第一次 01 10 01 00
0x33333333= 0011......0011
故 x&0x33333333将每个2位能单独拿出来,再加上 x>>2&0x33333333就是两个2位数的和(是一个用4位二进制表示的数),即将这16份,合并成8份,4位一组.
01 10 01 00
第二次 0011 0001
0x0f0f0f0f=00001111...00001111
故 x&0x0f0f0f0f将4位单独拿出来,再加上 x>>4&0x0f0f0f0f就是两个4位数的和.按照这种思想,最后会得到两个16位数的和(按32位表示)这个数的大小就是1的个数.
Original: https://www.cnblogs.com/oasisyang/p/13218500.html
Author: OasisYang
Title: 位运算（一）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/585699/
转载文章受原作者版权保护。转载请注明原作者出处！