位运算.md

• 位运算基本概念
• 位运算基本操作
• 位运算题型
  • Acwing.801 二进制中1的个数

---

位运算基本概念

位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。

	与	或	异或
运算符	&	|	^
表示	两个对应位都为 1 时才为 1	两个对应位都为 0 时才为 0	两个对应位不同时才为 1

假设数字 $x$ 的源码是
1010000100101
反码是源码取反，~x
0101111011010
补码是源码取反 +1 ~x + 1
0101111011011

位运算基本操作

输出数字 $x$ 二进制表示的第 $i$ 位数字

• 原理：将第 $i$ 位右移 $i$ 移到最低位上，和 $1$ 做与的运算，如果第 $i$ 位为 $0$，则输出 $0$，如果第 $i$ 位为 $1$，则输出 $1$，这样就取出了第 $i$ 位数字

int find(int x, int i){
    return x >> i & 1;
}

删除数字 $x$ 的最后一位 $1$

• 原理：如果 $x$ 的二进制表示为 $1101000$，那么 $x-1$ 二进制表示为 $1100111$，x & (x - 1)计算的结果为 $1100000$，最后一位 $1$ 变成了 $0$，其它位不变

x & (x - 1);

返回数字 $x$ 的最后一位 $1$

• 原理：如果 $x$ 的二进制表示为 $1101000$，那么 $~x$ 二进制表示为 $0010111$，$~x+1$ 二进制表示为 $0011000$，x & (~x+1) == x & (-x)的计算结果为 $0001000$ 只保留了最后一位 $1$，其余位都为 $0$

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

位运算题型

Acwing.801 二进制中1的个数

• 链接https://www.acwing.com/problem/content/description/803/

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

输入格式
第一行包含整数 $n$。

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

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

数据范围
$1≤n≤100000$,
$0≤数列中元素的值≤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 res = 0;
        while (x){
            x -= lowbit(x);// 也可以 x & (x - 1) 不用lowbit操作
            res ++;
        }
        
        cout << res << ' ';
    }
    return 0;
}