【编程笔记】位运算·二进制中1的个数

位运算

位运算最常用的操作是将一个整数n的二进制表示中第k位数字是几。

这种时候，一般先将第k位移到最后一位，即n>>k。（n右移k,将第k位移动成个位）

然后再看看个位数是几，即x&1。（从命令的角度讲,是将x的每一bit(2进制中的1和0都占一个bit)与0001的每一bit做与运算."&"是"与运算"的意思,1&1=1,其他情况(1&0,0&1,0&0)都=0.从逻辑的角度来讲,这个命令就是取x的最右边一位.例如x是0011,x&1得到0001,如果x是0110,x&1得到0000。简单来说就是，x&1的如果要为真，则x的二进制的2的0次方位一定要为1）

因此，求n的第k位数字即为 n >> k & 1

此外，位运算中，通常需要一个树状数组的通用操作，lowbit()。

lowbit()函数，用于二进制的形式下返回 x 的最后一位 1 ()。

实现原理 ：-x = ~x + 1。

~x代表的意思是按位取反的意思。将x按位取反，比如x = 10101010b。那么~x = 01010101b，~x+1 = 01010110b；比如x = 10101011b。那么~x = 01010100b，~x+1 = 01010101b；

~x+1 后，后面所有取反后的 1 会从最后一个1开始向前进位且该位的数变为 0(即恢复原位)直至进位到原数最后一个 1 取反后的 0 处停止向前进位(也相当于恢复原位)。

简单来说，~x + 1 后的数除了原数最后一个1的位置和原数一样都为1， 其余的1的位置全都保留取反后的情况，即为0。

最后 x & -x 的值就是 x 的最后一位1所形成的值（x & -x = x & (~x + 1)）。

lowbit的效果基本如下：

x=10010,lowbit(x)=10;

x=1001000,lowbit(x)=1000;

二进制中1的个数

给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 1 的个数。

输入格式

第一行包含整数 n。

第二行包含 n 个整数，表示整个数列。

输出格式

共一行，包含 n 个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。

二进制中1的个数思路

1.需要一个lowbit函数返回 x & -x。

2.x 每次减去二进制中最后一个 1（循环结束后减去的次数就为 x 的二进制中 1 的个数），并计数。

大概，应该算了解这一部分了。