位运算符

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

位运算符常用方式

用位运算做加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//step1:异或查看两个数进行加法操作后的结果
//step2:与运算计算出想对应的位置的进位结果，然后左移一位
//b代表的是两数相加是否有进位，有的话就继续，没有的话就结束得出相加后的答案
public class Solution{
    public int Add(int a,int b){
        while(b != 0){
            int temp = a ^ b;//计算出相对应的位置相加后的结果
            b = (a & b) << 1;//计算出想对应的位置的进位，然后左移一位
            a = temp;
        }
        return a;
    }
}

//这个其实可以简写成return (a^b)+((a&b)<<1);

用位运算求平均数

1
2
3
public int average(int a,int b){
	return (a & b)+((a ^ b) >> 1);
}

原理:

每一位都0,1有两种情况,所以对应的每一位相加有3种情况

1.(0+0):0&0和0^0都是0

2.(1+0)或(0+1):1&0为0,1^0为1;而1+0为1,所以相加的结果刚好是与的结果,要求平均数所以右移一位,相当于除以二

3.(1+1):1&1为1,1^1为0,而1+1为2,所以刚好是异或的结果刚好是平均数

二进制中1的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution{
    public int NumberOf1(int a){
        if(a == 0||a == 1){
            return a;
        }
        int count = 0;
        while(a != 0){
            count++;
            a = a & (a-1);
        }
        return count;
    }
}

原理:

a = a & (a-1);

a异或a-1的结果刚好为a去掉二进制时的最后一位1的结果

判断一个数的奇偶性

1
2
3
4
5
6
7
public void Test(int a){
    if((a & 1)==0){
        System.out.println("a是偶数");
    }else{
        System.out.println("a是奇数");
    }
}

两数的中位数

1
2
3
4
public void Test(int a,int b){
    //通过位运算不会造成溢出
	int mid = a - ((a - b) >> 1);
}

不使用第三个变量的情况下交换两个变量的值

1
2
3
4
5
6
7
//原理：运用异或的特性
//A ^ B = C --> C ^ A = B --> C ^ B = A
public void exchange(int a,int y){
    x = x ^ y;
    y = x ^ y;
    x = x ^ y;
}

原理:

x = x ^ y;y = x ^ y;x = x ^ y;

z = x ^ y;y = z ^ y;x = z ^ y;