int comput(int tmpn)
{
int tmpc=0;
while(tmpn>0)
{
tmpc++;
tmpn=tmpn&(tmpn-1)
}
return tmpc;
}
x=x&(x-1)
==============
以前沒(méi)有見(jiàn)過(guò)這樣的表達(dá)式，分析一下發(fā)現(xiàn)發(fā)明這個(gè)表達(dá)式的人是個(gè)高手。
表達(dá)式的意思就是把x的二進(jìn)制表示從最低位直到遇到第一個(gè)1的比特置0。
例如：
e1:
x = 01001000
x-1 = 01000111
x&(x-1)=01000000
e2:
x = 01001001
x-1 = 01001000
x&(x-1)=01001000
位運(yùn)算里有學(xué)問(wèn)呀，
例如眾所周知的交換算法：
void swap(int i1, int i2)
{
i1 ^= i2;
i2 ^= i1;
i1 ^= i2;
}
還有，我今天看了Minix操作系統(tǒng)作者寫(xiě)的《操作系統(tǒng) 設(shè)計(jì)與實(shí)現(xiàn)》（寫(xiě)的比William Stalling的《操作系統(tǒng) 內(nèi)核與設(shè)計(jì)原理》有條理而且清晰緊湊得多，后者內(nèi)容蕪雜）中的頁(yè)面替換算法之一矩陣法，就是用位運(yùn)算實(shí)現(xiàn)的：
假設(shè)內(nèi)存分為n頁(yè)，那么高速緩存一個(gè)n x n的比特矩陣，開(kāi)始時(shí)全置0，如下(假設(shè)n=4)：
0 1 2 3
0 0 0 0 0
1 0 0 0 0
2 0 0 0 0
3 0 0 0 0
每次內(nèi)存訪問(wèn)時(shí)，如果訪問(wèn)的是i頁(yè)，那么先把矩陣的第i行置1，然后把矩陣的第i列置0，這樣i行的二進(jìn)制的值越小就表示i頁(yè)最長(zhǎng)時(shí)間最近沒(méi)有被訪問(wèn)。例如假設(shè)訪問(wèn)的次序?yàn)?-2-3-1，那么該矩陣的變化過(guò)程為：
0 1 2 3
0 0 1 1 1 0 1 0 1 0 1 1 0 0 0 1 0
1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1
2 0 0 0 0 1 1 0 1 1 1 0 0 1 0 0 0
3 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0
第三個(gè)例子是Windows GDI的二元和三元光柵操作的編碼。比較復(fù)雜，就不講了。
x=x&(x-1); 可以用來(lái)求出x是否為2冪次方數(shù)；當(dāng)&的結(jié)果為0時(shí)，x原值是2冪次方數(shù)，否則就不是2冪次方數(shù)；
如x=4時(shí) 4: 0000 0100
& 3：0000 0011
得出結(jié)果為0 ，是2冪次方數(shù)；
x=5時(shí)， 0000 0101
0000 0100
得出結(jié)果為1,即非2冪次方數(shù)；