算法通关村——位运算

1. 常见的位运算

1.1 与 &

&：两个数对应的位都是1，那么结果才是1
1 & 1 = 1
1 & 0 = 0;
0 & 0 = 0;

1.2 或 |

|: 只要两个数对应的位有一个1，结果就是1
1 | 1 = 1;
1 | 0 = 1;
0 | 0 = 0;

1.3 异或^

^: 只有两个数的位都一样的时候才是返回0，否则返回1
1 ^ 1 = 0
0 ^ 1 = 1
0 ^ 0 = 0;

1.4 取反 ~

~: 就是取反，如果位是1，取反就是0
~1=0
~0=1

2. 移位运算

左移：<< 全部二进制左移若干位(如果左移一位，就是除以2)
右移：>> 全部二进制右移若干位

3. 位1的个数

位1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

3.1 右移

只需要将每一位和1进行与&操作，如果当前位是1，那么就计数
i=0 00000000000000000000000000001011 & …1=1
i=1 00000000000000000000000000000101 & …1=1
i=2 00000000000000000000000000000010 & …1=0
i=3 00000000000000000000000000000001 & …1=1

结果是3

 public int hammingWeight(int n) {int count =0;for(int i=0;i<32;i++){count+=(n>>i)&1;}return count;}

3.2 左移

先设置一个mask之用于左移比较是否位相同
00000000000000000000000000001011 & 1 =0
00000000000000000000000000001011 & 01 = 0
00000000000000000000000000001011 & 001 =0
…
00000000000000000000000000001011 & 00000000000000000000000000001 = 1
00000000000000000000000000001011 & 000000000000000000000000000001 = 0
00000000000000000000000000001011 & 0000000000000000000000000000001 = 1
00000000000000000000000000001011 & 00000000000000000000000000000001 = 1

 public int hammingWeight(int n) {int count =0;int mask = 1;for(int i=0;i<32;i++){if((n & mask) !=0){count++;}mask<<=1;}return count;}

3.3 n&(n-1)

将二进制最后一个1变成0,直到n最后变成0
00000000000000000000000000001011 & 00000000000000000000000000001010 = 00000000000000000000000000001010
count = 1;

00000000000000000000000000001010 & 00000000000000000000000000001001 = 00000000000000000000000000001000
count = 2;

00000000000000000000000000001000 & 00000000000000000000000000000111 =
0000000000000000000000000000000
count =3;

 public int hammingWeight(int n) {int count =0;while(n!=0){n=n&(n-1);count++;}return count;}

这种效率也是比较高的，经常使用，前两个位移都是需要遍历32次，而n&(n-1)只需要n为0的时候就退出
在这里插入图片描述

4. 比特位计数

比特位计数
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数，返回一个长度为 n + 1 的数组 ans 作为答案。
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

4.1 右移

这里面的的计算1的个数就可以采用之前的( n>>i ) &1,其中n是当前的值，而i是右移的位数
很显然，因为元素大小是在0-n这个范围内，所以是按照相应下标就可以知道当前的值，那么再次&1比较，然后右移，就可以算出1的个数，然后赋值给数组。

    public int[] countBits(int n) {int [] res = new int [n+1];for(int i=0;i<=n;i++){for(int j=0;j<32;j++){res[i] += (i >>j)&1;}}return res;}

此方法缺点在于时间耗费比较长，因为每个元素都要遍历右移32次，才能计算1的个数

4.2 位的性质 n&(n-1)

public int[] countBits(int n) {int count =0;int [] res = new int [n+1];for(int i=0;i<=n;i++){res[i] = getOneCount(i);}return res;}public int getOneCount(int x){int count =0;while(x!=0){x=x&(x-1);count++;}return count;}

5. 颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。提示：请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

5.1 逐位颠倒

一开始想的是直接反转这个二进制数，直接使用Integer的reverse是肯定不行的。
首先先获取到n的最后一位，然后n进行逻辑右移，和reversed反转数进行相加，直到n变成0
00000010100101000001111010011100右移31位，最低位是0
n逻辑右移1位
00000001010010100000111101001110右移30位，最低位是0

 public int reverseBits(int n) {int reversed =0;int length = 31;while(n!=0){reversed += (n&1)<<length;// 逻辑右移n >>>= 1;length--;}return reversed;}

6. 两整数之和

两整数之和
给你两个整数 a 和 b ，不使用运算符 + 和 - ，计算并返回两整数之和。
输入：a = 2, b = 3
输出：5

6.1 异或+与

2：010
3：011
5：101
可以看出相同为0，不同为1，这是异或，对于不需要进位的部分采用a^b , 但是需要关注首位是0还是1，进位部分就要采用a&b,只有两个都是1的时候才需要进位。

public int getSum(int a, int b) {while(b!=0){int sign = (a & b) << 1;a = a ^ b;b = sign;}return a;}

a&b= 010 010 << 1 = 100 sign = 100
a^b= 001 a = 001
b = 100

a&b = 100 & 001 = 000 000<1 =000 sign =0
a^b = 100 ^ 001 = 101 a = 101
b =0
退出

a=101 =5

7. 递归乘法

递归乘法
递归乘法。写一个递归函数，不使用 * 运算符，实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
输入：A = 3, B = 4
输出：12

7.1 位运算

例如3 * 4，就是3 * 2 ^ 2,也就是3<<2，左移两位
例如1 * 10，就是1 （2+8）就是1 * 2^1+12 ^3 就是1 <<1 +1<<3

先找出两者之间的最小值和最大值，选取最小值作为乘数的原因是次数较少，然后判断min的最右一位是不是1，是1就添加该位到结果中，然后最小值右移一位

 public int multiply(int A, int B) {int add = 0;int min = Math.min(A,B);int max = Math.max(A,B);for(int i=0;min!=0;i++){if((min & 1) == 1){add  += max<< i;}min >>= 1;}return add;}