赞
踩
基本思想
主要运用:
求n 的二进制表示中第k为数字: n >> k & 1
1.先把第k位移到最后一位 n>>k
2.看这个位置是几 x & 1
求返回n 的最后一位1:lowbit(n)= n & -n = n &(~n + 1) 例如:n = 10101000 lowbit(n) = 1000
(lowbit) O(nlogn)O(nlogn)
使用lowbit操作,进行,每次lowbit操作截取一个数字最后一个1后面的所有位,每次减去lowbit得到的数字,直到数字减到0,就得到了最终1的个数,
lowbit原理
根据计算机负数表示的特点,如一个数字原码是10001000,他的负数表示形势是补码,就是反码+1,反码是01110111,加一则是01111000,二者按位与得到了1000,就是我们想要的lowbit操作
基本模板来自yxc
求n的第k位数字: n >> k & 1
返回n的最后一位1:lowbit(n) = n & -n
经典例题
AcWing 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; int lowbit(int x)//返回x的最后一位1; 每次减去lowbit(x), 计算减了多少次即x含有多少个1 { return x & -x; } int main() { int n; cin >> n; while(n--) { int x; cin >> x; int res = 0; while(x) x-= lowbit(x), res++;//当x不为零 每次减去x的最后一位1 减去的次数为1的个数 cout << res << ' '; } return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。