一. 位操作符

1. & 与运算

两个位都是 1 时，结果才为 1，否则为 0。
特性：

  • a&(a-1) 去除a中最后的1

    2. | 或运算

    两个位都是 0 时，结果才为 0，否则为 1。

    3. ^ 异或运算

    两个位相同则为 0，不同则为 1。
    概念：找不同。可用来去除冗余
    特性：

  • 0异或任何数＝任何数

  • 1异或任何数 = 任何数取反

  • 任何数异或自己＝把自己置0**

    4. ~ 取反运算

    0 则变为 1，1 则变为 0。

    5. << 左移运算

    向左进行移位操作，高位丢弃，低位补 0。

    6. >> 右移运算

    向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位。



    二. 运用

    1. 实现乘除

    a<<1 == a*2;
    a>>1 == a/2;

    2. 指定位取反

    3. 两值交换

    a^=b; b^=a; a^=b;

    4. 判断奇偶

    0==(a&1)

    5. 交换符号

    (~a)+1

    6. 求绝对值

    int i = a >> 31; //正数i=0; 负数i=-1;
    i == 0 ? a : (~a + 1);
    优化：((a^i)-i) //正数((a^0)-0); 负数((a^0xffffffff)-(-1)) 等同于取反+1

    7. 高低位交换(无符号)

    a=(a >> 8) | (a << 8)

    8. 二进制逆序

    将无符号数的二进制表示进行逆序，求取逆序后的结果，如

    1. 数34520的二进制表示：
    2. 10000110 11011000
    3. 逆序后则为：
    4. 00011011 01100001
    5. 它的十进制为7009

    在字符串逆序过程中，可以从字符串的首尾开始，依次交换两端的数据。在二进制中使用位的高低位交换会更方便进行处理，这里我们分组进行多步处理。

  • 第一步:以每 2 位为一组，组内进行高低位交换

    1. 交换前： 10 00 01 10 11 01 10 00
    2. 交换后： 01 00 10 01 11 10 01 00

  • 第二步：在上面的基础上，以每 4 位为 1 组，组内高低位进行交换

    1. 交换前： 0100 1001 1110 0100
    2. 交换后： 0001 0110 1011 0001

  • 第三步：以每 8 位为一组，组内高低位进行交换

    1. 交换前： 00010110 10110001
    2. 交换后： 01100001 00011011

  • 第四步：以每16位为一组，组内高低位进行交换

    1. 交换前： 0110000100011011
    2. 交换后： 0001101101100001

    对于上面的第一步，依次以 2 位作为一组，再进行组内高低位交换，这样处理起来比较繁琐，下面介绍另外一种方法进行处理。先分别取原数 10000110 11011000 的奇数位和偶数位，将空余位用 0 填充：

    原数：  10000110 11011000
奇数位： 10000010 10001000
偶数位： 00000100 01010000

    再将奇数位右移一位，偶数位左移一位，此时将两个数据相或即可以达到奇偶位上数据交换的效果：

    原数：  10000110 11011000
奇数位右移一位： 0 10000010 1000100
偶数位左移一位：0000100 01010000 0
两数相或得到： 01001001 11100100

    上面的方法用位操作可以表示为：

  • 取a的奇数位并用 0 进行填充可以表示为：a & 0xAAAA

  • 取a的偶数为并用 0 进行填充可以表示为：a & 0x5555 因此，上面的第一步可以表示为：
    a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1)
    同理，可以得到其第二、三和四步为：
    a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2)
    a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4)
    a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8)
    因此整个操作为：
    unsigned short a = 34520;
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1);
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2);
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4);
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8);

    9. 位操作统计二进制中 1 的个数

    count = 0  
while(a){  
a = a & (a - 1);  //消去
count++;  
}

    10.