位运算的操作与算法

在上一次的博客中，我们实现了使用位操作去实现四则运算。实现整数的加减乘除。这次我们将讨论位运算在算法中的一些妙用。

位运算可以进行的骚操作

在这里我将使用题目进行示例

题1：找出唯一成对的数

1-1000这1000个数放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空间,能否设计一个算法实现?

这个题目有两个要注意的点

数的范围是1-1000，这个是确定的
不能使用辅助储存空间
只有一个数字g重复

那么我们应该怎么去解决这个题目呢?在这里我们既然讲了位运算，那么肯定是使用|，&，～，^等来解决这些问题。

首先我们得知道：

A ^ A = 0 , A ^ 0 = A

那么我们可以想想，假如我们将题目中的数组与 1～1000进行异或操作那么剩下的值就是那一个重复的值。

简单的来个示例,假如数组是[1,2,3,4,3]

1 ^ 2 ^ 3 ^ 4 ^ 3 ^ 1 ^ 2 ^ 3 ^ 4 = 1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 3 ^ 4 ^ 4 ^ 3 = 0 ^ 3 = 3

import java.util.Arrays;
import java.util.Random;
public class SameWord {
    public static void main(String[] args) {
        // 不重复的数字有1000个
        int N = 1000;
        // 数组的容量为10,其中有一个为重复的
        int[] arry = new int[N + 1];

        for (int i = 0; i < N; i++) {
            arry[i] = i + 1;
        }
        Random random = new Random();
        // 产生1~N的随机数
        int same = random.nextInt(N)+1;
        int position = random.nextInt(N);
        // 将重复的值随机调换位置
        arry[N] = arry[position];
        arry[position] = same;
        // 前面一部分就是为了产生1001大小的数组，其中有一个是重复的
                
        // 进行异或操作 【1^2^3^4……】
        int x = 0;
        for (int i = 0; i < N; i++) {
            x = (x ^ (i+1));
        }
        
        // 对数组进行异或操作
        int y = 0;
        for (int i = 0; i < N + 1; i++) {
            y = (arry[i] ^ y);
        }
        // 打印重复的值
        System.out.println(x^y);
    }
}

题2：找出单个值

一个数组里除了某一个数字之外,其他的数字都出现了两次。请写程序找出这个只出现一次的数字。

emm，假如弄懂了上面一个题目，这个题目就轻而易举了

public void getSingle(){
    int[] a = {1,2,3,2,1,3,4};

    int single = 0;
    for (int i : a) {
        single = single^i;
    }
    System.out.println(single);
}

题三：找出1的个数

请实现一个函数,输入一个整数,输出该数二进制表示中1的个数

例:9的二进制表示为1001,有2位是1

这个题目挺简单的。有2个方向可以去解决

通过移位获得1的个数

1001 & 1 = 1 ， 1001 >> 1 = 100，100 & 1 = 0

public void getNum(){
    int n = 255;
    int count = 0;
    while(n!=0){
        if((n & 1) == 1){
            count ++;
        }
        n = n>>1;
    }
    System.out.println("个数是:"+count);
}

这种解法其实有一定问题的，因为如果去移动负数的话就会凉凉，陷入死循环（负数右移，最左边的那个1会一直存在）。那么我们怎么解决这个方法呢？既然我们不能移动n，那么我们可以移动相与的那个数啊

1001 & 1 = 1， 1<<1 = 10，1001&10 = 0

public void getNum2(){
    int n = 222;
    int flag = 1;
    int count = 0;
    
    while(flag >=1){
        // 这个地方不是n&flag == 1了
        if((n&flag) > 0){
            count ++;
        }
        flag = flag << 1;
    }
    System.out.println("个数是:"+count);
}

我们可以去考虑下这个的时间复杂度。实际上，无论你要求解的数值有多小，它都要循环32次（因为int为4个字节，需要循环32次）。

最高效的解法

这边有个规律：n&(n-1)能够将n的最右边的1去掉。

那么根据这个规律，如果我们将右边的1去掉，去掉的次数也就是二进制中1的个数
```
public void getNum3(){
    int n = 233;
    int count = 0;
    while(n>0){
        count ++;
        n = (n -1)&n;
    }
    System.out.println("个数是:"+count);
}
```

题四：保证不溢出地取整数平均值

求平均值我们一般是使用相加来进行操作的，但是如果值比较大呢，造成溢出怎么办？实际上我们知道溢出就是因为进位造成的，那么我们就可以使用位来解决这个方法。

10 二进制 1010
14 二进制 1110
公共部分： 1010
不同部分的和： 0100
不同部分除以2：0010
平均数 = 1010(相同部分) + 0010(不同部分的平均数) = 1100
因此二者平均数为12

以上的操作我们可以用位运算来替代：

公共部分 = a & b
不同部分的平均值 = (a ^ b) >> 1
平均值 = 公共部分 + 不同部分的平均值 = (a & b) + ((a ^ b) >> 1)

public void aver(){
    int a = 10;
    int b = 220;
    int averNum = (a&b) + ((a^b)>>1);
    System.out.println("平均值是："+averNum);
}

题五：高低位交换

给出一个16位的无符号整数。称这个二进制数的前8位为“高位”，后8位为“低位”。现在写一程序将它的高低位交换。例如，数34520用二进制表示为：
10000110 11011000
将它的高低位进行交换，我们得到了一个新的二进制数：
11011000 10000110
它即是十进制的55430

A | 0 = A

在这个题目（以34520为例）中我们可以先将 10000110 11011000 >> 8右移动8位得到A = 00000000 10000110，10000110 11011000 << 8得到B = 11011000 00000000，然后A | B = 11011000 10000110