CodeArena

常用的位操作

Java中的位操作符

::: warning 注意

Java中位操作符的操作数只能是整型（byte、short、int、long）和字符型数据（char）。
Java中位操作符一共有7个，其中4个是位逻辑运算符，3个是移位运算符。
使用按位操作符时要注意：相等（==）与不相等（!=）的优先级在按位操作符之上！这意味着，位运算符的优先级极小，所以使用位运算符时，最好加上括号。

:::

4个位逻辑运算符

位逻辑运算符包括按位取反（~）、按位与（&）、按位或（|）和按位异或（^）4种。
- 与操作符 “&”，如果两个输入位都是 1，那么输出位是 1，否则输入位是 0。【对应位全都为1，则为1】
- 或操作符 “|” ，如果两个输入位有一个是 1，那么输出位是 1，只有两个输入位都是 0，输出位才是 0。【对应位含有1，则为1】
- 异或运算符 “^”，如果两个输入位都为 1 或者都为 0，那么输出位是 0，否则输出位是 1。【对应位相同，则为0，反之为1】
- 非运算符 “~”，这个一元操作符，只能对一个数操作，规则是输出位与输入位相反。【一元操作符，输入1，则输出0；输入0，则输出1】

1
@Test
2
public void test() {
3
    //转化为二进制：0101
4
    int num1 = 5;
5
    //转化为二进制：1001
6
    int num2 = 9;
7
    //与运算，二进制结果为 0001，打印结果为 1
8
    System.out.println(num1 & num2);
9
    //或运算，二进制结果为 1101，打印结果为 13
10
    System.out.println(num1 | num2);
11
    //异或运算，二进制结果为 1100，打印结果为 12
12
    System.out.println(num1 ^ num2);
13
    //非运算，打印结果 -6
14
    System.out.println((~num1));
15
    //非运算，二进制结果为 11111111 11111111 11111111 11111010
2 collapsed lines
16
    System.out.println(Integer.toBinaryString(~num1));
17
}

::: tip 补充

数字的二进制表现形式为 “有符号的二进制补码”。
- 原码：数字的二进制表示法，最高位为符号位，“ 0 ” 为正，“ 1 ” 为负。
- 反码：正数的反码与原码相同，负数的反码对原码逐位取反，符号位除外。
- 补码：正数的补码与原码相同，负数的补码在其反码末位加 1。
- 负数的二进制算法（以 -6 为例，int类型占 4 个字节， 1 个字节是 8 位）：
  - 求-6 的原码，即：10000000 00000000 00000000 00000110
  - 求该二进制数的反码，即：11111111 11111111 11111111 11111001
  - 对以上求得的二进制数加 1，即：11111111 11111111 11111111 11111010

:::

::: tip 说明

位逻辑运算符用来操作整数的二进制位，会对两个参数中对应的位执行布尔代数运算，并最终生成一个结果。

:::

3个移位运算符

移位运算符包括左移（<<）、右移（>>）和无符号右移（>>>）3种。
- 左移位操作符 “<<” 按照操作符右侧指定的位数将操作符左边的操作数向左移动（低位补零）。【左移之后，低位补0】
- “有符号”右移位操作符 “>>” 按照操作符右侧指定的位数将操作符左边的操作数向右移动。该操作符使用 “符号扩展”：若符号为正，则高位插入 0；若符号为负，则高位插入 1。【右移之后，高位进行符号扩展】
- “无符号”右移位操作符 “>>>”，该操作符使用 “零扩展”，无论正负，都在高位插入 0。【右移之后，高位进行零扩展】

1
@Test
2
public void test() {
3
    //二进制 1111;
4
    int i = 15;
5
    //向右边移动两位，二进制结果为 0011，打印结果为 3
6
    System.out.println(i >> 2);
7
    //向左边移动两位，二进制结果为 111100，打印结果为 60
8
    System.out.println(i << 2);
9
}

移位运算符可以与等号组合使用（<<= 或 >>= 或 >>>=），表示操作符左边的值会移动由右边数值指定的位数，再将得到的结果赋给左边的变量。
在数字没有溢出的前提下，对于正数和负数，左移一位都相当于乘以2的1次方，左移n位就相当于乘以2的n次方，右移一位相当于除2，右移n位相当于除以2的n次方。

1
@Test
2
public void test() {
3
    int i = 10;
4
    // 左移1位，相当于乘2的1次方
5
    System.out.println(i << 1);// 20
6
    // 左移4位，相当于乘2的4次方
7
    System.out.println(i << 4);// 160
8
    // 右移1位，相当于除2的1次方
9
    System.out.println(i >> 1);// 5
10
    // 左移3位，相当于除2的3次方
11
    System.out.println(i >> 3);// 1
12
}

::: tip 说明

移位操作符的运算对象也是二进制的 “位”，但是只能用来处理整数类型。

:::

::: warning 注意

逻辑运算符包括逻辑与（&&）、逻辑或（||）和逻辑非（!），前两个是二元运算符，后一个是一元运算符。

:::

参考：https://www.cnblogs.com/blknemo/p/14141417.html

几个有趣的位操作

利用或操作 | 和空格将英文字符转换为小写

1
('a' | ' ') = 'a'
2
('A' | ' ') = 'a'

利用与操作 & 和下划线将英文字符转换为大写

1
('b' & '_') = 'B'
2
('B' & '_') = 'B'

利用异或操作 ^ 和空格进行英文字符大小写互换

1
('d' ^ ' ') = 'D'
2
('D' ^ ' ') = 'd'

以上操作能够产生奇特效果的原因在于 ASCII码。字符的ASCII码其实就是数字，恰巧这些字符对应的数字通过位运算就能得到正确的结果。

1
@Test
2
public void test() {
3
    // 测试和空格进行按位或操作转为小写字母
4
    int i1 = 'a' | ' ';
5
    int j1 = 'A' | ' ';
6
    log.debug("{},{}", (char) i1, (char) j1);//a,a
7
    // 测试和下划线进行按位与操作转为大写字母
8
    int i2 = 'a' & '_';
9
    int j2 = 'A' & '_';
10
    log.debug("{},{}", (char) i2, (char) j2);//A,A
11
    // 测试和空格进行按位异或操作进行大小写转换
12
    int i3 = 'a' ^ ' ';
13
    int j3 = 'A' ^ ' ';
14
    log.debug("{},{}", (char) i3, (char) j3);//A,a
15
}

判断两个数是否异号

1
int x = -1, y = 2;
2
boolean f = ((x ^ y) < 0); // true
3

4
int x = 3, y = 2;
5
boolean f = ((x ^ y) < 0); // false

不用临时变量交换两个数

1
int a = 1, b = 2;
2
a ^= b;
3
b ^= a;
4
a ^= b;
5
// 现在 a = 2, b = 1
6
// 或者
7
b ^= a;
8
a ^= b;
9
b ^= a;

加一

1
int n = 1;
2
n = -~n;
3
// 现在 n = 2

减一

1
int n = 2;
2
n = ~-n;
3
// 现在 n = 1

::: tip 位操作的黑科技玩法

有一个叫做Bit Twiddling Hacks的外国网站收集了几乎所有位操作的黑科技玩法。
网址：http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel

:::

n&(n-1)的运用

n & (n-1) 是算法中常见的位操作，作用是消除数字 n 的二进制表示中的最后一个 1。
其核心逻辑就是，n - 1 一定可以消除最后一个 1，同时把其后的 0 都变成 1，这样再和 n 做一次 & 运算，就可以仅仅把最后一个 1 变成 0 了。

1、计算汉明权重（Hamming Weight）

LeetCode相关题目：位1的个数

就是让你返回 n 的二进制表示中有几个 1。因为 n & (n - 1) 可以消除最后一个 1，所以可以用一个循环不停地消除 1 同时计数，直到 n 变成 0 为止。

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

2、判断一个数是不是 2 的指数

LeetCode相关题目：2的幂

一个数如果是 2 的指数，那么它的二进制表示一定只含有一个 1：

1
2^0 = 1 = 0b0001
2
2^1 = 2 = 0b0010
3
2^2 = 4 = 0b0100

如果使用 n & (n-1) 的技巧就很简单了（注意运算符优先级，括号不可以省略）：

1
public boolean isPowerOfTwo(int n) {
2
    if (n <= 0) return false;
3
    n = n & (n - 1);
4
    return n == 0;
5
}
6
//或者
7
public boolean isPowerOfTwo(int n) {
8
  // 一句代码解决问题
9
    return n > 0 && ((n & (n - 1)) == 0);
10
}

a^a=0的运用

::: tip 异或运算的性质

一个数和它本身做异或运算结果为 0，即 a ^ a = 0；一个数和 0 做异或运算的结果为它本身，即 a ^ 0 = a。
满足结合律和交换律。
由于异或运算满足交换律和结合律，所以总是能把成对儿的数字消去，留下缺失的那个元素。

:::

1、查找只出现一次的元素

LeetCode相关题目：只出现一次的数字

把所有数字进行异或，成对儿的数字就会变成 0，落单的数字和 0 做异或还是它本身，所以最后异或的结果就是只出现一次的元素。

1
// 满足结合律和交换律
2
// 以[4, 1, 2, 1, 2]为例
3
0 ^ 4 ^ 1 ^ 2 ^ 1 ^ 2
4
0 ^ 4 ^ (1 ^ 1) ^ (2 ^ 2)
5
0 ^ 4 ^ (0 ^ 0)
6
0 ^ 4 ^ 0
7
(0 ^ 0) ^ 4
8
0 ^ 4
9
4

1
public int singleNumber(int[] nums) {
2
    int res = 0;
3
    for (int n : nums) {
4
        res ^= n;
5
    }
6
    return res;
7
}

2、寻找缺失的元素

LeetCode相关题目：丢失的数字

给一个长度为 n 的数组，其索引应该在 [0,n)，但是现在你要装进去 n + 1 个元素 [0,n]，那么肯定有一个元素装不下，请找出这个缺失的元素。
思路一：把这个数组排个序，然后遍历一遍，就可以很容易的找到缺失的那个元素

1
public int missingNumber(int[] nums) {
2
    Arrays.sort(nums);
3
    for (int i = 0; i < nums.length; i++) {
4
        if (i != nums[i]) {
5
            return i;
6
        }
7
    }
8
    return nums.length;
9
}

思路二：利用数据结构的特性，用一个 HashSet 把数组里出现的数字都储存下来，再遍历 [0,n] 之间的数字，去 HashSet 中查询，也可以很容易查出那个缺失的元素。

1
public int missingNumber(int[] nums) {
2
    HashSet<Integer> set = new HashSet<>();
3
    for (int num : nums) {
4
        set.add(num);
5
    }
6
    for (int i = 0; i <= nums.length; i++) {
7
        if (!set.contains(i)) {
8
            return i;
9
        }
10
    }
11
    return 0;
12
}

思路三：利用等差数列求和公式，题目的意思可以这样理解：现在有个等差数列 0, 1, 2,..., n，其中少了某一个数字，那这个数字就是 sum(0,1,..n) - sum(nums) 。

1
public int missingNumber(int[] nums) {
2
    int sum1 = (1 + nums.length) * nums.length / 2;
3
    int sum2 = 0;
4
    for (int num : nums) {
5
        sum2 += num;
6
    }
7
    return sum1 - sum2;
8
}

思路四：利用一个数和它本身做异或运算结果为 0，一个数和 0 做异或运算还是它本身的性质。

::: tip 异或运算满足交换律和结合律

1
2 ^ 3 ^ 2 = 3 ^ (2 ^ 2) = 3 ^ 0 = 3

:::

比如说 nums = [0,3,1,4]：

假设先把索引补一位，然后让每个元素和自己相等的索引相对应：
通过上图可以发现：只要把所有的元素和索引做异或运算，成对儿的数字都会消为 0，只有这个落单的元素会剩下。

1
public int missingNumber(int[] nums) {
2
// 时间复杂度O(N)
3
// 空间复杂度O(1)
4
    int result = 0;
5
    // 把索引全都异或一遍，范围是[0,n]，左右都包括，即n+1个数
6
    for (int i = 0; i <= nums.length; i++) {
7
        result ^= i;
8
    }
9
    // 把nums中的值全都异或一遍，即n个数
10
    for (int num : nums) {
11
        result ^= num;
12
    }
13
    return result;
14
}

1
public int missingNumber(int[] nums) {
2
// 时间复杂度O(N)
3
// 空间复杂度O(N)
4
    // list放置索引和nums中的所有值，后续依次对list中的数据进行异或操作
5
    ArrayList<Integer> list = new ArrayList<>();
6
    // 把索引全都加入list
7
    for (int i = 0; i <= nums.length; i++) {
8
        list.add(i);
9
    }
10
    // 把nums中的值全都加入list
11
    for (int num : nums) {
12
        list.add(num);
13
    }
14
    // 对list中的所有值进行异或操作
15
    int result = 0;
6 collapsed lines
16
    for (Integer integer : list) {
17
        result ^= integer;
18
    }
19
    return result;
20
}
21
// 本思路直接将题目演变成了LeetCode的第136题目，即只出现一次的数字。

两道常考的阶乘算法题

题一

LeetCode相关题目：阶乘后的零

输入一个非负整数 n，请你计算阶乘 n! 的结果末尾有几个 0。
比如说输入 n = 5，算法返回 1，因为 5! = 120，末尾有一个 0。
两个数相乘结果末尾有 0，一定是因为两个数中有因子 2 和 5，因为 10 = 2 x 5。
- 问题转化为：n! 最多可以分解出多少个因子 2 和 5？
- 比如说 n = 25，那么 25! 最多可以分解出几个 2 和 5 相乘？这个主要取决于能分解出几个因子 5，因为每个偶数都能分解出因子 2，因子 2 肯定比因子 5 多得多。25! 中 5 可以提供一个，10 可以提供一个，15 可以提供一个，20 可以提供一个，25 可以提供两个，总共有 6 个因子 5，所以 25! 的结果末尾就有 6 个 0。
- 问题转化为：n! 最多可以分解出多少个因子 5？
- 难点在于像 25，50，125 这样的数，可以提供不止一个因子 5，怎么才能不漏掉呢？
假设 n = 125，来算一算 125! 的结果末尾有几个 0：
- 首先，125 / 5 = 25，这一步就是计算有多少个像 5，15，20，25 这些 5 的倍数，它们一定可以提供一个因子 5。
- 然后，像 25，50，75 这些 25 的倍数，可以提供两个因子 5，那么我们再计算出 125! 中有 125 / 25 = 5 个 25 的倍数，它们每人可以额外再提供一个因子 5。
- 最后，我们发现 125 = 5 x 5 x 5，像 125，250 这些 125 的倍数，可以提供 3 个因子 5，那么我们还得再计算出 125! 中有 125 / 125 = 1 个 125 的倍数，它还可以额外再提供一个因子 5。
- 125! 最多可以分解出 25 + 5 + 1 = 31 个因子 5，也就是说阶乘结果的末尾有 31 个 0。

1
public int trailingZeroes(int n) {
2
    /*
3
        n / 5
4
        n / 5 / 5
5
        n / 5 / 5 / 5
6
    */
7
    int result = 0;
8
    // d有可能越界
9
    long d = 5;
10
    // n可以分解出多少个因子5
11
    while (d <= n) {
12
        result += (n / d);
13
        d *= 5;
14
    }
15
    // d>n的时候退出循环，n如果是int的最大值，那么d使用int类型有可能越界，所以使用long类型
2 collapsed lines
16
    return result;
17
}

1
public int trailingZeroes(int n) {
2
    /*
3
        n / 5
4
        n / 5 / 5
5
        n / 5 / 5 / 5
6
    */
7
    int result = 0;
8
    for (int i = 1; Math.pow(5, i) <= n; i++) {
9
        result += (n / Math.pow(5, i));
10
    }
11
    return result;
12
}

1
public int trailingZeroes(int n) {
2
    /*
3
    n / 5
4
    n / 5 / 5
5
    n / 5 / 5 / 5
6
    */
7
    int res = 0;
8
    for (int d = n; d / 5 > 0; d = d / 5) {
9
        res += d / 5;
10
    }
11
    return res;
12
}

时间复杂度是底数为 5 的对数，也就是 O(logN)。

题二

LeetCode相关题目：阶乘函数后K个零

输入一个非负整数 K，请你计算有多少个 n，满足 n! 的结果末尾恰好有 K 个 0。
比如说输入 K = 1，算法返回 5，因为 5!,6!,7!,8!,9! 这 5 个阶乘的结果最后只有一个 0，即有 5 个 n 满足条件。
一个直观地暴力解法就是穷举，因为随着 n 的增加，n! 肯定是递增的，trailingZeroes(n!) 肯定也是递增的，伪码逻辑如下：

1
int res = 0;
2
for (int n = 0; n < +inf; n++) {
3
    if (trailingZeroes(n) < K) {
4
        continue;
5
    }
6
    if (trailingZeroes(n) > K) {
7
        break;
8
    }
9
    if (trailingZeroes(n) == K) {
10
        res++;
11
    }
12
}
13
return res;

对于这种具有单调性的函数，用 for 循环遍历，可以用二分查找进行降维打击。
搜索有多少个 n 满足 trailingZeroes(n) == K，其实就是在问，满足条件的 n 最小是多少，最大是多少，最大值和最小值一减，就可以算出来有多少个 n 满足条件，这就是二分查找中搜索左侧边界和搜索右侧边界。

::: tip 寻找上界和下界

因为二分查找需要给一个搜索区间，也就是上界和下界，上述伪码中 n 的下界显然是 0，但上界是 +inf，这个正无穷应该如何表示出来呢？

首先，数学上的正无穷肯定是无法编程表示出来的，我们一般的方法是用一个非常大的值，大到这个值一定不会被取到。比如说 int 类型的最大值 INT_MAX（2^31 - 1），还不够的话就 long 类型的最大值 LONG_MAX（2^63 - 1）。
需要多大才能一定不会被取到呢？这就需要认真读题，看看题目给的数据范围有多大。
这道题目实际上给了限制，K 是在 [0, 10^9] 区间内的整数，也就是说，trailingZeroes(n) 的结果最多可以达到 10^9。然后我们可以反推，当 trailingZeroes(n) 结果为 10^9 时，n 为多少？这个不需要你精确计算出来，你只要找到一个数 hi，使得 trailingZeroes(hi) 比 10^9 大，就可以把 hi 当做正无穷，作为搜索区间的上界。
trailingZeroes 函数是单调函数，那可以先算一下 trailingZeroes(INT_MAX) 的结果，比 10^9 小一些，那再用 LONG_MAX 算一下，远超 10^9 了，所以 LONG_MAX 可以作为搜索的上界。

:::

在区间 [0, LONG_MAX] 中寻找满足 trailingZeroes(n) == K 的左侧边界和右侧边界。

1
/* 主函数 */
2
public int preimageSizeFZF(int K) {
3
    // 左边界和右边界之差 + 1 就是答案
4
    return (int) (right_bound(K) - left_bound(K) + 1);
5
}
6

7
/* 搜索 trailingZeroes(n) == K 的左侧边界 */
8
public long left_bound(int target) {
9
    long lo = 0, hi = Long.MAX_VALUE;
10
    while (lo < hi) {
11
        long mid = lo + (hi - lo) / 2;
12
        if (trailingZeroes(mid) < target) {
13
            lo = mid + 1;
14
        } else if (trailingZeroes(mid) > target) {
15
            hi = mid;
33 collapsed lines
16
        } else {
17
            hi = mid;
18
        }
19
    }
20
    return lo;
21
}
22

23
/* 搜索 trailingZeroes(n) == K 的右侧边界 */
24
public long right_bound(int target) {
25
    long lo = 0, hi = Long.MAX_VALUE;
26
    while (lo < hi) {
27
        long mid = lo + (hi - lo) / 2;
28
        if (trailingZeroes(mid) < target) {
29
            lo = mid + 1;
30
        } else if (trailingZeroes(mid) > target) {
31
            hi = mid;
32
        } else {
33
            lo = mid + 1;
34
        }
35
    }
36
    return lo - 1;
37
}
38

39
// 全都改成long类型，避免整型溢出
40
public long trailingZeroes(long n) {
41
    long result = 0;
42
    long d = 5;
43
    while (d <= n) {
44
        result += n / d;
45
        d *= 5;
46
    }
47
    return result;
48
}

时间复杂度主要是二分搜索，从数值上来说 LONG_MAX 是 2^63 - 1，虽然大得离谱，但是二分搜索是对数级的复杂度，log(LONG_MAX) 是一个常数；
每次二分的时候都会调用一次 trailingZeroes 函数，复杂度 O(logK)；
所以总体的时间复杂度就是 O(logK)。

::: tip 规律和优化

这个题的答案其实不是0就是5，所以其实只需要判断阶乘结果末尾恰好有 K 个 0的值是否存在即可，如果存在，那么我们直接return 5；如果不存在，则直接return 0即可。
此优化效率提升明显。

:::

1
public int preimageSizeFZF(int K) {
2
    long lo = 0, hi = Long.MAX_VALUE;
3
    while (lo < hi) {
4
        long mid = lo + (hi - lo) / 2;
5
        if (trailingZeroes(mid) < K) {
6
            lo = mid + 1;
7
        } else if (trailingZeroes(mid) > K) {
8
            hi = mid;
9
        } else {
10
          // 找到之后直接返回结果5
11
            return 5;
12
        }
13
    }
14
    return 0;
15
}
11 collapsed lines
16

17
// 全都改成long类型，避免整型溢出
18
public long trailingZeroes(long n) {
19
    long result = 0;
20
    long d = 5;
21
    while (d <= n) {
22
        result += n / d;
23
        d *= 5;
24
    }
25
    return result;
26
}

高效寻找素数

高效进行模幂运算

LeetCode相关题目：超级次方

要求你的算法返回幂运算 a^b 的计算结果与 1337 取模（mod，也就是余数）后的结果，这个 b 是一个非常大的正整数且会以数组形式给出。
- 一是如何处理用数组表示的指数。现在 b 是一个数组，也就是说 b 可以非常大，没办法直接转成整型，否则可能溢出。
- 二是如何得到求模之后的结果。先把幂运算结果算出来，然后做 % 1337 ，但指数运算的真实结果肯定会大得吓人，也就是说，算出来真实结果也没办法表示，早都溢出报错了。
- 三是如何高效进行幂运算。

如何处理数组指数

首先明确问题：现在 b 是一个数组，不能表示成整型，而且数组的特点是随机访问，删除最后一个元素比较高效。
- 以 b = [1,5,6,4] 来举例，结合指数运算的法则，我们可以发现这样的一个规律：
问题规模缩小，这是递归的标志。

先不考虑取模的情况：

1
// 手动实现pow(a,b)-不使用递归
2
public int myPow(int a, int b) {
3
    if (b < 0) return -1;//非法情况
4
    if (b == 0) return 1;//不能丢掉，否则会遗漏b=0的情况【仔细分析，由于res的值为1，实际上可以丢掉】
5
    int res = 1;
6
    for (int i = 1; i <= b; i++) {
7
        res *= a;
8
    }
9
    return res;
10
}
11
// 手动实现pow(a,b)-使用递归
12
public int myPow(int a, int b) {
13
    if (b < 0) return -1;//非法情况
14
    if (b == 0) return 1;//能丢掉，实际上走不到这
15
    if (b == 1) return a;
15 collapsed lines
16
    return a * myPow(a, b - 1);
17
}
18

19
// 递归
20
public int superPow(int a, int[] b) {
21
    // 递归终止条件
22
    if (b.length == 0) return 1;
23
    // 将原问题化简，缩小规模递归求解
24
    // 计算第一部分
25
    int part1 = myPow(a, b[b.length - 1]);
26
    // 计算第二部分
27
    int part2 = myPow(superPow(a, Arrays.copyOf(b, b.length - 1)), 10);
28
    // 合并结果
29
    return part1 * part2;
30
}

如何处理mod运算

首先明确问题：由于计算机的编码方式，形如 (a * b) % base 这样的运算，乘法的结果可能导致溢出，我们希望找到一种技巧，能够化简这种表达式，避免溢出同时得到结果。
- 比如在二分查找中，我们求中点索引时用 (l+r)/2 转化成 l+(r-l)/2，避免溢出的同时得到正确的结果。
快速进行mod运算公式：(a * b) % k = [(a % k)(b % k)] % k
- 对乘法的结果求模，等价于先对每个因子都求模，然后对因子相乘的结果再求模。

完整代码：

1
public int base = 1337;
2

3
// 手动实现pow(a,b)
4
// 函数返回的是pow(a,b)取模之后的结果
5
public int myPow(int a, int b) {
6
  // 1*a*a*a*a...
7
    if (b < 0) return -1;//非法情况
8
    if (b == 0) return 1;//不能丢掉，否则会遗漏b=0的情况【仔细分析，由于res的值为1，实际上可以丢掉】
9
    int res = 1;
10
    a %= base;
11
    for (int i = 1; i <= b; i++) {
12
        res *= a;
13
        res %= base;
14
    }
15
    return res;
15 collapsed lines
16
}
17

18

19
// 递归
20
public int superPow(int a, int[] b) {
21
    // 递归终止条件
22
    if (b.length == 0) return 1;
23
    // 将原问题化简，缩小规模递归求解
24
    // 计算第一部分
25
    int part1 = myPow(a, b[b.length - 1]);
26
    // 计算第二部分
27
    int part2 = myPow(superPow(a, Arrays.copyOf(b, b.length - 1)), 10);
28
    // 合并结果
29
    return (part1 * part2) % base;
30
}

myPow函数先对因子 a 求模，然后每次都对乘法结果 res 求模，这样可以保证 res *= a 这句代码执行时两个因子都是小于 base 的，也就一定不会造成溢出，同时结果也是正确的。

myPow函数也可以通过递归方式进行优化，完整代码如下（推荐使用高级的快速幂算法，时间复杂度可以达到O(logN)对数级别）：

1
// 手动实现pow(a,b)
2
// 函数返回的是pow(a,b)取模之后的结果
3
public int myPow(int a, int b) {
4
    /**
5
     * 以a^4为例，则b=4，该函数返回的是a^4取模之后的结果
6
     * 即：(a^4)%base
7
     * (a*a^3)%base
8
     * (a%base)((a^3)%base)%base
9
     * 其中：(a^3)%base是(a^4)%base规模缩小的问题
10
     * 所以可以使用递归进行求解
11
     */
12
    if (b < 0) return -1;//非法情况
13
    if (b == 0) return 1;//能丢掉，实际上走不到这
14
    if (b == 1) return a % base;
15
    return ((a % base) * (myPow(a, b - 1))) % base;
2 collapsed lines
16
}
17
// 时间复杂度为O(N)

如何高效求幂（快速幂）

快速幂（快速的进行幂运算）是一种简单而有效的小算法，它能够以O(log⁡N)的时间复杂度进行幂运算，快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。
举个例子：7的10次方，怎样算比较快？
- 最朴素的想法：7*7=49、49*7=343，依次一步一步算，共进行了9次乘法。
- 先算7的5次方，即7*7*7*7*7，再算它的平方，共进行了5次乘法。
- 先算7*7得49，则7的5次方为49*49*7，再算它的平方，共进行了4次乘法。
- 模仿这样的过程，我们得到一个在 O(log⁡N) 时间内计算出幂的算法，也就是快速幂。
递归快速幂【 ==重点掌握== 】

1
// 递归快速幂
2
public int recursionPow(int a, int b) {
3
    if (b < 0) return -1;// 非法情况
4
    if (b == 0) {// 0
5
        return 1;// 相当于是递归的结束条件
6
    } else if (b % 2 == 1) {// 奇数
7
        return recursionPow(a, b - 1) * a;
8
    } else {// 偶数
9
        // tmp变量是必要的
10
        // 如果写成recursionPow(a, b / 2)*recursionPow(a, b / 2)
11
        // 则计算机会计算两次，那么算法退化成O(N)的时间复杂度
12
        int tmp = recursionPow(a, b / 2);
13
        return tmp * tmp;
14
    }
15
}

::: tip 注意

在实际问题中，题目常常会要求对一个大数取模，这是因为幂运算的计算结果可能会非常巨大。
快速幂也应当进行取模，此时应当注意：三种情况都需要考虑取模，如果取模的base较大，还应当使用long类型进行定义。

1
// 递归快速幂
2
// 返回的是取模之后的结果
3
public int recursionPow(int a, int b) {
4
    if (b < 0) return -1;// 非法情况
5
    if (b == 0) {// 0
6
        return 1;// 相当于是递归的结束条件
7
    } else if (b % 2 == 1) {// 奇数
8
        return (recursionPow(a, b - 1) * (a % base)) % base;
9
    } else {// 偶数
10
        // tmp变量是必要的
11
        // 如果写成recursionPow(a, b / 2)*recursionPow(a, b / 2)
12
        // 则计算机会计算两次，那么算法退化成O(N)的时间复杂度
13
        int tmp = recursionPow(a, b / 2);
14
        return (tmp * tmp) % base;
15
    }
1 collapsed line
16
}

递归虽然简洁且运算速度快，但会产生额外的空间开销，可以把递归改写为循环，来避免对栈空间的大量占用，也就是非递归快速幂。
- 时间复杂度：O(log⁡N)，即为递归的层数。
- 空间复杂度：O(log⁡N)，即为递归的层数。这是由于递归的函数调用会使用栈空间。

:::

非递归快速幂【 ==重点掌握== 】

::: tip 引入

换一个角度来引入非递归的快速幂，还是7的10次方，但这次，把10写成二进制的形式，也就是 0b1010 。
要计算 7^0b1010^ ，可以怎么做？
- 很自然地想到可以把它拆分为 7^0b1000^*7^0b10^ 。
- 实际上，对于任意的整数，都可以把它拆成若干个 7^0b100…^的形式相乘。
- 而这些7^0b100…^，恰好就是 7^1^ 、7^2^、7^4^等等，我们只需不断把底数平方就可以算出它们。

:::

不考虑取模的情况：

1
// 非递归快速幂
2
public int unRecursionPow(int a, int n) {
3
    if (n < 0) return -1;//非法情况
4
    if (n == 0) return 1;//不能丢掉，否则会遗漏b=0的情况【仔细分析，由于res的值为1，实际上可以丢掉】
5
    int ans = 1;
6
    while (n != 0) {
7
        if ((n & 1) == 1)        //如果n的当前末位为1
8
            ans *= a;  //ans乘上当前的a
9
        a *= a;        //a自乘
10
        n >>= 1;       //n往右移一位
11
    }
12
    return ans;
13
}

考虑取模的情况：

1
// 非递归快速幂
2
// 返回的是取模之后的结果
3
public int unRecursionPow(int a, int n) {
4
    if (n < 0) return -1;//非法情况
5
    if (n == 0) return 1;//不能丢掉，否则会遗漏b=0的情况【仔细分析，由于res的值为1，实际上可以丢掉】
6
    int ans = 1;
7
    a %= base;
8
    while (n != 0) {
9
        if ((n & 1) == 1) {//如果n的当前末位为1
10
            ans *= a;  //ans乘上当前的a
11
            ans %= base;
12
        }
13
        // 潜在的整型溢出
14
        a *= a;        //a自乘
15
        a %= base;
4 collapsed lines
16
        n >>= 1;       //n往右移一位
17
    }
18
    return ans;
19
}

复杂度分析
- 时间复杂度：O(log⁡N)，即为对 n 进行二进制拆分的时间复杂度。
- 空间复杂度：O(1)。
总结
- 空间复杂度要求的不是太高的话，建议还是使用递归快速幂。

参考：

https://zhuanlan.zhihu.com/p/95902286

https://leetcode.cn/problems/powx-n/solutions/238559/powx-n-by-leetcode-solution/

LeetCode相关题目：

Pow(x, n)：考虑指数为负数的情况。

1
// 主函数
2
public double myPow(double x, int n) {
3
    long N = n;
4
    if (N == 0) return 1;
5
    return N < 0 ? 1 / unRPow(x, -N) : unRPow(x, N);
6
}
7

8

9
// 使用非递归快速幂
10
public double unRPow(double a, long b) {
11
    if (b < 0) return -1;// 非法情况
12
    if (b == 0) return 1;
13
    double res = 1.0;
14
    while (b != 0) {
15
        if ((b & 1) == 1) {//末位是1
7 collapsed lines
16
            res *= a;
17
        }
18
        a *= a;
19
        b >>= 1;
20
    }
21
    return res;
22
}

::: warning 注意

Java中int类型的范围是[-2147483648,2147483647]，即最大值是2^31^-1，最小值是-2^31^。
所以在测试用例x=1，n=-2147483648运行时，使用下面的代码会出现问题：

1
// 主函数
2
public double myPow(double x, int n) {
3
    if (n == 0) return 1;
4
    return n < 0 ? 1 / unRPow(x, -n) : unRPow(x, n);
5
  // 当n=-2147483648时候，取相反数应该是2147483648，但int类型最大值才是2147483647，所以取相反数是不变的，还是原值-2147483648。
6
  // 解决办法是将其转为long类型
7
}

:::

数值的整数次方

同时寻找缺失和重复的元素

LeetCode相关题目：错误的集合

给一个长度为 N 的数组 nums，其中本来装着 [1..N] 这 N 个元素，无序。但是现在出现了一些错误，nums 中的一个元素出现了重复，也就同时导致了另一个元素的缺失。
正常思路：首先记录每一个元素出现的次数，找到重复的元素，然后在找缺失的元素。

1
import java.util.*;
2
class Solution {
3
    public int[] findErrorNums(int[] nums) {
4
        int[] res = new int[2];
5
        // 存储每一个元素出现的此次数
6
        Hashtable<Integer, Integer> hashtable = new Hashtable<>();
7
        for (int num : nums) {
8
            if (!hashtable.containsKey(num)) {
9
                hashtable.put(num, 1);
10
            } else {
11
                hashtable.put(num, hashtable.get(num) + 1);
12
            }
13
        }
14
        Set<Integer> set = hashtable.keySet();
15
        for (Integer integer : set) {
13 collapsed lines
16
            if (hashtable.get(integer) != 1)
17
                res[0] = integer;
18
        }
19
        for (int i = 1; i <= nums.length; i++) {
20
            if (set.contains(i))
21
                continue;
22
            else
23
                res[1] = i;
24
        }
25
        return res;
26
    }
27

28
}

::: tip 复杂度分析

时间复杂度：O(N)
空间复杂度：O(N)
O(N) 的时间复杂度遍历数组是无法避免的，所以可以想想办法如何降低空间复杂度，是否可以在 O(1) 的空间复杂度之下找到重复和缺失的元素？

:::

思路分析（优化空间复杂度到O(1)）
- 每个元素和数组索引有一定的对应关系。
- 暂且将 nums 中的元素变为 [0..N-1]，这样每个元素就和一个数组索引完全对应了，这样方便理解一些。
- 如果说 nums 中不存在重复元素和缺失元素，那么每个元素就和唯一一个索引值对应。
- 有一个元素重复了，同时导致一个元素缺失了，会导致有两个元素对应到了同一个索引，而且会有一个索引没有元素对应过去。
- 找到这个重复对应的索引，就找到了那个重复的元素；找到那个没有元素对应的索引，就找到了那个缺失的元素。

::: tip 思路分析

用数组元素的绝对值做下标，然后让这个下标对应的元素置为负的，相当于把它标记为已访问过的元素，如果某个元素做下标时对应的元素值为负，则这个数是重复值。再次遍历数组寻找唯一没有置为负的那个元素，它的下标就是缺失的元素值。
假设元素是 [0..N-1]，但题目要求是 [1..N]，所以需要修改部分的值才能得到正确结果。
时间复杂度：O(N)
空间复杂度：O(1)

:::

原理图如下：
完整代码如下：

1
public int[] findErrorNums(int[] nums) {
2
    int[] res = new int[2];
3
    // 寻找重复的元素
4
    int length = nums.length;
5
    for (int i = 0; i < length; i++) {
6
        int index = Math.abs(nums[i]) - 1;
7
        if (nums[index] >= 0) {
8
            nums[index] *= -1;
9
        } else {
10
            res[0] = index+1;
11
        }
12
    }
13
    // 寻找缺失的元素
14
    for (int i = 0; i < length; i++) {
15
        if (nums[i] > 0) {
6 collapsed lines
16
            res[1] = i + 1;
17
            break;
18
        }
19
    }
20
    return res;
21
}