算法通关村第十一关|白银|位运算高频算法题【持续更新】

1.位移

1.1 位1的个数

原题：力扣191.

挨个判断是不是 1 的话需要对整个长度进行遍历，但是采用技巧可以只寻找为 1 的位，然后将其数量记录下来。

public int hammingWeight(int n) {
	int count = 0;
	while (n != 0) {
        n = n & (n - 1);
        count++;
    }
	return count;
}
1
2
3
4
5
6
7
8

1.2 比特位计数

原题：力扣338.

public int[] countBits(int num) {
	int[] bits = new int[num + 1];
	for (int i = 0; i <= num; i++) {
        bits[i] = countOnes(i);
    }
	return bits;
}

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

1.3 颠倒无符号整数

原题：力扣190.

public int reverseBits(int n) {
	int reversed = 0, power = 31;
	while (n != 0) {
        reversed += (n & 1) << power;
        n >>>= 1;
        power--;
    }
	return reversed;
}
1
2
3
4
5
6
7
8
9

1.4 分块翻转无符号整数

在 JDK，Dubbo等源码中常见。

reverseBits(int n) {
    n = (n >>> 16) | (n << 16);
    n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
    n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
    n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
    n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
    return n;
}
1
2
3
4
5
6
7
8

2.加减乘除

2.1 位运算实现加法

原题：力扣371.

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

2.2 递归乘法

原题：力扣面试08.05.

要求写一个递归函数，不能使用 * 运算符，实现两个正整数的相乘。

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

2.3 位运算实现除法

【持续更新】

如果对您有帮助，请点赞关注支持我，谢谢！❤
如有错误或者不足之处，敬请指正！❤
个人主页：星不易 ❤
算法通关村专栏：不易|算法通关村 ❤