位运算

原码，反码，补码

原码

1. 正数的原码就是其二进制本身
2. 负数的原码是把对应的正数的原码最高位改为１

反码

1. 正数的反码就是其二进制原码本身
2. 负数的反码是在其原码的基础上，符号位不变，其余各位取反

补码

1. 正数的补码就是其二进制原码本身
2. 负数的补码是在其反码的基础上加１,** -1的补码是11111111, 所以当一个数减１的时候，可以直接对其二进制数加1111111**

位运算小技巧

NOTE: 位运算只能运用在整数上

判断奇偶

只要根据末位是0还是１来决定，末位为０就是偶数，末位为１就是奇数，因此可以这样写

bool is_odd(int n) { 
    if ( n & 1 == 0) {
        return true; 
    }
    return false;
}

交换两数

//位操作的交换两数
void swap(int &a, int &b) { 
    a = a ^ b; 
    b = b ^ a; 
    a = a ^ b;
}

• b = b ^ a这一句根据上一句可以替换为b = b ^ (a ^ b),由于^（异或操作）满足交换律，　b = b ^ a ^ b等价于b = b ^ b ^ a，对于异或操作来说，一个整数和自己异或永远等于0, 　而一个数与０进行异或数值仍然不变，　所以此时等价于b = a
• 第三句a = a ^ b，由于第二句等价于b = a且第一句a = a ^ b所以第三句可以等价于a = a ^ b ^ a,又可以等价于a = b,即a被赋予b的值

正负变换

11的二进制为000 01011 , 进行取反 --> 1111 0100, 加1 --> 1111 0101（-11）同理，-11的二进制为1111 0101，取反 --> 0000 1010，加1 --> 0000 1011（11）

int reverse_signal(int n) { 
    return ~n + 1;
}

求绝对值

1. 先移位来取符号位， int i = n >> 31, 如果n为整数则i=0,n为负数则i=-1> 因为int型整数一般是4个字节，共32位，最高位为符号位，所以右移31位可以得到符号位> NOTE:符号位为１即负数的二进制，每右移一位，高位补的是１
2. 对于任何数，与0异或保持不变，与-1即0xFFFFFFFF异或相当于取反，因此，n与i异或后再减i（因为i不是为０就是-1，而减去-1即加1）也可以得到绝对值> 二进制转十六进制：-1的二进制为32个1, 转成十六进制的话，每四位先计算出对应的十进制

//第一种方法
int abs(int n) {
    int i = n >> 31; 
    return i == -1 ? (~n + 1) : n;
}
//第二种方法
int abs(int n) {
    int i = n >> 31; 
    return (a ^ i) - i;
}

高低位交换

假设一个16位无符号整数的二进制为:1000011011011000，经过高低位变换后则为11011000 10000110．无符号左移低位补０，右移高位补0，因此将1000011011011000 这个数先右移８位为0000000010000110得到高位，再将10000011011011000左移8位为11011000 00000000即得到低位，再将两个数相或就可以得到高低位变换后的数字

int low_high_transit(int n) { 
    return (n >> 8) | (n << 8)
}

二进制逆序

//16位二进制
int reverse_binary(int &n) { 
  n = ((n & 0xAAAA) >> 1) | ((n & 0x5555) << 1); 
  n = ((n & 0xCCCC) >> 2) | ((n & 0x3333) << 2);
  n = ((n & 0xF0F0) >> 4) | ((n & 0x0F0F) << 4); 
  n = ((n & 0xFF00) >> 8) | ((n & 0x00FF) << 8); 
  return n;
}

计算32位二进制有几个位是１

//32位二进制，如果要计算16位则0x55555555变为0x5555，依次类推,且没有最后一步
int count_bit(int &n) { 
    n = (n & 0x55555555) + ((n & 0xAAAAAAAA) >> 1); 
    n = (n & 0x33333333) + ((n & 0xCCCCCCCC) >> 2); 
    n = (n & 0x0F0F0F0F) + ((n & 0xF0F0F0F0) >> 4); 
    n = (n & 0x00FF00FF) + ((n & 0xFF00FF00) >> 8); 
    n = (n & 0x0000FFFF) + ((n & 0FFFF0000)) >> 16);
}