C/C++ 位运算总结
2019-04-29
C/C++ 位运算总结
n位数据的位运算可以视为长度为n的0/1向量运算
与为乘法，异或为模2加法
一、基本的位操作运算符
| 符号 | 描述 | 运算规则 |
|---|---|---|
& |
与 | 两个位都为1时，结果才为1 |
| ` | ` | 或 |
^ |
异或 | 两个位相同为0，相异为1，本质为模2加法（无进位加法） |
~ |
取反 | 0变1，1变0 |
<< |
左移 | 各二进位全部左移若干位，高位丢弃，低位补0 |
>> |
右移 | 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移） |
注意：
- 使用位操作算符时尽量添加括号，因为优先级低于一般的算术运算符
- 只能对整型数据运算
基本等式（无符号数）
~~n == n
基本等式（有符号数）
-n == ~n + 1 == ~(n - 1)
-~n == n + 1 //推论
~-n == n - 1 //推论
分配律
a & (b | c) == (a & b) | (a & c)
a | (b & c) == (a | b) & (a | c)
其他
((1 << n) - c) == ((1 << n) ^ c)
//
异或的性质
记 为异或运算，异或运算满足以下性质：
- ；
- （交换律）；
- （结合律）；
- （自反性）；
所有位二进制数的异或为
0（因为每一位1在所有数中出现的次数为一半，为偶数次）
更一般地，对于任意
二、位运算技巧（无关位长）
乘/除2的幂次（无符号数）
unsigned int x;
x >> n; //等价于x / 2^n;
x << n; //等价于x * 2^n;
判断奇偶
bool is_odd(int a){
return a & 1; // 等价于a % 2 == 0;
}
判断是否为
bool is_power_of_2(int a){
return !(a & (a - 1));
}
交换两数
void swap(int &a, int &b){ //不使用第3个变量，a和b不能引用同一个变量
a ^= b; //a = old_a ^ old_b
b ^= a; //b = old_b ^ (old_a ^ old_b) = old_a
a ^= b; //a = (old_a ^ old_b) ^ old_a = old_b
}
是否同号
bool is_same_sign(int a, int b){ //a!=0 且 b!=0
return (a ^ b) >= 0;
}
置二进制第 n 位为 1
int set_nth_bit_to_1(int a){
a = a | (1 << n);
}
置二进制第 n 位为 0
int set_nth_bit_to_0(int a){
a = a & ~(1 << n);
}
将二进制第 n 位取反
int reverse_nth_bit(int a){
a = a ^ (1 << n);
}
取二进制最低一位1
int get_low_1(int a){
return a & (-a); //-a = ~a + 1 = ~(a - 1), eg: a = 01010100 => 00000100
}
取二进制最低一位0
int get_low_0(int a){
return ~a & (a+1); //eg: a = 01010101 => 00000010
}
置二进制最低一位1为0
int set_low_1_to_0(int a){
a = a & (a - 1); //eg: a = 01010100 => 01010000
}
置二进制最低一位0为1
int set_low_0_to_1(int a){
a = a | (a + 1); //eg: a = 01010101 => 01010111
}
置二进制低位连续的0为1
int set_low_1_to_0(int a){
a = a | (a - 1); //eg: a = 01010100 => 01010111
}
向上对齐为的倍数
unsigned int round_up_to_power_of_2(unsigned int x, unsigned int n) { //align_to_
return (x + (1 << n) - 1) & ~((1 << n) - 1)
}
二、位运算技巧（依赖位长）
获取int的位长
sizeof(int) * CHAR_BIT; //CHAR_BIT = 8 in <climits>
下面默认int为32位的情况
获得int的最大值
int get_int_max(){
return ((unsigned)1 << 31) - 1; //2147483647
}
获得int的最小值
int get_int_min(){
return ((unsigned)1 << 31); //-2147483648
}
取符号
当a>0时候返回1，a<0时返回-1，a=0时返回0
方法1
int sign(int a){
return !!a - (((unsigned)a >> 31) << 1);
}
方法2
int sign(int a){
return -(int)((unsigned int)((int)a) >> 31);
}
取绝对值
int abs1(int a){
return (a >> 31) == 0 ? a : (~a + 1);
}
/* n>>31 取得n的符号，若n为正数，n>>31等于0，若n为负数，n>>31等于-1
若n为正数 n^0=0,数不变，若n为负数有n^-1 需要计算n和-1的补码，然后进行异或运算，
结果n变号并且为n的绝对值减1，再减去-1就是绝对值 */
若右移是算术右移，也可写为
int abs2(int a){
int s = a >> 31; //0 或 -1
return (a ^ s) - s; //s = 0, a ^ 0 - 0 = a, s = 1, a
}
取最大值
方法1
int max(int a, int b){
return b & ((a - b) >> 31) | a & (~(a-b) >> 31);
/*如果a>=b,(a-b)>>31为0，否则为-1*/
}
方法2
int max(int x, int y){
return x ^ ((x ^ y) & -(x < y));
/*如果x<y,x<y返回1，否则返回0，与0做与运算结果为0，与-1做与运算结果不变*/
}
取最小值
方法1
int min(int a, int b){
return a & ((a - b) >> 31) | b & (~(a - b) >> 31);
/*如果a>=b,(a-b)>>31为0，否则为-1*/
}
方法2
int min(int x, int y){
return y ^ ((x ^ y) & -(x < y));
/*如果x<y,x<y返回1，否则返回0，与0做与运算结果为0，与-1做与运算结果不变*/
}
高16位与低16位交换
unsigned int exchange_high_low_16(unsigned int a){
a = (a >> 16) | (a << 16);
}
取二进制最高一位1
int get_high_1(unsigned int a){//注意是无符号数
a = a | (a >> 1);
a = a | (a >> 2);
a = a | (a >> 4);
a = a | (a >> 8);
a = a | (a >> 16);
return (a + 1) >> 1; //eg: a = 01010101 => 01000000
}
取二进制中1的个数
内置函数__builtin_popcount实现相同功能
swar算法？
int count_1(unsigned int a){
a = (a & 0x55555555) + ((a >> 1) & 0x55555555);
a = (a & 0x33333333) + ((a >> 2) & 0x33333333);
a = (a & 0x0F0F0F0F) + ((a >> 4) & 0x0F0F0F0F);
a = (a & 0x00FF00FF) + ((a >> 8) & 0x00FF00FF);
a = (a & 0x0000FFFF) + ((a >> 16) & 0x0000FFFF);
return a
}
取二进制中前导0的个数
内置函数__builtin_clz实现相同功能
int count_leader_0(unsigned int a){
if (a == 0) return 32;
int n = 1;
if((a >> 16) == 0) {n += 16; a = a << 16;}
if((a >> 24) == 0) {n += 8; a = a << 8;}
if((a >> 28) == 0) {n += 4; a = a << 4;}
if((a >> 30) == 0) {n += 2; a = a << 2;}
if((a >> 31) == 0) {n += 1;} // 或者 n -= (a >> 31);
return n;
}
取二进制中末尾0的个数
内置函数__builtin_ctz实现相同功能
int count_tail_0(unsigned int a){
if (a == 0) return 32;
int n = 1;
if((a << 16) == 0) {n += 16; a = a >> 16;}
if((a << 24) == 0) {n += 8; a = a >> 8;}
if((a << 28) == 0) {n += 4; a = a >> 4;}
if((a << 30) == 0) {n += 2; a = a >> 2;}
if((a << 31) == 0) {n += 1;} // 或者 n -= (a << 31);
return n;
}
取二进制最低一位1的位数
int Lsb32(unsigned int a){ //LSB = Least Significant Bit
int n = 31;
if (a & 0x0000ffff) {n -= 16; a &= 0x0000ffff;}
if (a & 0x00ff00ff) {n -= 8; a &= 0x00ff00ff;}
if (a & 0x0f0f0f0f) {n -= 4; a &= 0x0f0f0f0f;}
if (a & 0x33333333) {n -= 2; a &= 0x33333333;}
if (a & 0x55555555) n -=1;
return n;
}
取二进制最高一位1的位数
int Msb32(unsigned int a){ //MSB = Most Significant Bit
int n = 0;
if (a & 0xffff0000) {n += 16; a &= 0xffff0000;}
if (a & 0xff00ff00) {n += 8; a &= 0xff00ff00;}
if (a & 0xf0f0f0f0) {n += 4; a &= 0xf0f0f0f0;}
if (a & 0xcccccccc) {n += 2; a &= 0xcccccccc;}
if (a & 0xaaaaaaaa) n += 1;
return n;
}
裁剪为0(小于0则返回0)
int clamp_to_0(int x){
return ((-x) >> 31) & x; //利用带符号的右移
}
裁剪为(大于则返回)
int clamp_to_power_of_2(int x, unsigned int n){
return ((((1 << n) - 1 - x) >> 31) | x) & ((1 << n) - 1);
}
下一个大于x的
unsigned int next_power_of_2(unsigned int x){
--x;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return ++x;
}
三、位运算实现基本数值运算
实现加法
本质上实现了加法器，可以使用串行加法或并行加法
一位全加器
和：
进位：
这里的乘法就是按位与，加法就是按位或，就是按位异或
串行加法
可以按上面的全加器一位一位计算结果
并行加法
一种实现是超前进位，所有进位可直接由计算得到
但在程序中不像电路可以直接相连，也只能依次计算
int add(int a, int b) {
int g = a & b;
int p = a ^ b;
int carry = 0; //超前进位，计算出所有位上的进位（已考虑更低位进位结果）
for(int i = 0; i < 32; i++) {
carry |= (g | (p & (carry << 1))) & (1 << i);
}
return a ^ b ^ (carry << 1); //最后可以直接进行无进位加法
}
其他方法
下面采用了一次计算所有位的和与进位，然后循环解决子问题（和加上进位）
int add(int a, int b) {
int carry, add;
do {
add = a ^ b; //无进位加法
carry = (a & b) << 1; //计算出所有位上的进位（未考虑更低位进位的结果）
//下次计算：无进位加法的结果 + 所有进位，每次循环，需要进位的最低位都会提高，直到没有需要进位的位，carry=0
a = add;
b = carry;
} while (carry);
return add;
}
实现减法
负数在计算机中以补码表示，加减法都可以由加法器计算，减去一个数等价于加上相反数
int subtract(int a, int b) {
return add(a, add(~b, 1)); //如果允许使用负号，直接取add(a, -b)
}
实现乘法
乘法可以通过系列移位和加法完成。最后一个1可通过b&~(b-1)取得，可通过b&(b-1)去掉
C语言写法，
int multiply(int a, int b) {
int neg = (b < 0);
if(neg) b = -b;
int sum = 0;
while(b > 0){
int last_bit = Lsb32(b); //调用之前的Lsb32函数，最低一位1的位数
sum += (a << last_bit);
b &= b - 1;//置最低一位1为0
}
return neg ? -sum : sum;
}
C++写法：可提前计算一个map
int multiply(int a, int b) {
bool neg = (b < 0);
if(neg) b = -b;
int sum = 0;
map<int, int=""> bit_map;
for(int i = 0; i < 32; i++)
bit_map.insert(pair<int, int="">(1 << i, i));
while(b > 0){
int last_bit = bit_map[b & ~(b - 1)];//最低一位1的位数
sum += (a << last_bit);
b &= b - 1;//置最低一位1为0
}
return neg ? -sum : sum;
}
实现除法
int divide(int a, int b) {
//b==0, a==INT_MIN, b==INT_MIN的情况没有考虑
bool neg = (a ^ b) < 0;//(a > 0) ^ (b > 0);
if(a < 0) a = -a;
if(b < 0) b = -b;
if(a < b) return 0;
//每次将b移位至与a位数相同，需要计算b最多需要移动几位
//有几种方法，右移被除数或左移除数，但是根据比较大小来判断位数是否相同容易出问题，特别是被除数是31位的时候
//下面采用同时右移，计算位数差，不会发生溢出后比较的问题
int m = 1, n = 1;
while((dividend >> m) > 0) m++;
while((divisor >> n) > 0) n++;
int q = 0;
for(int i = m - n; i >= 0; i--){
if((b << i) > a)
continue;
q |= (1 << i);
a -= (b << i);
}
return neg ? -q : q;
}
格雷码
n位格雷码：n位二进制码的一个排列，满足任意两个相邻的代码（包括首尾）只有一位二进制位不同
递归生成方法
n位格雷码的集合 = 前缀0加 n-1位格雷码集合（顺序） + 前缀1加 n-1位格雷码集合（逆序）
异或生成方法
n位，二进制码=>格雷码 ，格雷码=>二进制码，，
这种方法使用每位与其后（高）一位进行异或（比较差异）（代码实现就是二进制码自身与自身右移一位异或）
为什么这种方法映射后符合任意两个相邻的代码只有一位二进制位不同？
我们首先观察相邻两个二进制码的位变化情况，可以容易地发现+1相当于 从末尾开始直到第1个0（设为第k位）的所有位取反
x..xx011..11 => x..xx100..00；特别地，最低位就是0时，则x..xx0=>x..xx1；仅最高位是0时，则011..11 => 100..00
这样相邻二进制码的变化都发生在末尾的连续一部分
因此前后位异或的结果的变化的位只出现在二进制码变与不变的交界处，只有一位（第k位）发生了变化
（特别地，对于最高位，与0异或后不变（格雷码最高位与二进制码最高位相同），则最高位异或结果发生变化仅在原二进制码最高位变化时011..11 => 100..00，此时也只有一位（最高位，第k=n-1位）发生了变化）
为什么是一一映射
vector<int> grayCode(int n) {
int nn = 1 << n;
vector<int> res(nn);
for(int i = 0; i < nn; i++) {
res[i] = i ^ (i >> 1);
}
return res;
}
三、二进制位表示作为集合压缩数据
可以用 位二进制整数 编码 编号为的个对象 的 任何子集，其中当且仅当
（换句话说，二进制整数的每位表示一个对象是否在集合中）
则在，每个整数表示一个子集
（换句话说，二进制整数的位1的分布对应对象在集合中的情况）
遍历子集
由二进制整数表示的集合，可以方便地遍历所有子集，依次获取的位分布情况即可
遍历大小为k的子集
相当于枚举所有包含个的位二进制数，关键是如何从一个大小为子集计算得到下一个（对应二进制数更大）
int state = (1 << k) - 1; //初始时k个1都在末尾：state = 00001111
while (state < 1 << n) { //有效位数小于等于n位：state = 01100110 < 100000000
int low_bit = state & -state; //最低位1：low_bit = 000000 1 0
int added = state + low_bit; //移除最低位连续多个1，之前的0变1：0110 011 0 -> 0110 100 0
int low_multi_bits = state & ~added; //仅保留上一次操作使得state发生位翻转的部分即state最低连续多个1的区间：z = 0000 011 0
low_multi_bits = (low_multi_bits / low_bit) >> 1; //除法使得该区间连续多个1移至末尾，右移一位相当于删除一个1：z = 0000000 1
state = added | low_multi_bits; //合并
} //相当于每次把最低连续多个1的第一个1前移一位，剩余1全部移至末尾
集合操作
由二进制整数表示的集合，可以方便地进行集合运算
C/C++一般实现
typedef unsigned long long set;
//添加
set add(set s, int i){
s |= (1 << i);
return s;
}
//删除
set remove(set s, int i){
s &= ~(1 << i);
return s;
}
//在集合内
int in(set s, int i){
return s & (1 << i); //或者 (s >> i) & 1
}
//并集
set union_(set s1, set s2){
return s1 | s2;
}
//交集
set intersect(set s1, set s2){
return s1 & s2;
}
//差集, s1 - s2
set except(set s1, set s2){
return s1 & ~s2;
}
对于C++，也可以使用STL提供的bitset类
//初始化
std::bitset<4> foo; //foo: 0000
std::bitset<4> a (9); //用整数初始化，a: 0000000000001001
std::bitset<4> b (std::string("0011")); //用字符串初始化，不够位数前面补0，b: 0000000000000011
//位的获取和赋值，相当于加入或删除元素，或者判断元素是否在集合中
foo[1] = 1; // foo: 0010
foo[2] = foo[1]; // foo: 0110
foo.set(); // foo: 1111
foo.set(2,0); // foo: 1011
foo.set(2); // foo: 1111
foo.reset(1); // foo: 1101
foo.reset(); // foo: 0000
foo.flip(2); // foo: 0100
foo.flip(); // foo: 1011
//位运算对应集合操作
a & b; // 0010,交集
a | b; // 0111,并集
a ^ b; // 0101,差集
a == b; // false (0110==0011)
a != b; // true (0110!=0011)
//其他位运算，不对应集合操作
~b; // 1100 (NOT)
b << 1; // 0110 (SHL)
b >> 1; // 0001 (SHR)
//另外，一些统计和判断函数
foo.count(); //Count bits set
foo.size(); //Return size
foo.test(); //Return bit value
foo.any(); //Test if any bit is set
foo.none(); //Test if no bit is set
foo.all(); //Test if all bits are set
四、参考
http://www.cplusplus.com/reference/bitset/bitset/
http://graphics.stanford.edu/~seander/bithacks.html#OperationCounting
https://blog.whezh.com/bit-hacks/
http://www.matrix67.com/blog/archives/263
https://blog.csdn.net/zmazon/article/details/8262185
https://www.zhihu.com/question/38206659
https://blog.csdn.net/MoreWindows/article/details/7354571