基础算法7：位运算

位运算

这里就记录一下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;
}