一、基础算法7：位运算模板题+算法模板（二进制中1的个数）

红太狼 2023-10-09 18:01 7阅读 0赞

#### 文章目录 ####

*  算法模板
 *   *  求n的第k位数字
     *  返回n的最后一位1
     *  求一个数x的二进制中1的个数模板
 *  模板题
 *   *  二进制中1的个数
     *   *  原题链接
         *  题目
         *  题解
 *  补充
 *   *  输出一个数n的补码x的二进制并按位输出
     *  关于原码，反码，补码

## 算法模板 ##

### 求n的第k位数字 ###

n >> k & 1

![在这里插入图片描述][bb8750e803ec4020a1b403d9e0cbbd5a.png]

### 返回n的最后一位1 ###

lowbit(n) = n & -n

![在这里插入图片描述][1415242dc74b4fcbaa50f4a72a4b79a8.png]  
![在这里插入图片描述][aa4442c79d06464ba384b0721681da24.png]

### 求一个数x的二进制中1的个数模板 ###

int res = 0;
    		while(x){
         //当x为0时表示x二进制表示中没有1，否则x二进制表示中还有1 
    			x-=lowbit(x); //每次减去二进制中最后一个1 
    			res++;
    		}
    		cout<<res<<" ";

## 模板题 ##

### 二进制中1的个数 ###

#### 原题链接 ####

[https://www.acwing.com/problem/content/803/][https_www.acwing.com_problem_content_803]

#### 题目 ####

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

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

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

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

数据范围  
1≤n≤100000  
,  
0≤数列中元素的值≤109  
输入样例：

5
    1 2 3 4 5

输出样例：

1 1 2 1 2

#### 题解 ####

#include <iostream>
    using namespace std;
    const int N = 1e5 + 10;
    int lowbit(int x){
        
    	return x & -x;
    	// -x = ~x+1
    }
    
    int n;
    int main(){
        
    	cin>>n;
    	
    	int x;
    	while(n--){
        
    		cin>>x;
    		int res = 0;
    		while(x){
         //当x为0时表示x二进制表示中没有1，否则x二进制表示中还有1 
    			x-=lowbit(x); //每次减去二进制中最后一个1 
    			res++;
    		}
    		cout<<res<<" ";
    	}
    	return 0;
    }

## 补充 ##

### 输出一个数n的补码x的二进制并按位输出 ###

![在这里插入图片描述][0026e450454449629be12050babe9e19.png]

### 关于原码，反码，补码 ###

![在这里插入图片描述][485b10109e8b44e294c6c487bfd0c148.png]  
参考文章：[原码、反码、补码][Link 1]

[bb8750e803ec4020a1b403d9e0cbbd5a.png]: https://img-blog.csdnimg.cn/bb8750e803ec4020a1b403d9e0cbbd5a.png
[1415242dc74b4fcbaa50f4a72a4b79a8.png]: https://img-blog.csdnimg.cn/1415242dc74b4fcbaa50f4a72a4b79a8.png
[aa4442c79d06464ba384b0721681da24.png]: https://img-blog.csdnimg.cn/aa4442c79d06464ba384b0721681da24.png
[https_www.acwing.com_problem_content_803]: https://www.acwing.com/problem/content/803/
[0026e450454449629be12050babe9e19.png]: https://img-blog.csdnimg.cn/0026e450454449629be12050babe9e19.png
[485b10109e8b44e294c6c487bfd0c148.png]: https://img-blog.csdnimg.cn/485b10109e8b44e294c6c487bfd0c148.png
[Link 1]: https://zhuanlan.zhihu.com/p/118432554