算法-位运算-数字范围按位与

算法-位运算-只出现一次的数字 II

1 题目概述

1.1 题目出处

https://leetcode.cn/problems/bitwise-and-of-numbers-range/description/?envType=study-plan-v2&envId=top-interview-150

1.2 题目描述

2 逐个按位与运算

2.1 思路

最简单的就是直接挨个做与运算，但要注意result = 0、循环到 Integer.MAX_VALUE时的特殊处理。

2.2 代码

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        if(m == Integer.MAX_VALUE){
            return m;
        }
        int result = m;
        for (int i = m + 1; i <= n; i++) {
            result &= i;
            // result=0时，提前退出，因为0和任何数按位与都是0
            // i = Integer.MAX_VALUE时，也需要退出，否则i++后会因为补码的原因直接变为-2147483648了，会死循环
            if(result == 0 ||  i == Integer.MAX_VALUE){
                break;
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.3 时间复杂度

O(n)

2.4 空间复杂度

O(1)

3 公共前缀法

3.1 思路

所有数字从左往右开始找公共前缀，直到第一个不为一致的位，在这之后的都置为0，保留左边的公共前缀。

比如 [4,7]，100 & 101 & 110 & 111，公共前缀为1，则结果为100 即4.

这里不会出现如 101XXX & 111YYY = 101000这样的情况，因为我们题意指定数字是每次等差为1递增的，101XXX 递增到 111YYY 之间，肯定有 110DDD这样的数字，导致和 101XXX和111YYY的第三位1一起相与结果为0。所以只需要考虑最左公共前缀即可。

1. 找公共前缀的方法，就是把m和n一起往右按位移动，并记录下移动次数moveCount，直到m==n为止。
2. 将m往左按位移动moveCount次，得到的结果就是最终结果了

3.2 代码

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        if (m == n) {
            return m;
        }
        if (m == 0) {
            return 0;
        }
        if ((m & n) == 0) {
            return 0;
        }

        int moveCount = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            moveCount++;
        }
        return m << moveCount;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3.3 时间复杂度

O(logn)

3.4 空间复杂度

O(1)

4 统计int每位为1出现次数

4.1 思路

题意中已经明确指出除了一个数字外，其他数字都出现三次，那么我们就按二进制累加数字每一位为1的，最后再对每一位对3取余数。最后余数为1的位置，就是只出现过的一次的数字的二进制组成。把他还原即可

4.2 代码

class Solution {
    public int singleNumber(int[] nums) {
        // 一个int 32位
        int[] counts = new int[32];
        // 统计所有数字
        for(int num : nums) {
            for(int j = 0; j < 32; j++) {
                // 将当前数字按拆成二进制，每位和1与运算，如果不为0就统计
                counts[j] += num & 1;
                // 无符号右移一位，以便计算下一二进制位
                num >>>= 1;
            }
        }

        int res = 0;
        for(int i = 31; i >= 0; i--) {
            // 从高位开始每次处理一位
            res <<= 1;
            // 该二进制位的1出现次数，先对3取余，再和当前位求或运算
            // 比如 1 | 1 = 1 则最高位是出现一次的数字的二进制位
            // 10 | 1 = 11 则次高位也是出现一次的数字的二进制位
            // 100 | 0 = 100 则第三高位不是出现一次的数字的二进制位
            res |= counts[i] % 3;
        }
        return res;
    }
}
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

4.3 时间复杂度

O(N)

4.4 空间复杂度

O(1)