前言

此博文用于记录我学习到的一些算法思想，语言是c++或者python。

cpp竞赛模板

第一行的万能头大部分情况下是能用的，如果不能用，那就手动导入iostream等等的库。

#include <bits/stdc++.h>
using namespace std;

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // code here
}

py和cpp时间复杂度对比

• 这是单机、单核、主流在线评测平台（如LeetCode、Codeforces、牛客、洛谷等）上1秒内大致能承受的数据规模。
• C++ 由于编译型、无解释器开销，所以通常比 Python 快 5~10 倍，甚至更高。
• 复杂度上升一档，数据规模要大幅缩小！

c++一些需要注意的地方

1.快速输入输出

c++默认的cin cout在数据量很大时输入输出很慢，可以在main函数的开头加上如下两行（此时输入输出只能是cin cout，不能再用scanf和printf了）：

ios::sync_with_stdio(false);
cin.tie(nullptr);

尤其是在处理矩阵时，差两行这个可能会让你从ac到超时。

2.unsigned数据类型的溢出反倒可以自动取模

举个例子，unsigned long long正好到2^64-1的大小，所以如果此时输入2^64或者更大的数，相当于自动对2的64次方取模(mod)，实现了啥都不干自动就取模了。

c++主要数据类型的范围和取模的关系：

3.set的使用

用途

在需要不断维护一个有序列表，并且需要经常插入、寻找、删除、修改的，用set这个数据结构是十分高效且合适的。

时间复杂度

平均为O(logn)

使用方法

相关题目

https://www.luogu.com.cn/problem/P5250

Python一些需要注意的地方

1.浅拷贝问题——如何正确创建矩阵

在Python中，创建一维列表有两种创建方式：

list1=[0]*length
list2=[0 for _ in range(length)]

随意选择即可。

但是创建二维列表就不一样了，虽然也有两种方式：

matrix1=[[0 for _ in range(length1)] for _ in range(length2)]
matrix2=[[0]*length1 for _ in range(length2)]

我知道你肯定想写这种：

matrix3=[[0]*length1]*length2

那你猜会发生什么？正如标题所言，浅拷贝：

假设你使得matrix[0][2]=1，那么matrix[1][2] matrix[2][2] matrix[3][2]...全都会等于1。

也就是相当于你这样生成矩阵，python相当于复制了一堆引用，也算是一个特性吧，所以不要这么写。

2.append中暴露的引用问题

看下面的代码：

def a(lis,cnt):
    global result
    if cnt>=5:
        return
    lis.append(1)
    result.append(lis)
    a(lis,cnt+1)
result=[]
a([],1)
print(result)

你肯定会认为，最后的结果是这样：

[[1], [1, 1], [1, 1, 1], [1, 1, 1, 1]]

实际是这样的：

[[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]

为什么呢？因为在函数中，append进result中的lis其实是一个引用，所以result实际上是这样的：[lis,lis,lis,lis]，所以最后lis是啥值，就会有四个一样的值。

要解决这个问题，直接在lis后面加.copy即可：

def a(lis,cnt):
    global result
    if cnt>=5:
        return
    lis.append(1)
    result.append(lis.copy())
    a(lis,cnt+1)
result=[]
a([],1)
print(result)

这样输出就正常了。

这个问题常常在递归函数访问外部变量时出现，如果想彻底避免这个问题，每次多写个copy就行了，反正又不会影响运行。

3.递归深度问题

在做一些一眼递归的题目时，如果发现数据量很大，需要递归很多次，还是能转循环的转循环吧，尽量不要用递归，不然会爆栈，反而弹出c语言的错误。

能否到达：DFS递归写法

经典走迷宫写法

题目见：https://www.luogu.com.cn/problem/B3625

#include <bits/stdc++.h>
using namespace std;

int n, m;
// 迷宫地图：'#' 表示墙，'.' 表示空地
vector<string> grid;
// 访问标记
vector<vector<bool>> vis;
// 四个方向：下、上、右、左
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

// 递归 DFS：
// 返回值：从 (x,y) 出发，能否到达终点 (n-1, m-1)
bool dfs(int x, int y) {
    // 1）越界或遇墙或已访问 → 剪枝
    if (x < 0 || x >= n || y < 0 || y >= m) return false;
    if (grid[x][y] == '#' || vis[x][y])      return false;

    // 2）标记当前格已访问
    vis[x][y] = true;

    // 3）到达终点，直接返回 true
    if (x == n-1 && y == m-1) {
        return true;
    }

    // 4）依次尝试四个方向，只要有一条路返回 true 就可
    for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (dfs(nx, ny)) {
            return true;  // 子调用找到路了，直接向上层返回
        }
    }

    // 5）如果四个方向全部失败，可选地「回溯」时撤销标记：
    //    vis[x][y] = false;
    //    这里只问能否到达，不需要路径，所以不撤销也行。
    //提示：时间复杂度爆炸，如果只想知道是否能到达，不要撤销，不然会超时。
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 读入
    cin >> n >> m;
    grid.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    vis.assign(n, vector<bool>(m, false));

    // 从 (0,0) 开始 DFS
    bool canReach = dfs(0, 0);
    cout << (canReach ? "Yes\n" : "No\n");
    return 0;
}

大概就是利用了递归天然自动回溯的特性，可以减少一些代码量，而且速度也不会太慢。

当遇到递归边界时，它就会自动返回到刚刚的路口，选择另外的路。

在递归中，差不多就是四步走：

1. 判断是否无法行走，然后剪枝
2. 给当前方块标记已访问
3. 判断是否在终点，然后返回true
4. 继续尝试其他可用的方向

需要记住的要素：

1. 访问标记二维数组
2. 递归退出条件：到达终点或者剪枝时

遍历树的写法

相关题目：https://www.luogu.com.cn/problem/P5318

bool dfs(int node){
    //1.如果当前点已访问，直接走
    if (visited[node-1]){
        return false;
    }
    //2.标记当前点已访问
    visited[node-1]=true;
    //3.输出当前点
    cout << node << " ";
    //4.如果接下来没点了，直接走
    if (tree[node-1].empty()){
        return false;
    }
    //5.遍历不同方向
    for (int i=0;i<tree[node-1].size();++i){
        if (dfs(tree[node-1][i])){
            return true;
        }
    }
    return false;
}

枚举这个东西选不选的写法

相关题目：https://www.luogu.com.cn/problem/P2036

def generate(pos,lis):
    global results
    global n
    if pos==n:
        results.append(lis.copy())#这里一定要copy，不然存入的是引用，后续lis的值变了就导致results里面的lis一直变
        return
    #下个东西取或不取
    lis.append(1)#取
    generate(pos+1,lis)
    lis.pop()#撤销
    lis.append(0)#不取
    generate(pos+1,lis)
    lis.pop()#撤销

results=[]
#开始举出所有情况
generate(0,[])
print(results)

全排列写法

相关题目：https://www.luogu.com.cn/problem/P1706

def dfs(n,used,path):
    if not 0 in used:#全都用过了
        for j in path:
            print("{:5d}".format(j),end="")
        print()
        return
    for i in range(1,n+1):
        if used[i-1]==0:
            path.append(i)
            used[i-1]=1
            dfs(n,used,path)
            used[i-1]=0#复原
            path.pop()#复原

N = int(input())
dfs(N,[0 for i in range(N)],[])

最短路径：BFS队列写法

走迷宫写法

相关题目：https://www.luogu.com.cn/problem/P1443

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 1）读入 n 行 m 列的迷宫尺寸
    int n, m;
    cin >> n >> m;

    // 2）读入迷宫地图：'.' 为空地，'#' 为墙
    vector<string> grid(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }

    // 3）方向数组，表示四个相邻的偏移：下、上、右、左
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    // 4）距离数组 dist[x][y]：从起点 (0,0) 到 (x,y) 的最短步数
    //    初始化为 -1，表示未访问过
    vector<vector<int>> dist(n, vector<int>(m, -1));

    // 5）队列，用来按“层”来遍历所有可达节点
    queue<pair<int,int>> q;

    // 6）BFS 起点初始化
    dist[0][0] = 0;          // 起点自身距离为 0
    q.emplace(0, 0);         // 将起点入队，开始 “波纹” 扩散

    // 7）开始标准的 BFS 循环
    while (!q.empty()) {
        // 7.1）取出当前队首节点 (x,y)
        auto [x, y] = q.front();
        q.pop();

        // 7.2）如果已经到达终点 (n-1,m-1)，可以提前终止循环
        if (x == n-1 && y == m-1) {
            break;
        }

        // 7.3）尝试向四个方向扩散
        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];  // 下一个点的横坐标
            int ny = y + dy[dir];  // 下一个点的纵坐标

            // 7.3.a）边界检查：必须在 [0,n) 和 [0,m) 范围内
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                continue;
            }

            // 7.3.b）障碍物或已访问：墙 '#' 或 dist 已被设置过
            if (grid[nx][ny] == '#' || dist[nx][ny] != -1) {
                continue;
            }

            // 7.3.c）合法的新格子：
            //        ① 标记最短距离 = 当前距离 + 1
            dist[nx][ny] = dist[x][y] + 1;
            //        ② 把它加入队列，后续再扩散它的邻居
            q.emplace(nx, ny);
        }
    }

    // 8）循环结束后，检查终点是否被访问
    if (dist[n-1][m-1] == -1) {
        // dist 仍是 -1，代表终点不可达
        cout << "No\n";
    } else {
        // 否则输出最短路径长度
        cout << "Yes\n";
        cout << dist[n-1][m-1] << "\n";
    }

    return 0;
}

利用队列“先进先出”的特性，保证在遍历迷宫时是一层一层往下遍历的——每一轮遍历的点到起点的最短距离均相等。这样就可以保证，在遍历到终点时，这个路径一定是最短的。因为如果还有更短的路径，它在上一轮遍历时就应该出现。

BFS要素：

1. 记录距离的二维数组
2. 记录某点是否访问过的二维数组
3. 保证处理次序的队列

遍历树的写法

相关题目：https://www.luogu.com.cn/problem/P5318

int main(){
    int n,m;
    cin >> n >> m;
    tree.assign(n,vector<int>());
    visited.assign(n,false);
    visited2.assign(n,false);
    //构建树
    for (int i=0;i<m;++i){
        int pos,re;
        cin >> pos >> re;
        tree[pos-1].emplace_back(re);
    }
    //给re排序
    for (int i=0;i<n;++i){
        sort(tree[i].begin(),tree[i].end());
    }
    //开始bfs
    queue <int> q;
    visited2[0]=true;
    q.emplace(1);
    while (!q.empty()){
        //取出队首节点
        int cNode = q.front();
        q.pop();
        cout << cNode << " ";
        //尝试不同方向
        for (int i=0;i<tree[cNode-1].size();++i){
            int nNode=tree[cNode-1][i];
            //检查是否访问过
            if (visited2[nNode-1]){
                continue;
            }
            //未访问过即为合法，加入队列等待后续扩散
            q.emplace(nNode);
            visited2[nNode-1]=true;
        }
    }
    return 0;
}

DP(动态规划)

0-1背包问题

相关题目：https://www.luogu.com.cn/problem/P1048

#include <bits/stdc++.h>
using namespace std;

/*
 * 0-1 背包示例（二维数组 DP）
 * 问题描述：
 *   给定 N 件物品和一个容量为 W 的背包。
 *   第 i 件物品的重量为 w[i]，价值为 v[i]。
 *   每件物品只能选 0 次或 1 次，求在不超过背包容量的前提下，能够获得的最大总价值。
 *
 * DP 状态定义：
 *   dp[i][j] 表示：在只考虑前 i 件物品（1..i），背包容量恰好为 j 时能取得的最大价值。
 *
 * 转移方程：
 *   不选第 i 件物品：dp[i][j] = dp[i-1][j]
 *   选第 i 件物品：dp[i][j] = dp[i-1][j - w[i]] + v[i]  （前提 j >= w[i]）
 *   取两者最大值即可。
 *
 * 边界 & 初始条件：
 *   dp[0][*] = 0，表示不考虑任何物品时，价值为 0。
 *   dp[*][0] = 0，表示容量为 0 时，价值为 0。
 *
 * 最终答案：
 *   dp[N][W]，即考虑完 N 件物品后，容量为 W 的最大价值。
 */

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, W;
    // 输入物品数量 N 和背包容量 W
    cin >> N >> W;

    vector<int> w(N + 1), v(N + 1);
    // 读入每件物品的重量 w[i] 和价值 v[i]，下标从 1 开始
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> v[i];
    }

    // 构造 N+1 行，W+1 列的 dp 数组，初始值均为 0
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));

    // 进行状态转移
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= W; j++) {
            // 1. 不选第 i 件物品
            dp[i][j] = dp[i - 1][j];

            // 2. 选第 i 件物品（前提：背包剩余容量 j >= w[i]）
            if (j >= w[i]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
            }

            // （可选）打印中间 dp 值以便调试
            // cerr << "dp[" << i << "][" << j << "] = " << dp[i][j] << "\n";
        }
    }

    // 输出最终结果：考虑完所有 N 件物品、容量恰为 W 时的最大价值
    cout << dp[N][W] << "\n";
    return 0;
}

dp的本质其实就是：

1. 有限背包空间，需要创造最大的价值，方法其实藏在每次的选择之中。
2. 每次都有拿和不拿这个物品，我们无法一下子就判断拿不拿，就只能通过二维数组将所有可能存储起来，又保证了不会超出背包空间。
3. 然后最后构建完成dp后，就可以取最后一个物品，用满背包空间的值，则为最大的价值。

完全背包问题

给定：

• n种物品，每种物品有一个重量 wi 和一个价值 vi。
• 背包容量为 W。
• 每种物品的数量不限。

目标：选择若干个物品放入背包，使总重量不超过 W，且总价值最大。

n, W = 3, 7
w = [0, 2, 3, 4]    # 下标从1开始
v = [0, 3, 4, 5]
dp = [0] * (W + 1)

for i in range(1, n+1):
    for j in range(w[i], W+1):
        dp[j] = max(dp[j], dp[j-w[i]] + v[i])

print(dp[W])  # 输出最大价值

有点不一样：最长上升子序列

相关题目：https://www.luogu.com.cn/problem/B3637

#输入数据
n=int(input())
nums=list(map(int,input().split()))
#初始化存储尾巴的数组
tail=[]
for i in range(n):
    if (not tail) or nums[i]>max(tail):#如果尾巴数组为空或者数字比尾巴数组里面的全部数都大
        tail.append(nums[i])#将数字放到尾巴数组尾部
    else:#否则寻找第一个比该数字大的位置
        for j in range(len(tail)):
            if nums[i]<=tail[j]:
                tail[j]=nums[i]#将其替换
                break#然后就退出寻找，因为是只找第一个
print(len(tail))#然后尾巴数组的长度就是最长上升子序列

为何最后尾巴数组的长度就是最长上升子序列的长度？这个我也不清楚。只要记住就行了。

有一个基本思想就是：我们在不断优化尾部的数字。假如我给4加到了尾部，结果遍历到后面发现存在3，那就把4换成3，保证尾部的数字尽量小，这样才能最有可能接下去。

记忆化搜索

用途

在进行比较多的递归运算时，将算好的值存入缓存(Python中用dict，C++中用map)，下次遇到同样的值直接从缓存中拿取就行，查询缓存的时间复杂度O(1)。

Python代码模板

mem={}#用字典存放缓存
def w(a,b,c):
    global mem#记得全局化变量，因为要读写
    key=(a,b,c)
    if key in mem:#如果在缓存中，直接返回
        return mem[key]
    #否则继续递归
    #在这里写递归逻辑...
    #然后将值存入缓存中
    mem[key] = value
    return value
print(w(1111,2222,3333))

使用Dict存放函数参数->函数值的键值对，因为有哈希，查询飞速。

相关题目

https://www.luogu.com.cn/problem/P1464

贪心

本质

在每一步都做出一个局部最优的选择，然后把结果累积下去。

1.Kadane 算法

算法用途

一般用于解决最大连续子段和的问题。

算法框架

n=int(input())
a=list(map(int,input().split()))
#直接开始贪心累加
maxPart=a[0]
maxSum=float('-inf')
for i in range(1,n):
    maxPart=max(maxPart+a[i],a[i])#前者是继续取这个，后者是舍弃掉前面的，从这个重新开始
    maxSum=max(maxSum,maxPart)#维护一个最大段
print(maxSum)

算法原理/如何体现贪心

在上方的代码中，维护了一个maxPart变量，比较加上当前数(继续连着)和在当前数重新开一个子序列的大小，取最大。因为如果我加上当前数字还不如我直接取当前数字大，那还不如新开一个子序列，没必要继续延续之前的。

由于我会这样一直线性处理到最后，无法判断哪一段子序列是最大的，因此只能再起一个变量来维护子序列的最大值。

相关题目

https://www.luogu.com.cn/problem/P1115

变种

一般最大连续子段和必须得求一个答案出来，也就是我们必须至少选择一个数，所以maxPart就只能在拿这个值加上之前的值和只拿当前值来选择。但是我遇到了一道题：https://www.luogu.com.cn/problem/P11642

它可以选择不操作。我一开始看到还一头雾水，怎么a[i]还能改成0了，后来理解了。

所以此时，只需要把maxPart=max(maxPart+a[i],a[i])改成maxPart=max(maxPart+a[i],0)，也就是只允许正提升。

还是需要灵活一些，随机应变。

二分查找

用途

相当于枚举的优化版本，本质还是枚举，只是想明白这个枚举能不能通过某次试验的结果来决定将值变大还是变小，否则不能用二分。

就举一个最简单的二分猜数字吧，很多人编程的入门代码，其实就是一种二分查找。当我猜一个数，如果你说“小了”，那我就知道我要给数加大；如果你说“大了”，那我就知道给数减小。这就是每次试验的结果的一种很直接的反馈了。

Python代码

l=minValue
r=maxValue#左指针右指针初始存放题目中合理的枚举范围，减少不必要的枚举
ans=Value#答案初始化为不进入二分的情况下应该输出的结果，防止题目产生hack数据恶心你
while l<=r:
    mid=(l+r)//2
    result=0#用于比较大小的值
    #此处插入处理逻辑
    if result>certainValue:#如果比特定的值更大，需要减小
        r=mid-1
    else:#比特定值小或者等于，还能变大
        ans=mid#存储下当前的可能答案，万一下次二分不行了就可以直接输出这个
        l=mid+1
print(ans)#输出答案

相关题目

https://www.luogu.com.cn/problem/P2678

前缀和

一维前缀和

用途：告诉你一个数组，需要多次求区间和。

代码模板：

n = int(input())
a = [0] + list(map(int, input().split())) # a[1]~a[n]
s = [0] * (n + 1)
for i in range(1, n + 1):
    s[i] = s[i-1] + a[i]

# 区间和 [l, r]:
def query(l, r):
    return s[r] - s[l-1]

在构造时需要o(n)，但是在构造完成后，求区间和只需要o(1)。

二维前缀和

用途：告诉你一个矩阵，需要多次求左上角某个点到右下角某个点区间内值的总和。

代码模板：

n, m = map(int, input().split())
a = [[0] * (m + 1)]
for _ in range(n):
    a.append([0] + list(map(int, input().split())))  # 下标从1开始

# 计算前缀和
s = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]

# 查询子矩阵
def query(x1, y1, x2, y2):
    return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]

注意：里面的坐标都是1based。

时间复杂度：构造时是O(n*m)，求和时O(1)。

后缀和

# 输入：长度为 n 的数组 a
n = len(a)
suffix_sum = [0] * (n + 1)  # 多开一位，suffix_sum[n]=0 方便处理

# 从后往前累加
for i in range(n - 1, -1, -1):
    suffix_sum[i] = suffix_sum[i + 1] + a[i]

# 现在 suffix_sum[i] 表示从 a[i] 到 a[n-1] 的和
# 例如：区间 [l, r] 的和 = suffix_sum[l] - suffix_sum[r + 1]

差分

用途

差分数组是对原数组的“变化量”进行编码，能让区间加法操作的复杂度从 O(n) 优化到 O(1)。它常出现在算法竞赛和工程开发中，特别是在需要多次区间加减时，可以极大提升效率。

如何构建

给定一个原数组 A，构建差分数组 D：

• D[1] = A[1]
• D[i] = A[i] - A[i-1] （i > 1）

如何操作区间加法

假设你要将区间 [l, r] 内每个元素加上一个数 x，普通做法需要 O(r-l+1) 的复杂度遍历每个元素。用差分数组，只需两步：

1. D[l] += x
2. D[r+1] -= x（如果 r+1 在范围内）

如何还原回原数组

最后只需对差分数组做前缀和即可还原出最终结果：

A[1] = D[1]
A[2] = D[1] + D[2]
A[3] = D[1] + D[2] + D[3]
...
也就是 A[i] = D[1] + D[2] + ... + D[i]

代码模板

def apply_operations(n, operations):
    """
    n: 原数组长度
    operations: 每个元素是 [l, r, x]，表示将区间 [l, r] 加 x
    返回：操作后的数组
    """
    diff = [0] * (n+2)  # n+2 是因为要防止越界
    for l, r, x in operations:
        diff[l] += x
        diff[r+1] -= x
    # 还原原数组
    res = [0] * (n+1)
    for i in range(1, n+1):
        res[i] = res[i-1] + diff[i]
    return res[1:]

相关题目

https://www.luogu.com.cn/problem/P1083

数学基础

1.组合数

定义

$$ \binom{n}{k} = \frac{n!}{k! \, (n-k)!} $$

计算方法

1. 阶乘公式

$$ \binom{n}{k} = \frac{n!}{k! \, (n-k)!} $$

2. 递推公式

$$ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} $$

3. 乘积形式

$$ \binom{n}{k} = \prod_{i=1}^k \frac{n - k + i}{i} = \frac{n(n-1)\cdots(n-k+1)}{k!} $$

示例

$$ \binom{5}{2} = \frac{5!}{2! \cdot 3!} = \frac{5 \times 4}{2 \times 1} = 10 $$

适用于

求不同长度的区间和种类时比较好用，别的暂时没发现。见题目：https://www.luogu.com.cn/problem/P8649

2.质数筛

用途

需要一次性判断大量数是否为质数。

原理/方法

如果一个数是质数，那么从它的平方开始，它的倍数一定不是质数。

通过这个原理，我们只需要先找到这群数中最大的数，然后以这个为范围，生成质数表。

在生成表时，遇到一个质数，可以立马排除后面的一些非质数。

生成表的时间复杂度为O(n^2)，查询的时间复杂度为O(1)。

代码

def get_primes(N):
    is_prime = [True] * (N + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(N**0.5) + 1):#从2遍历到它的平方根+1
        if is_prime[i]:#如果是质数
            for j in range(i*i, N+1, i):#将从它本身平方开始的所有倍数都排除
                is_prime[j] = False
    return is_prime
# 用法：is_prime[17] 就是 17 是否为质数

相关题目

https://www.luogu.com.cn/problem/P1036

字符串处理

位运算

在 Python 中，常用的位运算符如下：

示例

a = 5      # 二进制 0101
b = 3      # 二进制 0011

print(a & b)   # 结果: 1   (0001)
print(a | b)   # 结果: 7   (0111)
print(a ^ b)   # 结果: 6   (0110)
print(~a)      # 结果: -6  (补码表示)
print(a << 1)  # 结果: 10  (1010)
print(a >> 1)  # 结果: 2   (0010)

有用的技巧

• 检查第k位是否为1：(a >> k) & 1
• 只保留低k位：a & ((1 << k) - 1)
• 交换a,b：a, b = b, a