与运算

这里的与运算并不是平常的bool运算，而是按位与。这种运算比加减法快

符号： &

例： 1010&1000=1000 1001&0110=0000

含义： 1&1=1,1&0=0,0&1=0,0&0=0，只要不是两个都是,1，那么结果就是0

应用：

  • 替换指定位的值

一个典型应用就是大小写转换，如果平常转换我们可能要写一大堆，但是经过仔细观察后发现大写字母和小写字母之间差距只有第5位，如果第五位为0，就是大写字母，为1就是小写字母，所以只要a&0b11011111这一段代码就可以完成小写到大写的转换

  • 清零

通过 a&0b00000000 ,可以快速的把某个数变成零

  • 消去最后一位 1

x & (x-1) 例如 x 1010 x-1 1001 ，计算之后1000。减1就是让最小的那个1变成0然后后面全是1

  • 找到最小一位1

x & (-x) 在lowbit函数中用到， -x=~（x-1），大于最小一位1的都由于取反变成0，然后最小一位1及其后面本来是0111…,取反变成1000…，而原来是100…，所以最终是00…0100…

或运算

符号： |

例： 1010|1000=1010 1001|0110=1111

含义： 1|1=1,1|0=1，0|1=1，0|0=0

应用：

  • 设定某一个数据位为1，例如想把第五位设为1，只要 a|0b00100000

异或

符号： ^

例： 1010^1000=0010, 1001^0110=1111

含义：1^1=0,1^0=1,0^1=1,0^0=0，同为假，异为真

应用：

  • x^11111…=~x;
  • 异或满足交换率，结合率

*x^x=0,x^0=x,自己是自己的逆元，0是幺元

  • a^b^a=b,因此可以用这种性质做许多应用，一个应用就是交换两个变量的值
void swap(int*& a,int*& b)
{
    *a=*a ^ *b;  //a=a^b
    *b=*a ^ *b; //b=a^b^b=a
    *a=*a ^ *b; //a=a^b^a=b
}

另外还可以用来检查重复数或者在其余都是偶数个重复数字中找到一个奇数

例：1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现
一次。每个数组元素只能访问一次

将所有的数全部异或，得到的结果与1^2^3^…^1000的结果进行异或，得到的结果就是重复数。

按位非

符号： ~

例： ~ 1001=0110， ~1010=0101

含义： ~1=0，~0=1 ,取反

应用：

  • 对于有符号数 ~a=-(a+1),因为一般采用补码，而补码的负数就是正数-1再取反得到，所以~(a-1)=-a，可得~a=-(a+1)

  • 把最低位变成0，a&~1

    左移

符号： <<

例 00001010<<1 => 00010100

含义： 把所有的位向左移位，高位删去，低位补零，相当于乘上2的n次方

注意：如果移动次数超过了最高位，那么这是一个未定义行为。所以不同编译器，不同cpu对其有不同解释。gcc会将其自动变成0，而微软的编译器会先将移动位数模上最大位数然后再左移相应位数。cpu中也是取模的方式。

例如

int a=1;
b=a<<40;//此时b=0，因为这个命令是在编译器中完成的
a<<=40;//此时a！=0，因为这个命令是在cpu中完成的

右移

符号： >>

含义 将所有位向右移位，高位视情况而定，低位舍弃

视情况而定是因为实际上有两种右移，第一种是逻辑右移，第二种是算术右移

  • 逻辑右移，高位直接取0
  • 算术右移，高位要看情况，如果原来最高位是0，则取0。如果最高位是1，则后面加的都是1.

逻辑右移的符号： >>>(java)

那什么时候用逻辑右移还是算术右移呢？一般来说，有符号数算术右移，无符号数逻辑右移。因为有符号数用的是补码，如果是负数右移最高位补1才能让这个数还是负数

应用：

  • 不用-号把1变成-1
    int a=1;
    a>>=31;//最高位为1，其余都为0
    a<<=31;//都为1

右移运算对整数的影响

右移运算相当于除2，之后低位相当于小数点后面的数字。这时我们把它截断相当于取整，对于无符号数和有符号数中的非负数，这个取整是没什么影响的，但对于有符号数中的负数，取整却与除法取整有所偏差。

除法取整是趋向于零。也就是说，非负数向下取整，负数向上取整。而右移确是把小数后面的数全部舍弃，就相当于让这个数更小了。

例如： 假如右移后是 -1234.32423，结果是-1235.因为把小数点舍弃会使这个数更小。

有一种情况除外。就是右移产生的小数点位中全是0，这时舍弃它并不会产生影响，所以不会发生向下取整。

为了解决这个问题，一种办法就是 (x+2^k-1)>>k，为了加快速度，可以写成(x+1<<k-1)>>k

现在来看这个式子的正确性，当最后几位全为0时，例如1000000右移三位，那么2^3-1=0b111,因为本来这个结果就是正确答案，现在加上111并没有改变它的值，0b1111000.111后面三位舍弃与原来相同，因此这个时候结论正确

如果后面不是全为0，那么这时必定产生进位，例如1101右移三位那么加上之后必定会使第四位进一位，这时我们再右移三位，便相当于让原来的答案加一，达到了向上取整的效果

最后，只有在有符号数中的负数中才要采用这种算法，在非负数中直接右移即可