前言

在面试和比赛中，位运算是一个很灵活的应用，今天的博文带大家一起熟悉一些常见的位运算，并针对每道题目的位运算知识进行相应的示例解析。

一、位运算

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。
常见的位运算有：

x<<1 == x * 2
x>>1 == x / 2
a ^ b
a | b
a & b

二、前置知识：

0-原码

	原码是计算机机器数中最简单的一种形式，数值位就是真值的绝对值，符号位为“0”时表示正数，符号位为“1”时表示负数，原码又称带符号的绝对值。为了方便整数和小数区别，整数的符号位与数值位之间用“，”隔开，小数的符号位与数值位之间用“.”隔开。

1-反码

    正数的反码与其原码相同；负数的反码是对正数逐位取反，符号位保持为1.

2-补码

	正数的补码与其原码相同；负数的补码是在其反码的末位加1。

3-左移

	num1 = 1;
	num2 = num1 << 1;  [0001 << 1] ->[0010] = 2;
	即num2 = 2;
	总结：
	1)左移是将指定数字的二进制位所有位置向左移动，低位补零。
	2)左移n位相当于乘以2^n;

4-右移

	num1 = 4;
	num2 = num1 >> 1;  [0100 >> 1] ->[0010] = 2;
	即num2 = 2;
	总结：
	1)右移是将指定数字的二进制位所有位置向右移动，高位补零。
	2)右移n位相当于除以2^n;

5-按位与

	num1 =  3;
	num2 = 4;
	num3 = num1 & num2;
				num1 : [0011]
				num2: [0100]
				num3: [0000]
	即num3 = 0;
	按位与相当于将两个数字的每个二进制位置各自进行按位与操作。
	1 & 1 =  1;
	1 & 0 = 0;
	0 & 1 = 0;
	0 & 0 = 0;

6-按位或

	num1 =  3;
	num2 = 4;
	num3 = num1 | num2;
				num1 : [0011]
				num2: [0100]
				num3: [0111]
	即num3 = 7;
	按位与相当于将两个数字的每个二进制位置各自进行按位或操作。
	1 | 1 =  1;
	1 | 0 = 1;
	0 | 1 = 1;
	0 | 0 = 0;

7-按位异或

	num1 =  3;
	num2 = 6;
	num3 = num1 ^ num2;
				num1 : [0011]
				num2: [0110]
				num3: [0101]
	即num3 = 5;
	按位与相当于将两个数字的每个二进制位置各自进行按位异或操作。
	1 ^ 1 =  0;
	1 ^ 0 = 1;
	0 ^ 1 = 1;
	0 ^ 0 = 0;
	异或操作中，位值相同为零，不同为一。

8- >>>和>>的区别

	>>>:不带符号位右移；
	>>  :带符号位右移

9-无进位相加

	在两个数值进行异或操作时，
	如：num1 = 4， num2 = 3；
		num3 = num1 + num2 此时可以写成num1 ^ num2
						num1 =[0100]
						num2= [0011]
						num3 =[0111] = 7;
		num5 = 4, num6 = 5;
		num7 = num5 + num6 此时不可以写成num5 ^ num6
						num5 =[0100]
						num6= [0101]
						num7 =[0011] = 3;

在这里插入图片描述

根据第九个前置知识点引申出力扣算法中剑指Offer65题：

题目描述及示例

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:
输入: a = 1, b = 1
输出: 2

提示：
a, b 均可能是负数或 0
结果不会溢出 32 位整数

代码如下：

class Solution {
    public int add(int a, int b) {
        while(b != 0)
        {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
}

代码解析

class Solution {
    public int add(int a, int b) {//不使用四则运算实现两数相加函数
        while(b != 0)//核心代码
        {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        //假设a = 4， b = 5；
        while（5 != 0）
        {
        	第一次循环
        	carry = (4 & 5) << 1;
        			0100 & 0101 = 0100
        			0100 << 1 = 1000
        	a = 4 ^ 5 = 0001;
        	b = 8;
        	第二次循环
        	carry = (1 & 8) << 1;
        			0001 & 1000 = 0000
        			0000 << 1 = 0000
        	a = 1 ^ 8 = 1001 = 9;
        	b = 0;
        }
        return a;
    }
}