1.数字的位操作

1-1.回文

1-1-1.回文数：9

法一：常规解法，但是需要考虑整数溢出问题

法二：反转一半数字

方法与法一类似，但是这样可以避免考虑溢出问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isPalindrome(int x) {
        int res = 0;
        if (x < 0 || (x % 10 == 0 && x)) {
            //因为最终return部分加入了x==res/10的情况，所以需要(x % 10 == 0 && x)
            return false;
        }
        while (x > res) {
            int digit = x % 10;
            x /= 10;
            res = res * 10 + digit;
        }
        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == res || x == res / 10;
    }
};

1-1-2.寻找最近的回文数：564（困难）

模拟：

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
35
36
37
using ULL = unsigned long long;

class Solution {
public:
    vector<ULL> getCandidates(const string& n) {
        int len = n.length();
        // 候选数组，符合这4中情况的数字
        vector<ULL> candidates = {
            (ULL)pow(10, len - 1) - 1,
            (ULL)pow(10, len) + 1,
        };
        ULL selfPrefix = stoull(n.substr(0, (len + 1) / 2));
        for (int i : {selfPrefix - 1, selfPrefix, selfPrefix + 1}) {
            // i只在这三个数之间遍历
            // prefix就是原数字的前半部分
            string prefix = to_string(i);
            string candidate = prefix + string(prefix.rbegin() + (len & 1), prefix.rend());
            candidates.push_back(stoull(candidate));
        }
        return candidates;
    }

    string nearestPalindromic(string n) {
        ULL selfNumber = stoull(n), ans = -1;
        const vector<ULL>& candidates = getCandidates(n);
        for (auto& candidate : candidates) {
            if (candidate != selfNumber) {
                if (ans == -1 ||
                    llabs(candidate - selfNumber) < llabs(ans - selfNumber) ||
                    llabs(candidate - selfNumber) == llabs(ans - selfNumber) && candidate < ans) {
                    ans = candidate;
                }
            }
        }
        return to_string(ans);
    }
};

注：

1
2
3
4
5
6
7
8
9
10
11
// 第一种：typedef
typedef int myInt1;
typedef std::vector<int> IntVector1;

// 第二种：using 别名声明
using myInt2 = int;
using IntVector2 = std::vector<int>;

// 第三种：using 模板别名
template <typename T>
using myIntVector = std::vector<T>;

  1. using ULL = unsigned long long;：关于别名有三种写法，typedef、using别名声明、using模板声明。

    类型别名（type alias）、#define 宏和 const 常量的区别：

  2. string(prefix.rbegin() + (len & 1), prefix.rend());：
    +len&1是指，如果长度len为单数（len&1==1，涉及位运算，奇数的二进制末位为1），则从下标1开始添加，否则从0开始。string(startIterater,endIterater);

  3. stoull()、llabs():不在赘述，注意并没有ullabs()的用法。还有一点值得注意，应该使用unsigned long long而非long long,是因为如果输入为：”999999999999999999”,对于13行这句 candidates.push_back(stol(candidate)); stol 会产生溢出，原因是candidate超过 long long，是两个大数相加接近 2^65了。

1-2.x的幂

1-2-1.2的幂：231

法一：位运算

1
2
3
4
5
6
7
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
};

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & -n) == n;
    }
};

法二：判断是否为最大的2的幂的约数（取巧，了解）

1
2
3
4
5
6
7
8
9
class Solution {
private:
    static constexpr int BIG = 1 << 30;

public:
    bool isPowerOfTwo(int n) {
        return n > 0 && BIG % n == 0;
    }
};

注:1<<30是指二进制数1左移30位变成$2^{31}$。

关于常量

constexpr用于声明常量表达式,const用于声明常量。1<<30是常量表达式，因为它在编译时就能得到计算结果。并且这里必须加上static使得BIG被声明为静态常量，让所有Solution的实例都共享同一份BIG。

Q:如何判断一个常量表达式是不是运行时才能计算出结果？

A:考虑以下几点：

  1. 非编译时计算：如果一个常量表达式可以在编译时就计算出结果，那么它就不是运行时才能计算出的。编译器会在编译阶段对这些表达式进行求值。

  2. 依赖运行时信息：如果一个常量表达式依赖于在运行时才能确定的信息，比如用户输入、动态分配的内存地址等，那么它就是运行时才能计算出的。

  3. 函数调用：如果一个常量表达式中包含函数调用，特别是虚函数调用或者依赖于动态多态性的调用，那么它通常是在运行时才能计算出结果的。

  4. 条件表达式：如果一个常量表达式包含条件运算符（如? :），并且条件是在运行时才能确定的，那么它也是在运行时才能计算出结果的。

比如1<<x,pow(3,19),a>15?true:false都是在运行时才能计算出结果。第一个对应第2点，x在运行时才能确定；第二个对应第3点，包含了pow()函数调用;第三个对应第4点，包含了条件运算符的同时包含了运行时才能确定的条件a>15.

而诸如20>15,4+3,110<<24这类，则是编译时就能计算出结果。

constexpr和const的详细区别：constexpr和const

总的来说，const 是一个用于指定常量的关键字，而 constexpr 则是一个用于指定常量表达式的关键字。使用 constexpr 可以让编译器进行优化和检查，提高代码的可读性和运行效率。

1-2-2.4的幂：342

法一：位运算

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
    }
};

法二：取模

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
    }
};

尝试写出判断一个数是否为8的幂次方。

1-2-3.3的幂：326

法一：判断是否为最大的3的幂的约数（取巧，了解）

1
2
3
4
5
6
7
8
9
class Solution {
private:
    static const int BIG = 1162261467;

public:
    bool isPowerOfThree(int n) { 
        return n > 0 && BIG % n == 0; 
    }
};

法二：试除法（时间复杂度较高）

不断除以3直到n=1:

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool isPowerOfThree(int n) {
        while (n && n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
};

1-3.颠倒二进制位：190

uint32_t是无符号32位整数类型，范围在$0$~$2^{32}-1$，定义在头文件<cstdint>中。

法一：逐位颠倒

每次把 res 左移，把 n 的二进制末尾数字，拼接到结果 res 的末尾。然后把 n 右移。

以8位二进制为例：

inn&1res
—-110010011—-
00110010001,0000000
100110010010,000000
2000110011100,00000
30000110001001,0000
400000110010010,000
5000000111100100,00
60000000111001001,0
700000000—-10010011
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; n > 0 && i < 32; i++) {
            res |= (n & 1) << (31 - i);
            //如n&1==1时,n为奇数.同时也能判断出n末位为1,所以n&1也代表末位
            //末位右移31-i位，后面补上0并与res进行位或操作
            n >>= 1; // n左移1位，相当于去除之前的末位
        }
        return res;
    }
};

或者：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; n > 0 && i < 32; i++) {//去掉n>0的条件
            res = (res << 1) | (n & 1);
            n >>= 1;
        }
        return res;
    }
};

法二：位运算分治(最优)

类似归并排序，其思想是分而治之，把数字分为两半，然后交换这两半的顺序；然后把前后两个半段都再分成两半，交换内部顺序……直至最后交换顺序的时候，交换的数字只有 1 位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
private:
    const uint32_t M1 = 0x55555555; // 01010101010101010101010101010101
    const uint32_t M2 = 0x33333333; // 00110011001100110011001100110011
    const uint32_t M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
    const uint32_t M8 = 0x00ff00ff; // 00000000111111110000000011111111

public:
    uint32_t reverseBits(uint32_t n) {
        n = n >> 1 & M1 | (n & M1) << 1;
        n = n >> 2 & M2 | (n & M2) << 2;
        n = n >> 4 & M4 | (n & M4) << 4;
        n = n >> 8 & M8 | (n & M8) << 8;
        return n >> 16 | n << 16;
    }
};

关于分治算法：分治算法

1-3-1.位1的个数：191

法一：遍历每个二进制位

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int num = 0;
        for (int i = 0; i < 32; i++) {
            if (n & (1 << i)) { // 1左移i位
                num++;
            }
        }
        return num;
    }
};

法二：优化

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int num = 0;
        while (n) {
            n &= n - 1;
            num++;
        }
        return num;
    }
};

n&(n-1)可以用来判断有几个1，也可以通过其值是否为0来判断一个数是不是2的幂(详见1-2-2)。也有内置函数__builtin_popcount(n)，时间复杂度$O(1)$。

1-3-2.数字的补数：476(低位取反)

法一:常规位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int findComplement(int num) {
        uint t = (uint)1 << 31;
        while ((t & num) == 0) {
            num |= t;
            t >>= 1; // t右移一位
            //相当于对num从高位到地位逐个遍历,把num第一个1前面的0都改为1
            // 这样num取反才是正确的
        }
        return ~num; // 取反
    }
};

t:1000…000->0100…000->…->0000…0001(如果一直循环)

num(5):000…0101->100…0101->…->111…1101->(取反)000…0010(32位二进制数)->2

注意，==的优先级比&高，所以t&num必须带上括号。

(uint)1<<31也可以写为1u<<31。uint相当于unsigned int.

或者：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int findComplement(int num) {
        uint mask = 1;
        while (mask < num) {
            mask <<= 1;
            mask |= 1;//mask比较特殊，这里mask++;也可以
        }
        return mask ^ num;
    }
};

由于mask只含有1个“1”,因此mask<num也就是mask的“1”相比num中的最高位1，总是在同位或者更低位，即还在遍历num中。000…1000<000…1011

法二：位运算分治

时间复杂度为$O(log log num)$

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int findComplement(int num) {
        int t = num;
        t |= t >> 1;
        t |= t >> 2;
        t |= t >> 4;
        t |= t >> 8;
        t |= t >> 16;
        return ~num & t;
    }
};

注：分治目的是把t各低位为零数取反，最终变为与num对应低位全1的32位二进制数。

t:0000…0101->0000…0111(奇位且低位的0变为1)->…->0000…0111

~num=1111…1010,则~num&t=num^t=0000…0010

在位运算中，^ 表示按位异或运算，它的结果是对应位不同则为1，相同则为0。而 & 表示按位与运算，它的结果是对应位都为1时为1，否则为0。

1-3-3.汉明距离：461

汉明距离指两个数字对应的二进制位不同的位置的数目。该题其实是1-3-1和1-3-2的结合

法一：(最优)内置函数，时间复杂度O(1)。

1
2
3
4
5
6
class Solution {
public:
    int hammingDistance(int x, int y) {
        return __builtin_popcount(x ^ y);
    }
};

法二：Brian Kernighan算法(基础位运算结合)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hammingDistance(int x, int y) {
        int t = x ^ y;//按位异或,不同的地方全变为1
        int count = 0;
        while (t) {
            t &= t - 1;//用来判断有几个1
            count++;
        }
        return count;
    }
};

或者:移位实现位计数

只是换一种方式统计1的个数

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hammingDistance(int x, int y) {
        int t = x ^ y; // 按位异或,不同的地方全变为1
        int count = 0;
        while (t) {
            count += t & 1;//t末位为1,则t&1=1,count加1
            t >>= 1;//相当于去除末位,首位补0
        }
        return count;
    }
};

法三：位运算分治

两两切分统计：掩码对数值进行切分，连续的0用于进位，连续的1是运算位。五次运算分别类似于是二进制数加法，四进制数加法，十六进制数加法和三十二进制数加法。如01111011->01 10 01 10(1212)->0011 0011(33)->00000110(6)，个数即为6。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
    const uint32_t M1 = 0x55555555;
    const uint32_t M2 = 0x33333333;
    const uint32_t M4 = 0x0f0f0f0f;
    const uint32_t M8 = 0x00ff00ff;
    const uint32_t M16 = 0x0000ffff;

public:
    int hammingDistance(int x, int y) {
        int n = x ^ y;
        n = ((n >> 1) & M1) + (n & M1);
        n = ((n >> 2) & M2) + (n & M2);
        n = ((n >> 4) & M4) + (n & M4);
        n = ((n >> 8) & M8) + (n & M8);
        n = ((n >> 16) & M16) + (n & M16);
        return n;
    }
};

关于运算符优先级

最好是手动加入括号控制运算顺序。总优先级：算术运算>关系运算>逻辑运算。

算术运算（加+ 减- 乘* 除/ 取余%），关系运算（> >= < <= != ==) ，逻辑运算 （与或非）

常见位运算技巧

  1. n & M1:将二进制数n中的奇数位的1保留，丢弃偶数位。如n=00011001…01110101->00010001…01010001。(n>>2)&M2同理。

  2. (n >> 1) & M1 | (n & M1) << 1：交换相邻两个数的位置。(n >> 2) & M2 | (n & M2) << 2则是两个为一组，互相交换各组。如0011->1100

  3. ((n >> 1) & M1) + (n & M1)：将n中的相邻两位相加，如10110101->1211(即01110101).((n >> 2) & M2) + (n & M2)同理，如1211(即01 11 01 01)->32(即0011 0010)

  4. t & 1：判断t是否为奇数,如果为奇数则结果为1。/获取t末位数字。(t>>i) & 1则用来获取第i位的值（从右往左数第i位）。

  5. t & (t-1)：每在循环内执行一次并计数+1，则循环完成就可以统计出二进制数中1的个数。

1-3-4.汉明距离总和:477

最优解：逐位统计

先看所有数字的第一位，然后再第二位…而非先计算出两两之间的汉明距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int ans = 0, size = nums.size();
        for (int i = 0; i < 32; i++) {
            int n = 0;
            for (int num : nums) {
                n += (num >> i) & 1; // n加上num第i位的值(从右往左第i位)
                //第i位的值只可能是0/1，因此n记录下出现过1的次数
            }
            //第i位一共n个1，size-n个0
            ans += n * (size - n);
        }
        return ans;
    }
};

1-3-5.交替位二进制数：693

1
2
3
4
5
6
7
class Solution {
public:
    bool hasAlternatingBits(int n) {
        uint a = n ^ (n >> 1);//long也可以，但是int不行
        return (a & (a + 1)) == 0;
    }
};

a=n^(n>>1):a除去前导的0之外，其它数位全部都是1。因为如果a是低位二进制位交替出现的话，那右移一位就是原来是0的移到了原来是1的位置上；再异或，就全部都是1了。

a&(a+1):二进制位全部都是1的a加上1,得到的二进制数a+1多了最前面一个数位1其它都是0,再与全部是0的a进行&位与运算肯定是0。

1-4.数学思维（*）

1-4-1.可怜的小猪：458

数学分析+base进制：

画解算法:458.可怜的小猪

1
2
3
4
5
6
7
class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int base = minutesToTest / minutesToDie + 1;
        return ceil(log(buckets) / log(base) - 1e-5);//是1e-5即10^(-5)
    }
};

ceil():向上取整函数。

减去1e-5:目的是让log(buckets) / log(base)减去一个即小的值以避免舍入误差，也可以是1e-7等等。因为当buckets=125,minutesToDie=1,minutesToTest=4时，结果应该是3，而不考虑舍入误差，则答案会是4。在这段代码中，log(buckets) / log(base)的结果通常是一个浮点数，但由于浮点数计算的精度限制，可能会出现微小的舍入误差。通过减去 1e-5，可以确保结果向下取整，避免由于舍入误差而导致的计算结果错误。这样做可以更接近正确的整数结果。

1-4-2.各位相加：258

详细思路：力扣（LeetCode)

1
2
3
4
5
6
class Solution {
public:
    int addDigits(int num) { 
        return (num - 1) % 9 + 1; 
    }
};

1-4-3.灯泡开关：319

详细思路：【宫水三叶】经典数论推论题

1
2
3
4
5
6
class Solution {
public:
    int bulbSwitch(int n) { 
        return sqrt(n + 0.5); 
    }
};

答案为$\lfloor \sqrt{n} \rfloor$，其中 $\lfloor \cdot \rfloor$ 表示向下取整。

加上0.5：由于 $\sqrt{n}$涉及到浮点数运算，为了保证不出现精度问题（避免舍入误差），我们可以计算 $\sqrt{n + \dfrac{1}{2}}$​，这样可以保证计算出来的结果向下取整在32位整数范围内一定正确。其实加上一个较小的数也可以，比如1e-5。

综上，对于return浮点数类型且函数返回值类型为int的，往往需要向上或者向下取整。为避免舍入误差，需要引入较小的数，比如1e-5($10^{-5}$)，是加是减根据题目判断。

1-5.进制转换

1-5-1.数字转换为16进制数：405

位运算，关键在于int val = (num >> (4 * i)) & 0xf将二进制数分组以后再一一运算。如果这里是转为8进制数，则每三个数为一组，同理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string toHex(int num) {
        if (num == 0) {
            return "0";
        }
        string ans = "";
        // 32位的二进制数一共8组，每组4个数num>>(4*i)可以将第i组的四个数移到末尾
        for (int i = 7; i >= 0; i--) {
            int val = (num >> (4 * i)) & 0xf;//一个val对应十六进制的一个数字0-9/字母a-f
            if (ans.length() > 0 || val > 0) {
                char digit = val < 10 ? (char)(val + '0') : (char)('a' + val - 10);
                ans.push_back(digit);
            }
        }
        return ans;
    }
};

  • ans.length()>0用于避免出现前置0.

  • 求负整数的补码:将其原码除符号位外的所有位取反（0变1，1变0，符号位为1不变）后加1。

  • 该题还要注意一点，val+'0'只适用于val<10时的情况，因为'a'!='9'+1，它们对应的ASCII码并不是连续的。

1-5-2.Excel表列名称：168

本质为10进制转26进制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string convertToTitle(int columnNumber) {
        string ans = "";
        while (columnNumber > 0) {
            --columnNumber;
            char c = columnNumber % 26 + 'A';//从末位从后往前添加字符
            ans.push_back(c);
            columnNumber /= 26;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

1-6.数字变换/统计 + 数学分析

1-6-1.最大变换：670

最接近右边且最大的数是s[maxIndex]与最接近左边且非最大的数s[index]进行交换。但是如果这样得出的maxIndex<index，那么结果会出现问题。因此需要额外引入index2来记录每一次循环完成后的maxIndex，index2=maxIndex.

贪心：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maximumSwap(int num) {
        string s = to_string(num);
        int n = s.size(), maxIndex = n - 1, index1 = -1, index2 = -1;
        for (int i = n - 1; i >= 0; i--) {
            if (s[maxIndex] < s[i]) {
                maxIndex = i;
            } else if (s[i] < s[maxIndex]) {
                index1 = i;
                index2 = maxIndex;//比如98368,maxIndex=0,需要额外的index2记录
            }
        }
        if (index1 >= 0) {
            swap(s[index1], s[index2]);
        }
        return stoi(s);
    }
};

1-6-2.数字1的个数：233（困难）

解题思路：数字 1 的个数（清晰图解）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int countDigitOne(int n) {
        long digit = 1;
        int high = n / 10, cur = n % 10, low = 0, res = 0;
        while (high != 0 || cur != 0) {
            if (cur == 0) {
                res += high * digit;
            } else if (cur == 1) {
                res += high * digit + low + 1;
            } else {
                res += (high + 1) * digit;
            }
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res;
    }
};

1-6-3.统计各位数字都不同的数字个数：357

使用数字的排列组合$A^{n}_{k}​=\frac{n!}{(n−k)!}$

含有 $d（2 \le d \le 10）$位数的各位数字都不同的数字$x$的个数可以由公式$9 \times A9^{d-1}$计算，第一位只能从1-9中选择，后面的d-1位从剩下的9个数之中选，即$A_9^{d-1}$个。总个数其实就是$res = 10 + 9 \times (A^{1}{9}+A^{2}{9}+…+A^{n-1}{9})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 10;
        }
        int res = 10, CurrentNum = 9;
        for (int i = 0; i < n - 1; i++) {
            CurrentNum *= 9 - i;
            res += CurrentNum;
        }
        return res;
    }
};

2.快速幂

2-1.实现pow(x,n)：50

解题思路：快速幂，清晰图解

关于快速幂：快速幂-Pecco

快速幂本质是分治算法，有以下两种方法：

法一：递归（需要额外栈空间）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    double quilkMul(double x, long long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quilkMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }
    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quilkMul(x, N) : 1.0 / quilkMul(x, -N);
    }
};

法二：迭代（涉及位运算分析）

判断N%2==1也可以写为N&1==1,N/=2可以写为N>>=1,更能体现位运算思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    double quilkMul(double x, long long N) {
        double ans = 1.0;
        // 贡献的初始值为 x
        double x_contribute = x;
        // 在对 N 进行二进制拆分的同时计算答案
        while (N > 0) {
            if (N % 2 == 1) {
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x_contribute;
            }
            // 将贡献不断地平方
            x_contribute *= x_contribute;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            N /= 2;
        }
        return ans;
    }
    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quilkMul(x, N) : 1.0 / quilkMul(x, -N);
    }
};

注意：这里使用了long long N = n;，因为在n=INT_MIN时，-n=-INT_MIN=INT_MIN(INT_MIN=$-2^{31}$,INT_MAX=$2^{31}-1$)，使用long long存储能避免这一麻烦。

2-2.超级次方：372

法一：倒序遍历+快速幂

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
class Solution {
public:
    int pow(int x, int n) {
        // 数字太大，不使用long容易超出范围
        long ans = 1;
        long N = n;
        long x_contribute = x;
        while (N > 0) {
            if (N & 1) {
                // 包括之后的多次对1337取模都是为了避免溢出
                ans = ans * x_contribute % 1337;
            }
            x_contribute = x_contribute * x_contribute % 1337;
            N >>= 1;
        }
        return ans;
    }

    int superPow(int a, vector<int>& b) {
        if (a == 1) {
            return 1;
        }
        long res = 1;
        for (int i = b.size() - 1; i >= 0; i--) {
            res = res * pow(a, b[i]) % 1337;
            a = pow(a, 10);
        }
        return res;
    }
};

值得注意的是，形如x_contribute = x_contribute * x_contribute % 1337;不能写成x_contribute *= x_contribute % 1337;因为一个最终是平方对1337取的模，另一个是自身对1337取模以后的值再乘以自身，这样会导致溢出（注意运算顺序）。

法二：正序遍历+秦九韶算法

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
class Solution {
public:
    int pow(int x, int n) { // 数字太大，不使用long容易超出范围
        long ans = 1;
        long N = n;
        long x_contribute = x;
        while (N > 0) {
            if (N & 1) {
                // 包括之后的多次对1337取模都是为了避免溢出
                ans = ans * x_contribute % 1337;
            }
            x_contribute = x_contribute * x_contribute % 1337;
            N >>= 1;
        }
        return ans;
    }
    int superPow(int a, vector<int>& b) {
        if (a == 1) {
            return 1;
        }
        long res = 1;
        for (int num : b) { // 区别仅在于for循环
            res = pow(res, 10) * pow(a, num) % 1337;
        }
        return res;
    }
};

2-3.两数相除：29

类似快速幂通过乘法实现幂，这里使用“快速乘”算法通过加法实现乘法。

快速乘+类二分查找

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    int divide(int dividend, int divisor) {
        // 三种特殊情况
        //  考虑被除数为最小值的情况
        if (dividend == INT_MIN) {
            if (divisor == 1) {
                return INT_MIN;
            }
            if (divisor == -1) {
                return INT_MAX;
            }
        }
        // 考虑除数为最小值的情况
        if (divisor == INT_MIN) {
            return dividend == INT_MIN ? 1 : 0;
        }
        // 考虑被除数为 0 的情况
        if (dividend == 0) {
            return 0;
        }

        // 一般情况，使用类二分查找
        //  将所有的正数取相反数，这样就只需要考虑一种情况
        bool rev = false;
        if (dividend > 0) {
            dividend = -dividend;
            rev = !rev;
        }
        if (divisor > 0) {
            divisor = -divisor;
            rev = !rev;
        }

        vector<int> candidates = {divisor};
        // 注意溢出
        while (candidates.back() >= dividend - candidates.back()) {
            candidates.push_back(candidates.back() + candidates.back());
        }
        int ans = 0;
        for (int i = candidates.size() - 1; i >= 0; --i) {
            if (candidates[i] >= dividend) {
                ans += (1 << i);
                dividend -= candidates[i];
            }
        }

        return rev ? -ans : ans;
    }
};

将所有正数取相反数：确保都是负数，从而避免溢出，因为都转为正数会导致INT_MIN这个边界难以处理。

快速乘代码：

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
class Solution {
public:
    // 快速乘
    auto quickAdd = [](int y, int z, int x) {
        // x 和 y 是负数，z 是正数
        // 需要判断 z * y >= x 是否成立
        int result = 0, add = y;
        while (z) {
            if (z & 1) {
                // 需要保证 result + add >= x
                if (result < x - add) {
                    return false;
                }
                result += add;
            }
            if (z != 1) {
                // 需要保证 add + add >= x
                if (add < x - add) {
                    return false;
                }
                add += add;
            }
            // 不能使用除法
            z >>= 1;
        }
        return true;
    };
}

y对应除数divisor，z对应中点mid，x对应被除数dividend.