欢迎您访问365答案网,请分享给你的朋友!
生活常识 学习资料

【模板题】位运算

时间:2023-04-28
一、AcWing 801、二进制中1的个数

【题目描述】
给定一个长度为 n n n的数列,请你求出数列中每个数的二进制表示中 1 1 1的个数。

【输入格式】
第一行包含整数 n n n。
第二行包含 n n n个整数,表示整个数列。

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

【数据范围】
1 ≤ n ≤ 100000 1≤n≤100000 1≤n≤100000
0 ≤ 数 列 中 元 素 的 值 ≤ 1 0 9 0≤数列中元素的值≤10^9 0≤数列中元素的值≤109

【输入样例】

51 2 3 4 5

【输出样例】

1 1 2 1 2

【分析】


我们可以写一个 l o w b i t ( x ) lowbit(x) lowbit(x)函数返回 x x x的二进制中最低位的 1 1 1所表示的数,那么怎么实现这个功能呢?假设 x = ( 1100100 ) B x=(1100100)_B x=(1100100)B​,那么 − x = ( 0011011 ) B + 1 = ( 0011100 ) B -x=(0011011)_B+1=(0011100)_B −x=(0011011)B​+1=(0011100)B​,则 x & − x = ( 0000100 ) B x&-x=(0000100)_B x&−x=(0000100)B​,也就是 x x x的最低位 1 1 1所表示的数。然后回到本题,我们需要快速计算出某个数的二进制表示中有几个 1 1 1,那我们就可以循环每次将这个数 x x x减去 l o w b i t ( x ) lowbit(x) lowbit(x),也就是每次循环都把 x x x的最低位 1 1 1减去,每减一次答案加一,等这个数减为 0 0 0时答案就是这个数中 1 1 1的个数。


【代码】

#include using namespace std;int lowbit(int x){ return x & -x;}int main(){ int n; scanf("%d", &n); while (n--) { int x; scanf("%d", &x); int res = 0; //每次减去x的最后一位1 while (x) x -= lowbit(x), res++; printf("%d ", res); } return 0;}

Copyright © 2016-2020 www.365daan.com All Rights Reserved. 365答案网 版权所有 备案号:

部分内容来自互联网,版权归原作者所有,如有冒犯请联系我们,我们将在三个工作时内妥善处理。