位运算

一、算法思想

1.1 求 x 的第 k 位数字

1. 先把第 k 位移到最后一位：x >> k；
2. 查看个位数字：x & 1。

综上，可通过 x >> k & 1 得到 x 的第 k 位数字。

1.2 返回 x 的最后一位 1

1. x = 1010...1000
2. ~x = 0101...0111
3. ~x + 1 = 0101...1000
4. x & (~x + 1) = 1000 = x & -x

二、算法模板

C++

// 求 x 的第 k 位数字
int bit = x >> k & 1;

// 求 x 的第 k 位数字
int lowbit(int x)
{
    return x & -x;
}

三、代码实战

AcWing 0801

---

题目：二进制中 1 的个数

给定一个长度为 $n$ 的数列，请你求出数列中每个数的二进制表示中 $1$ 的个数。

输入格式

第一行包含整数 $n$。

第二行包含 $n$ 个整数，表示整个数列。

输出格式

共一行，包含 $n$ 个整数，其中的第 $i$ 个数表示数列中的第 $i$ 个数的二进制表示中 $1$ 的个数。

数据范围

$1 \le n \le 100000$

$0 \le \text{数列中元素的值} \le 10^9$

输入样例：

5

1 2 3 4 5

输出样例：

1 1 2 1 2

解答代码：

#include <iostream>
using namespace std;

int lowbit(int x)
{
    return x & -x;
}

int main()
{
    int n;
    cin >> n;
    
    while (n--) {
        int x;
        cin >> x;
        
        int ans = 0;
        while (x) {
            x -= lowbit(x);
            ans++;
        }
        
        cout << ans << ' ';
    }
    
    return 0;
}