这里就记录一下y总讲的位运算
就只有二进制的最后一位还有lowbit~
更难的二进制状态压缩先不写在这里~什么超级无敌大水文
求整数n的二进制的第k位
这里的k指的是从右往左开始的0base的第k位
要取出第k位分两步
- 先把第k位移到第0位，即n >> k
- 取出最后一位的值 x & 1
合并以上两步有了 n >> k & 1取出整数n的二进制的第k位
C++
int n = 10;
for (int k = 3; k >= 0; k -- )
{
cout << (n >> k & 1);
}
// 输出 1010lowbit运算
是还没有学过的树状数组的基本操作（虽然现在还不知道什么是树状数组）
作用：返回x的最后一位的1
e.g. lowbit(1010) = 10
e.g. lowbit(10101000) = 1000
实现：x & -x
原理：x & -x = x & (~ x + 1)
e.g.
x = 1010...0001000...000 ①
~x = 0101...1110111...111 ②
~x+1 = 0101...1111000...000 ③
x&-x = 0000...0001000...000 ① & ③应用：统计 x 中 1 的个数
思想：每次减去最后一个1
题目：二进制中1的个数
C++
int lowbit(int x)
{
return x & ~x;
}
int main()
{
int n; cin >> n;
while (n -- )
{
int x; cin >> x;
int ans = 0;
while (x) x -= lowbit(x),ans ++ ;// 每次减去 x 的最后一位 1
cout << ans << ' ';
}
return 0;
}
评论（0）
暂无评论