一、基础算法7:位运算 模板题+算法模板(二进制中1的个数)
文章目录
算法模板
求n的第k位数字
n >> k & 1
返回n的最后一位1
lowbit(n) = n & -n
求一个数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/
题目
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的二进制并按位输出
关于原码,反码,补码
参考文章:原码、反码、补码