第一讲 基础算法 - 07 位运算

AcWing 801. 二进制中1的个数 - 糖豆爸爸 - 博客园
AcWing 算法基础课笔记 1.基础算法-CSDN
AcWing《算法基础课》第1章 算法基础 - AcWing

---

位运算

1 核心思想

讲两种最常用的操作.

1.1 n >> k & 1

n >> k & 1 返回 x 右起第 k 位二进制数

n 的二进制表示中第 k 位是几 (从右往左, 低位到高位) ?

• 先把第 k 位移到最后一位 n >> k
• 看个位是几 n & 1
• 结合一、二步，可得 n >> k & 1

应用: 可以求一个数的二进制数, 比如 10(10) 的二进制数是 1010(2)

#include <iostream>
using namespace std;

int main()
{
    int n = 10;
    // 10 的二进制有 4 位, 所以 k = 3; k >= 0;
    for (int k = 3; k >= 0; k -- ) cout << (n >> k & 1);
}

1.2 lowbit(x)

lowbit(x) 从低位开始返回直至 x 的最后一位 1

比如:

 x        lowbit(x)
1010      10
1010000   10000

lowbit 的实现原理 lowbit(x) = x & -x
因为 -n 是 n 的负数，即为 n 的补码加 1 ：-x = ~x + 1
故 x & -x = x & (~x + 1)

应用 : 可以求二进制中 1 的个数

2 模板

返回 n 右起第 k 位二进制数: n >> k & 1
返回 n 的最后 1 位 1 ：lowbit(n) = n & -n

说明:

• 若让 x 不停地减去最后一位 1，直到变成 0 ，做减法的次数就是 x 二进制表示的 1 的个数
• 可用 for(int k = 31; k >= 0; k--) 把 int 转成二进制数

3 扩展知识 *

详细讲解看这位大佬: AcWing 801. 二进制中1的个数 - 糖豆爸爸 - 博客园

位运算两个性质:

• x & (−x)：保留二进制下最后出现的 1 的位置，其余位置置 0
• x & (x−1)：消除二进制下最后出现的 1 的位置，其余保持不变