有趣的位运算

位运算概述

从现代计算机中所有的数据都以二进制的形式存储在设备中。即0、1两种状态，计算机对二进制进行的运算（+、-、*、/）都叫位运算。示例：

1
2
3

int a = 35;
int b = 47;
int c = a + b;

计算a+b的值，在计算机中就是以二进制进行运算的。所以上面我们所给的int变量会在机器内部先转换为二进制在进行相加：

35:  0 0 1 0 0 0 1 1
47:  0 0 1 0 1 1 1 1
————————————————————
82:  0 1 0 1 0 0 1 0

所以，合理的运用位运算更能显著提高代码在机器上的运行效率。

位运算符

含义	运算符	例子
左移	<<	0011 => 0110
右移	>>	0110 => 0011
按位或	︳	0011 ——- =>1011 1011
按位与	&	0011 ——- =>0011 1011
按位取反	~	0011 =>1100
按位异或 (相同为零不同为一)	^	0011 ——- =>1000 1011

经典运用

不用加减乘除做加法

//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的个数

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 ^ B = C --> C ^ A = B --> C ^ B = A
public void exchange(int a,int y){
    x = x ^ y;
    y = x ^ y;
    x = x ^ y;
}

其他运用

判断一个数的奇偶性

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

两数的中位数

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

两数的平均数

1
2
3

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

以上就是我今天分享的常见位运算的经典问题，其实位运算的应用远远不止这些，在算法方面适当的使用还是很有帮助的。