概论

平常我们会遇见很多数学问题，比如多项式优化位卷积形式，或者用位运算、快速幂和进制转换来优化一部分题，例如一部分数论题和图论题就是让我们将数学定理具象化。
今天我们来看一下这些简单的数学问题,你会看到位运算、快速幂、进位制和高精度计算这些知识点，然后开始数论的学习。

位运算

文字太多了 看图吧

基本概念

这个可能是我们见得最多的简单知识点了，就是基于整数二进制表示进行的运算，常见有6种 与（ & ）、或（ | ）、异或（ ^ ）、取反（ ~ ）、左移（ << ）和右移（ >> ）

取反~ -------单目运算符

将二进制表示的数字中的0变为1, 1变为0
但是需要注意的是c++中对int型进行取反操作时，将前面的前导0也进行了取反(int型变量为32bit)。

比如1的二进制表示是

00000000 00000000 00000000 00000001

~(00000000 00000000 00000000 00000001) = 11111111 11111111 11111111 11111110

负数的二进制表示

负数的二进制表示 = 其绝对值的补码

• 原码：一个整数，按照绝对值大小转换成的二进制数，称为原码。

比如-3的原码是：

00000000 00000000 00000000 00000011

• 反码：将二进制数按位取反，所得的新二进制数称为原二进制数的反码。

-3的反码是：

11111111 11111111 11111111 11111100

• 补码：反码加1称为补码。也就是说，要得到一个数的补码，先得到反码，然后将反码加上1，所得数称为补码。

那么-3的补码，也就是-3的二进制表示为：

11111111 11111111 11111111 11111100 + 1
= 11111111 11111111 11111111 11111101

同理，整数-1在计算机中的二进制表示为：

1、先取1的原码：00000000 00000000 00000000 00000001

2、得反码： 11111111 11111111 11111111 11111110

3、得补码： 11111111 11111111 11111111 11111111

结论

只有~(-1) = 0

其他整型数取反都是非0的

与、或、异或

与（ & ）或（ | ）和异或（^）这三者都是两数间的运算，因此在这里一起讲解。它们都是将两个整数作为二进制数，对二进制表示中的每一位逐一运算。

下面我们已5（101） 6（110）举例

左移和右移

• 左移运算符是用来将一个数的各二进制位左移若干位，移动的位数由右操作数指定（右操作数必须是非负值），其右边空出的位用0填补，高位左移溢出则舍弃该高位。

例如：将a的二进制数左移2位，右边空出的位补0，左边溢出的位舍弃。若a=15,即00001111（2），左移2位得00111100（2）。左移1位相当于该数乘以2，左移2位相当于该数乘以2*2＝4,15＜＜2=60，即乘了４。但此结论只适用于该数左移时被溢出舍弃的高位中不包含1的情况。

假设以一个字节（８位）存一个整数，若ａ为无符号整型变量，则ａ＝64时，左移一位时溢出的是0，而左移2位时，溢出的高位中包含1。

• 右移运算符是用来将一个数的各二进制位右移若干位，移动的位数由右操作数指定（右操作数必须是非负值），移到右端的低位被舍弃，对于无符号数，高位补0。对于有符号数，某些机器将对左边空出的部分用符号位填补（即“算术移位”），而另一些机器则对左边空出的部分用0填补（即“逻辑移位”）。

注意：对无符号数,右移时左边高位移入0；对于有符号的值,如果原来符号位为0(该数为正),则左边也是移入0。如果符号位原来为1(即负数),则左边移入0还是1,要取决于所用的计算机系统。有的系统移入0,有的系统移入1。移入0的称为“逻辑移位”,即简单移位；移入1的称为“算术移位”。

例： a的值是八进制数113755：
a:1001011111101101 （用二进制形式表示）
a>>1: 0100101111110110 (逻辑右移时)
a>>1: 1100101111110110 (算术右移时)

基本特性

1. 异或特性

恒等律 x^0=x 归零律 x^x=0
交换律 A^B=B^A 结合律 A^(B^C)=(A^B)^C

证明： （字太丑了）

2.异或应用

• 1.快速比较两个数
  一般我们回直接用 a-b==0 或 a==b 来判断，但是这里我们用a^b==0 效率会更加快一点，对问题的证明我们可以用运行时=时间来对比一下或者可以看一下底层源码
  比如：
  java.lang.Integer类的源码:
  // really: r = i - (q * 100); r = i - ((q << 6) + (q << 5) + (q << 2));
  对于这一句话建议你可以试验一下，用数字感受一下。具体证明就不给了，因为这里涉及到这一些位运算指令占的机器周期、寻址时间和逻辑运算与读写有关。

• 2 k位取反
  例如：
  例如：翻转10100001的第6位， 答案：可以将该数与00100000进行按位异或运算;10100001 ^ 00100000 = 10000001
  对于正整数操作模板：

int a,b,k=1<<x;
a= 0xB1; // 10100001
b=a^k;// 翻转第x位

• 3.奇偶校验
  例如：求10100001中1的数量是奇数还是偶数； 答案：1 ^ 0 ^ 1 ^ 0 ^ 0 ^ 0 ^ 0 ^ 1 = 1,结果为1就是奇数个1，结果为0就是偶数个1
• 4.swap（a,b）

a = a ^ b;
b = a ^ b; //a ^ b ^ b = a ^ 0 = a;
a = a ^ b;

例题

1.LeetCode–配对交换

class Solution {
public:
    int exchangeBits(int n) {
          return  ((n<<1)&(0xAAAAAAAA))|((n>>1)&(0x55555555));
    }
};

题解：

• 1.为简化说明，我们以4位二进制码为例，0xAAAA 我们用 1010 代替；0x5555 我们用 0101 代替；
• 2.(n<<1)&(1010)把n先左移1位，再与1010做与运算，只保留移位之后的偶数位的值，奇数位全为0，实际上是只保留了n的奇数位的值，并把它们交换到了偶数位上。比如 n = 0110 , n<<1 = 1100, (n<<1) & 1010 = 1000 ;
• 3.(n>>1)&(0101) 把n右移一位，再与0101做与运算，只保留移位之后的奇数位的值，偶数位全为0，实际是只保留n 的偶数位的值，并把它们交换到对应的奇数位上。n = 0110； n>>1 = 0011； (n>>1) & 0101 = 0001；
• 4.最后做或运算（相加），得到1001。

2.LeetCode—只出现一次的数字

class Solution {
    public int singleNumber(int[] nums) {
    int res = 0;
    for (int i : nums) {
        res ^= i;
    }
    return res;
    }
}

题解：时间复杂度 O(N)
（1）A ^ A = 0; （2）异或满足交换律、结合律； 所有假设有数组：A B C B C D A 使用异或：

A ^ B ^ C ^ B ^ C ^ D ^ A
= A ^ A ^ B ^ B ^ C ^ C ^ D
= 0 ^ 0 ^ 0 ^ D
= 0 ^ D
= D

3.LeetCode----single-number-ii

class Solution {
  public int singleNumber(int[] nums) {
    int seenOnce = 0, seenTwice = 0;
    for (int num : nums) {
      seenOnce = ~seenTwice & (seenOnce ^ num);
      seenTwice = ~seenOnce & (seenTwice ^ num);
    }

    return seenOnce;
  }
}

当然还有拓展题，换汤不换药

3.右移与左移

1. 求n的第k位数字

n >> k & 1

2. 返回n的最后一位1

lowbit(n) = n & -n

3.乘 2 的非负整数次幂

int mulPowerOfTwo(int n, int m) {  // 计算 n*(2^m)
  return n << m;
}

4.除以 2 的非负整数次幂

int divPowerOfTwo(int n, int m) {  // 计算 n/(2^m)
  return n >> m;
}

4. 与 或 异或

1.判断一个数是不是 2 的正整数次幂

bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }

2.对 2 的非负整数次幂取模

int modPowerOfTwo(int x, int mod) { return x & (mod - 1); }

3.取绝对值

int Abs(int n) {
  return (n ^ (n >> 31)) - (n >> 31);
  /* n>>31 取得 n 的符号，若 n 为正数，n>>31 等于 0，若 n 为负数，n>>31 等于 -1
     若 n 为正数 n^0=n, 数不变，若 n 为负数有 n^(-1)
     需要计算 n 和 -1 的补码，然后进行异或运算，
     结果 n 变号并且为 n 的绝对值减 1，再减去 -1 就是绝对值 */
}

4. 取两个数的最大/最小值

// 如果 a>=b,(a-b)>>31 为 0，否则为 -1
int max(int a, int b) { return b & ((a - b) >> 31) | a & (~(a - b) >> 31); }
int min(int a, int b) { return a & ((a - b) >> 31) | b & (~(a - b) >> 31); }

5.判断符号是否相同

bool isSameSign(int x, int y) {  // 有 0 的情况例外
  return (x ^ y) >= 0;
}

5. bitset

std::bitset 是标准库中的一个存储 0/1 的大小不可变容器。严格来讲，它并不属于 STL。
使用：

• 头文件

#include <bitset>

• 指定大小
  bitset<1000> bs; // a bitset with 1000 bits
• 内置函数与运算符

bitset() : 每一位都是 false 。
bitset(unsigned long val) : 设为 val 的二进制形式。
bitset(const string& str) : 设为01串str 。

operator [] : 访问其特定的一位。
operator ==/!= : 比较两个 bitset 内容是否完全一样。
operator &/&=/|/| =/^/^=/~ : 进行按位与/或/异或/取反操作。 bitset 只能与 bitset 进行位运算 ，若要和整型进行位运算，要先将整型转换为 bitset 。
operator <</>>/<<=/>>= : 进行二进制左移/右移。
operator <</>> : 流运算符，这意味着你可以通过 cin/cout 进行输入输出。

count() : 返回 true 的数量。
size() : 返回 bitset 的大小。
test(pos) : 它和 vector 中的 at() 的作用是一样的，和 [] 运算符的区别就是越界检查。
any() : 若存在某一位是 true 则返回 true ，否则返回 false 。
none() : 若所有位都是 false 则返回 true ，否则返回 false 。
all() : C++11 ，若所有位都是 true 则返回 true ，否则返回 false 。
set() : 将整个 bitset 设置成 true 。
set(pos, val = true) : 将某一位设置成 true / false 。
reset() : 将整个 bitset 设置成 false 。
reset(pos) : 将某一位设置成 false 。相当于 set(pos, false) 。
flip() : 翻转每一位。（0-1，相当于异或一个全是  的 bitset ）
flip(pos) : 翻转某一位。
to_string() : 返回转换成的字符串表达。
to_ulong() : 返回转换成的 unsigned long 表达 ( long 在 NT 及 32 位 POSIX 系统下与 int 一样，在 64 位 POSIX 下与 long long 一样）。
to_ullong() : C++11 ，返回转换成的 unsigned long long 表达。
一些文档中没有的成员函数：

_Find_first() : 返回 bitset 第一个 true 的下标，若没有 true 则返回 bitset 的大小。
_Find_next(pos) : 返回 pos 后面（下标严格大于 pos 的位置）第一个 true 的下标，若 pos 后面没有 true 则返回 bitset 的大小。

• 应用
  （1）习题 LibreOJ——515

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 101;
const int W = 64;

struct Bitset {
    unsigned long long a[N * N * N >> 6];
    void shiftor(const Bitset& y, int p, int l, int r) {
        int t = p - p / W * W;
        int tt = (t == 0 ? 0 : W - t);
        int to = (r + p) / W;
        int qaq = (p + W - 1) / W;
        for (register int i = (l + p) / W; i <= to; ++i) {
            if (i - qaq >= 0)
                a[i] |= y.a[i - qaq] >> tt;
            a[i] |= ((y.a[i - qaq + 1] & ((1ull << tt) - 1)) << t);
        }
    }
} f[N];

int main() {
    int n, a, b, l = 0, r = 0, ans = 0;

    scanf("%d", &n);

    f[0].a[0] = 1;

    for (register int i = 1; i <= n; ++i) {
        scanf("%d%d", &a, &b);
        for (register int j = a; j <= b; ++j) f[i].shiftor(f[i - 1], j * j, l, r);
        l += a * a;
        r += b * b;
    }

    for (register int i = l / W; i <= r / W; ++i)
        ans += __builtin_popcount(f[n].a[i] & 0xffffffffu) + __builtin_popcount(f[n].a[i] >> 32);

    printf("%d", ans);

    return 0;
}

• (2)习题 CF-1097-F

#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <iostream>

using namespace std;

int read() {
  int out = 0;
  char c;
  while (!isdigit(c = getchar()))
    ;
  for (; isdigit(c); c = getchar()) out = out * 10 + c - '0';
  return out;
}

const int N = 100005;
const int M = 1000005;
const int V = 7005;

bitset<V> pre[V], pre2[V], a[N], mu;
int n, m, tot;
char ans[M];

int main() {
  int i, j, x, y, z;

  n = read();
  m = read();

  mu.set();
  for (i = 2; i * i < V; ++i) {
    for (j = 1; i * i * j < V; ++j) {
      mu[i * i * j] = 0;
    }
  }
  for (i = 1; i < V; ++i) {
    for (j = 1; i * j < V; ++j) {
      pre[i * j][i] = 1;
      pre2[i][i * j] = mu[j];
    }
  }

  while (m--) {
    switch (read()) {
      case 1:
        x = read();
        y = read();
        a[x] = pre[y];
        break;
      case 2:
        x = read();
        y = read();
        z = read();
        a[x] = a[y] ^ a[z];
        break;
      case 3:
        x = read();
        y = read();
        z = read();
        a[x] = a[y] & a[z];
        break;
      case 4:
        x = read();
        y = read();
        ans[tot++] = ((a[x] & pre2[y]).count() & 1) + '0';
        break;
    }
  }

  printf("%s", ans);

  return 0;
}

当然对于 bitset还有其他的比较男的应用例如：与树分块、莫队的结合
由于博主知识点有限大家参考这一个博客 莫队、带修莫队、树上莫队详解

快速幂

是什么？

快速幂，二进制取幂（Binary Exponentiation，也称平方法），是一个在O(loh(n))的时间内计算A^N的小技巧，而暴力的计算需要的时间。而这个技巧也常常用在非计算的场景，因为它可以应用在任何具有结合律的运算中。其中显然的是它可以应用于模意义下取幂、矩阵幂等运算

算法解释：

一般对于A^B,我们是用B个A相乘，当A或者B数字过大我们这个就将超出我们数据类型范围，所以我们就可以用二进制取幂的想法去解决这个问题。

证明：

1.实现

递归版

long long qmi(long long a, long long b) {
  if (b == 0) return 1;
  long long res = binpow(a, b / 2);
  if (b % 2)
    return res * res * a;
  else
    return res * res;
}

非递归版

long long qmi(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}

2.应用

（1）模下取幂

快速幂

LL qmi(LL a,LL b,LL c){
    LL res=1%c,t=a;
    while(b){
        if(b&1){
            res=res*t%c;
        }
        t=t*t%c;
        b>>=1;
    }
    return res%c;
}

（2）计算斐波那契数

java 实现，有兴趣可以看一下斐波那契数列相关问题

public class Fibonacci {
    static int[][] dot(int[][] A, int[][] B) {
        int Arows = A.length;
        int Acols = A[0].length;
        int Brows = B.length;
        int Bcols = B[0].length;
        assert (Acols == Brows);
        int tmp;
        int[][] R = new int[Arows][Bcols];
        for (int i = 0; i < Arows; i++) {
            for (int j = 0; j < Bcols; j++) {
                tmp = 0;
                for (int k = 0; k < Acols; k++) {
                    tmp += A[i][k] * B[k][j];
                }
                R[i][j] = tmp;
            }
        }
        return R;
    }

    static int fibonacci(int n) {
        if (n == 0) return 0;
        n -= 1;
        int[][] result = new int[][]{{1, 0}, {0, 1}};
        int[][] A = new int[][]{{1, 1}, {1, 0}};
        while (n > 0) {
            if (n % 2 == 1) {
                result = dot(result, A);
            }
            n /= 2;
            A = dot(A, A);
        }
        return result[0][0];
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(100000));
    }
}

3.习题

习题一
习题二

高精度

由于高精度运算理解过于简单所以我们这=这里基本不做过多的解释。

对于java 与 python 选手 可以略过
实现

1.对于高精度的存储问题

为了方便理解我这里用数组，但是一般竞赛我们一般用vertor，怎么方便怎么来，hhhhh
注意这里的问题 -----读与写的顺序问题

对于高精度的复读程序-----（ 来吧 复读机们）

#include <cstdio>
#include <cstring>

static const int LEN = 1004;

int a[LEN], b[LEN];

void clear(int a[]) {
  for (int i = 0; i < LEN; ++i) a[i] = 0;
}

void read(int a[]) {
  static char s[LEN + 1];
  scanf("%s", s);

  clear(a);

  int len = strlen(s);
  for (int i = 0; i < len; ++i) a[len - i - 1] = s[i] - '0';
}

void print(int a[]) {
  int i;
  for (i = LEN - 1; i >= 1; --i)
    if (a[i] != 0) break;
  for (; i >= 0; --i) putchar(a[i] + '0');
  putchar('\n');
}

int main() {
  read(a);
  print(a);

  return 0;
}

2.四则运算

（1）加法

从最低位开始，将两个加数对应位置上的数码相加，并判断是否达到或超过10。如果达到，那么处理进位：将更高一位的结果上增加1，当前位的结果减少10。

void add(int a[], int b[], int c[]) {
  clear(c);
  for (int i = 0; i < LEN - 1; ++i) {
    // 将相应位上的数码相加
    c[i] += a[i] + b[i];
    if (c[i] >= 10) {
      // 进位
      c[i + 1] += 1;
      c[i] -= 10;
    }
  }
}

（2）减法

从个位起逐位相减，遇到负的情况则向上一位借1。整体思路与加法完全一致

void sub(int a[], int b[], int c[]) {
  clear(c);
  for (int i = 0; i < LEN - 1; ++i) {
    // 逐位相减
    c[i] += a[i] - b[i];
    if (c[i] < 0) {
      // 借位
      c[i + 1] -= 1;
      c[i] += 10;
    }
  }
}

（3）乘法

A.高精度—单精度
就是a的每一位数乘以b即可，再加上一些细节处理

void mul_short(int a[], int b, int c[]) {
  clear(c);

  for (int i = 0; i < LEN - 1; ++i) {
    // 直接把 a 的第 i 位数码乘以乘数，加入结果
    c[i] += a[i] * b;

    if (c[i] >= 10) {
      // 处理进位
      // c[i] / 10 即除法的商数成为进位的增量值
      c[i + 1] += c[i] / 10;
      // 而 c[i] % 10 即除法的余数成为在当前位留下的值
      c[i] %= 10;
    }
  }
}

B.高精度—高精度
可以将b分解为它的所有数码，其中每个数码都是单精度数，将它们分别与a相乘，再向左移动到各自的位置上相加即得答案。当然，最后也需要用与上例相同的方式处理进位。

void mul(int a[], int b[], int c[]) {
  clear(c);
  for (int i = 0; i < LEN - 1; ++i) {
    // 这里直接计算结果中的从低到高第 i 位，且一并处理了进位
    // 第 i 次循环为 c[i] 加上了所有满足 p + q = i 的 a[p] 与 b[q] 的乘积之和
    // 这样做的效果和直接进行上图的运算最后求和是一样的，只是更加简短的一种实现方式
    for (int j = 0; j <= i; ++j) c[i] += a[j] * b[i - j];

    if (c[i] >= 10) {
      c[i + 1] += c[i] / 10;
      c[i] %= 10;
    }
  }
}

（4）除法

// 被除数 a 以下标 last_dg 为最低位，是否可以再减去除数 b 而保持非负
// len 是除数 b 的长度，避免反复计算
inline bool greater_eq(int a[], int b[], int last_dg, int len) {
  // 有可能被除数剩余的部分比除数长，这个情况下最多多出 1 位，故如此判断即可
  if (a[last_dg + len] != 0) return true;
  // 从高位到低位，逐位比较
  for (int i = len - 1; i >= 0; --i) {
    if (a[last_dg + i] > b[i]) return true;
    if (a[last_dg + i] < b[i]) return false;
  }
  // 相等的情形下也是可行的
  return true;
}

void div(int a[], int b[], int c[], int d[]) {
  clear(c);
  clear(d);

  int la, lb;
  for (la = LEN - 1; la > 0; --la)
    if (a[la - 1] != 0) break;
  for (lb = LEN - 1; lb > 0; --lb)
    if (b[lb - 1] != 0) break;
  if (lb == 0) {
    puts("> <");
    return;
  }  // 除数不能为零

  // c 是商
  // d 是被除数的剩余部分，算法结束后自然成为余数
  for (int i = 0; i < la; ++i) d[i] = a[i];
  for (int i = la - lb; i >= 0; --i) {
    // 计算商的第 i 位
    while (greater_eq(d, b, i, lb)) {
      // 若可以减，则减
      // 这一段是一个高精度减法
      for (int j = 0; j < lb; ++j) {
        d[i + j] -= b[j];
        if (d[i + j] < 0) {
          d[i + j + 1] -= 1;
          d[i + j] += 10;
        }
      }
      // 使商的这一位增加 1
      c[i] += 1;
      // 返回循环开头，重新检查
    }
  }
}

3.yls的视频讲解与模板

视频讲解

模板：
高精度加法 —— 模板题 AcWing 791. 高精度加法

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

高精度减法 —— 模板题 AcWing 792. 高精度减法

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

高精度乘低精度 —— 模板题 AcWing 793. 高精度乘法

// C = A * b, A >= 0, b > 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

高精度除以低精度 —— 模板题 AcWing 794. 高精度除法

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

作者：yxc
链接：https://www.acwing.com/blog/content/277/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

总结

对于位运算、快速幂和高精度一般会用于对一些题目的深化和优化，位运算就是会用bitset和lowbit运算就好了，快速幂要注意二进制取幂的展开，要将它拓展到龟速乘的证明上，对于高精度这个四则运算，由于原理比较简单，所以最关键就在与你的实现细节，比如前置0，处理顺序和位数等问题，当然对于这一些知识点肯定还有一些还有写错的地方和没有写道的地方，非常感谢你的阅读，欢迎大家的指正与补充！

补充

1.对于对于二进制加法关于-1+1的问题

最高位溢出的进位会被忽略掉，最后剩下 32个
感谢明朗编程 与yxc