位運(yùn)算

位運(yùn)算最常用的操作是將一個(gè)整數(shù)n的二進(jìn)制表示中第k位數(shù)字是幾。

這種時(shí)候，一般先將第k位移到最后一位，即n>>k。（n右移k,將第k位移動(dòng)成個(gè)位）

然后再看看個(gè)位數(shù)是幾，即x&1。（從命令的角度講,是將x的每一bit(2進(jìn)制中的1和0都占一個(gè)bit)與0001的每一bit做與運(yùn)算."&"是"與運(yùn)算"的意思,1&1=1,其他情況(1&0,0&1,0&0)都=0.從邏輯的角度來講,這個(gè)命令就是取x的最右邊一位.例如x是0011,x&1得到0001,如果x是0110,x&1得到0000。簡(jiǎn)單來說就是，x&1的如果要為真，則x的二進(jìn)制的2的0次方位一定要為1）

因此，求n的第k位數(shù)字即為 n >> k & 1

此外，位運(yùn)算中，通常需要一個(gè)樹狀數(shù)組的通用操作，lowbit()。

lowbit()函數(shù)，用于二進(jìn)制的形式下返回 x 的最后一位 1 ()。

實(shí)現(xiàn)原理 ：-x = ~x + 1。

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

~x+1 后，后面所有取反后的 1 會(huì)從最后一個(gè)1開始向前進(jìn)位且該位的數(shù)變?yōu)?0(即恢復(fù)原位)直至進(jìn)位到原數(shù)最后一個(gè) 1 取反后的 0 處停止向前進(jìn)位(也相當(dāng)于恢復(fù)原位)。

簡(jiǎn)單來說，~x + 1 后的數(shù)除了原數(shù)最后一個(gè)1的位置和原數(shù)一樣都為1， 其余的1的位置全都保留取反后的情況，即為0。

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

lowbit的效果基本如下：

x=10010,lowbit(x)=10;

x=1001000,lowbit(x)=1000;

二進(jìn)制中1的個(gè)數(shù)

給定一個(gè)長(zhǎng)度為?n?的數(shù)列，請(qǐng)你求出數(shù)列中每個(gè)數(shù)的二進(jìn)制表示中?1?的個(gè)數(shù)。

輸入格式

第一行包含整數(shù)?n。

第二行包含?n?個(gè)整數(shù)，表示整個(gè)數(shù)列。

輸出格式

共一行，包含?n?個(gè)整數(shù)，其中的第?i?個(gè)數(shù)表示數(shù)列中的第?i?個(gè)數(shù)的二進(jìn)制表示中?1?的個(gè)數(shù)。

二進(jìn)制中1的個(gè)數(shù)思路

1.需要一個(gè)lowbit函數(shù)返回 x & -x。

2.x 每次減去二進(jìn)制中最后一個(gè) 1（循環(huán)結(jié)束后減去的次數(shù)就為 x 的二進(jìn)制中 1 的個(gè)數(shù)），并計(jì)數(shù)。

大概，應(yīng)該算了解這一部分了。