位运算

（注意：负数按补码参与位运算）

1,& 与

取n对应二进制的最后一位： n&1
取n对应二进制的某一位：n&(1<<k)
将n对应二进制的最后一个1变为0：n&(n-1)

求n/2的余数：即取n二进制的最后一位
推广：求 n/2^k 的余数：即取n二进制的最后k位

2,| 或

将n对应二进制的最后一位置为1： n|1

3,~ 非

改变符号：x -> ~x+1 = -x
~y=-y-1
x-y=x+~y+1

4,^ 异或

不进位的加法;

性质：a^0=a; a^a=0;

用来求只出现一次的那个数：所有数相异或;

交换两个数值: x=x^y; y=x^y; x=x^y;

5,>> 右移

左边补符号位（>>> 可实现左边补零）
n>>1 == n/2

6,<< 左移

右边补0
n<<1 == n*2

7,不同长度的数据进行位运算

按右端对齐，然后位运算。
右端对齐后，左边不足的位：
（1）如果整型数据为正数或无符号数，左边补0。
（2）如果整型数据为负数，左边补1。

例题

例1，求x/2ⁿ
分析：位运算的右移是向下取整，正数的除法除法是向下取整，负数的除法是向上取整

int divpwr2(int x, int n) { 
    //当为负数&余数不为0时，对x>>n要加1 
    return (x >> n) + ((x >> 31) & !!(x ^ ((x >> n) << n)));  
}  

例2，求x的二进制中1的个数
分析：做一次x=x&(x-1)运算，x最右边的1就变为0

int numof1(int x){
    int count=0;
    while(x){
        x=x&(x-1);
        count++;
    }
    return count;
}

扩展：
1，判断x是否是2的k次方？
分析：即x的二进制中是否只有一个1
2，输入m和n，求改变m的二进制的多少位才能变为n
分析：x=m^n，则x的二进制中为1的位就是m和n不相同的位，所以求x的二进制中1的个数即可

例3，对x的二进制的低八位和高八位交换
int ans= x<<8 | x>>8

例4，用位运算实现加法
分析：x^y是x,y的不进位加法，x&y是x,y都为1的位置，a&b<<1就是进位，所以：a+b = (a^b)+(a&b<<1)，当b为0时，a就是结果

    int aplusb(int a, int b) {
        int a2,b2;
        while(b){
            a2=a^b;
            b2=(a&b)<<1;
            a=a2;
            b=b2;
        }
        return a;
    }