位运算
这里就记录一下y总讲的位运算
就只有二进制的最后一位还有lowbit~
更难的二进制状态压缩先不写在这里~
什么超级无敌大水文
求整数n的二进制的第k位
这里的k指的是从右往左开始的0base的第k位
要取出第k位分两步
- 先把第k位移到第0位，即n >> k
- 取出最后一位的值 x & 1
合并以上两步有了 n >> k & 1取出整数n的二进制的第k位
int n = 10;for (int k = 3; k >= 0; k -- )
{cout << (n >> k & 1);
}
// 输出 1010
lowbit运算
树状数组的基本操作
作用：返回x的最后一位的1及后面的0对应的整数
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的个数
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 的最后一位 1cout << ans << ' ';}return 0;
}