2019-04-29

C/C++ 位运算总结

一、基本的位操作运算符

符号	描述	运算规则
`&`	与	两个位都为1时，结果才为1
`｜`	或	两个位都为0时，结果才为0
`^`	异或	两个位相同为0，相异为1
`~`	取反	0变1，1变0
`<<`	左移	各二进位全部左移若干位，高位丢弃，低位补0
`>>`	右移	各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

注意：

使用位操作算符时尽量添加括号，因为优先级低于一般的算术运算符
只能对整形数据运算

一些基本的等式

~~n = n
-n = ~n + 1 = ~(n - 1)
-~n = n + 1
~-n = n - 1

二、位操作计算技巧

乘/除2的幂次

x >> n; //等价于X / 2^n;

判断奇偶

bool is_odd(int a){
    return a & 1; // 等价于a % 2 == 0;
}

交换两数

void swap(int &a, int &b){ //不使用第3个变量
    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
}

取相反数

int opposite(int a){  
    return ~a + 1; //等价于 a = - a;
}

取符号

当a>0时候返回1，a<0时返回-1，a=0时返回0

int sign(int a){  
    return !!a - (((unsigned)a >> 31) << 1); 
}

是否同号

boolean is_same_sign(int x, int y){ //有0的情况例外
    return (x ^ y) >= 0; 
}

取绝对值

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做与运算结果不变*/
}

置二进制第 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

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为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
}

获得32位int的最大值

int get_int_max(){
    return (1 << 31) - 1;//2147483647
}

获得32位int的最小值

int get_int_min(){
    return (1 << 31); //-2147483648
}

高16位与低16位交换

int exchange_high_low_16(int a){
    a = (a >> 16) | (a << 16);
}

取二进制中1的个数

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的个数

int count_pre_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;}
    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; //利用带符号的右移
}

裁剪为$2^n-1$(大于$2^n-1$则返回$2^n-1$)

int clamp_to_255(int x){
    return (((255 - x) >> 31) | x) & 255;
}

下一个大于x的$2^n$

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 carry, add;
    do{
        add = a ^ b;
        carry = (a & b) << 1;
        a = add;
        b = carry;
    }while(carry);
    return add;
}

实现减法

int subtract(int a, int b) {
    return add(a, add(~b, 1));
}

实现乘法

乘法可以通过系列移位和加法完成。最后一个1可通过b&~(b-1)求得，可通过b& (b-1)去掉，\

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;
}

C语言写法，调用之前的Lsb32函数

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);//最低一位1的位数
        sum += (a << last_bit);
        b &= b - 1;//置最低一位1为0
    }
    return neg ? -sum : sum;
}

实现除法

int divide(int a, int b) {
    bool neg = (a > 0) ^ (b > 0);
    if(a < 0) a = -a;
    if(b < 0) b = -b;
    if(a < b) return 0;
    int msb = 0;
    for(msb = 0; msb < 32; msb++) //也可调用之前的Msb32函数
        if((b << msb) >= a)
            break;
    int q = 0;
    for(int i = msb; i >= 0; i--){
        if((b << i) > a)
            continue;
        q |= (1 << i);
        a -= (b << i);
    }
    return neg ? -q : q;
}

三、位运算压缩数据/作为集合

对于C++，STL提供的bitset类就是位的集合

//初始化
std::bitset<4> foo; //foo: 0000
std::bitset<16> bar (0xfa2); //用整数初始化，bar: 0000111110100010
std::bitset<16> baz (std::string("0101111001")); 
//用字符串初始化，不够长前面补0，baz: 0000000101111001
//添加和删除元素就是位的赋值
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
//一些统计和判断函数
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
//集合操作就位运算
std::bitset<4> foo (std::string("1001"));
std::bitset<4> bar (std::string("0011"));
foo^=bar; // 1010 (XOR,assign)
foo&=bar; // 0010 (AND,assign)
foo|=bar; // 0011 (OR,assign)
foo<<=2; // 1100 (SHL,assign)
foo>>=1; // 0110 (SHR,assign)
~bar; // 1100 (NOT)
bar<<1; // 0110 (SHL)
bar>>1; // 0001 (SHR)
foo==bar; // false (0110==0011)
foo!=bar; // true (0110!=0011)
foo&bar; // 0010
foo|bar; // 0111
foo^bar; // 0101

对于C，可以利用整数

typedef long long set; //char, short, int/long, __int64/long long
//添加
set add(set s, int i){
    s |= (1 << i);
    return s;
}
//删除
set delete(set s, int i){
    s &= ~(1 << i);
    return s;
}
//在集合内
int in(set s, int i){
    return s & (1 << i);
}
//并集
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;
}