算法必刷系列之位运算

位运算

位运算既能在某些条件下提升运算速度，又能在某些条件下节省运算内存。计算机底层涉及大量位运算，位运算可以替代加加减乘除。位运算的基本运算单元是bit，相比于整数的int占据四个字节，大量节约运算空间，适用于海量数据处理

位1的个数

leetcode191
通过1移位并与给出的数字进行与运算判断对应位置是否位1

public int hammingWeight(int n) {
    int count = 0;
    for(int i=0;i<32;i++){
        int res = n&(1<<i);
        if(res!=0){
            count++;
        }
    }
    return count;
}
1
2
3
4
5
6
7
8
9
10

比特位计数

leetcode338
将某个数字与该数字减1的数字进行与运算，可以使该数字的最后一个为1的bit位变为0，重复操作，直至该数字为0，操作次数就是bit位1的个数

public int[] countBits(int n) {
    int[] counts = new int[n+1];
    for(int i=0;i<n+1;i++){
        counts[i] = count(i);
    }
    return counts;
}

public int count(int n){
    int count = 0;
    while(n!=0){
        n=n&(n-1);
        count++;
    }
    return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

颠倒32位无符号整数

leetcode190
不断从无符号整数的末尾取比特位，左移31-对应位置，遍历结束之后，完成反转

public int reverseBits(int n) {
    int reverseN = 0;
    for(int i=0;i<32;i++){
        int res = n&(1<<i);
        if(res!=0){
            reverseN += (1<<(31-i));
        }
	}
}  
1
2
3
4
5
6
7
8
9

两整数之和

leetcode371
通过与运算计算进位，通过亦或运算进行不包括进位的加法，然后再将进位相加，重复这个过程，直至进位为0

public int getSum(int a, int b) {
     while(b!=0){
         int sign = (a&b)<<1;
         a=a^b;
         b=sign;
     }
     return a;
}
1
2
3
4
5
6
7
8

递归乘法

leetcode08.05
通过将乘数中较小的数字拆分成2的n次方的形式，并通过移位运算实现乘法，之所以选择较小的乘数是因为运算次数少

public int multiply(int A, int B) {
    int res = 0;
    int min = Math.min(A,B);
    int max = Math.max(A,B);
    for(int i=0;i<32;i++){
        int temp = min&(1<<i);
        if(temp!=0){
            res+=(max<<i);
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12

4KB内存寻找重复元素

给定一个数组，数组中包含N个数字，N最大为32000，数组中存在重复数字，且N的大小不确定，要求用4KB内存实现输出数组中的所有重复数字

32000个数字使用int类型存储，内存是肯定大于4KB的。我们可以考虑使用bit数组来实现，数组的下标代表数字，bit位为0代表没有出现，bit位为1代表已经出现，进行输出

public class Bit {
    public void checkDuplicates(int[] array){
        BitSet bs = new BitSet(32000);
        for (int i = 0; i < array.length; i++) {
            int num = array[i];
            int num0 = num-1;
            if(bs.get(num0)){
                System.out.println(num);
            }else {
                bs.set(num0);
            }
        }
    }
}

class BitSet {
    int[] bitSet;

    public BitSet(int size) {
        this.bitSet = new int[size >> 5];
    }

    boolean get(int pos) {
        int wordNumber = pos >> 5;
        int bitNumber = pos & 0x1F;
        return (bitSet[wordNumber]&(1<<bitNumber))!=0;
    }
    
    void set(int pos){
        int wordNumber = pos >> 5;
        int bitNumber = pos & 0x1F;
        bitSet[wordNumber] |= (1<<bitNumber);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34