1) int型變量循環(huán)左移k次，即a=a < <k |a>>16-k (設(shè)sizeof(int)=16)
(2) int型變量a循環(huán)右移k次，即a=a>>k |a < <16-k (設(shè)sizeof(int)=16)
(3)整數(shù)的平均值
對(duì)于兩個(gè)整數(shù)x,y，如果用 (x+y)/2 求平均值，會(huì)產(chǎn)生溢出，因?yàn)?x+y 可能會(huì)大于INT_MAX，但是我們知道它們的平均值是肯定不會(huì)溢出的，我們用如下算法：
int average(int x, int y) //返回X,Y 的平均值
{
return (x&y)+((x^y)>>1);
}
(4)判斷一個(gè)整數(shù)是不是2的冪,對(duì)于一個(gè)數(shù) x >= 0，判斷他是不是2的冪
boolean power2(int x)
{
return ((x&(x-1))==0)&&(x!=0)；
}
(5)不用temp交換兩個(gè)整數(shù)
void swap(int x , int y)
{
x ^= y;
y ^= x;
x ^= y;
}
(6)計(jì)算絕對(duì)值
int abs( int x )
{
int y ;
y = x >> 31 ;
return (x^y)-y ; //or: (x+y)^y
}
(7)取模運(yùn)算轉(zhuǎn)化成位運(yùn)算 (在不產(chǎn)生溢出的情況下)
a % (2^n) 等價(jià)于 a & (2^n - 1)
(8)乘法運(yùn)算轉(zhuǎn)化成位運(yùn)算 (在不產(chǎn)生溢出的情況下)
a * (2^n) 等價(jià)于 a < < n
(9)除法運(yùn)算轉(zhuǎn)化成位運(yùn)算 (在不產(chǎn)生溢出的情況下)
a / (2^n) 等價(jià)于 a>> n
例: 12/8 == 12>>3
(10) a % 2 等價(jià)于 a & 1
(11) if (x == a) x= b;
else x= a;
等價(jià)于 x= a ^ b ^ x;
(12) x 的 相反數(shù) 表示為 (~x+1)
(13)求從x位（高）到y(tǒng)位（低）間共有多少個(gè)1
public static int FindChessNum(int x, int y, ushort k)
{
int re = 0;
for (int i = y; i <= x; i++)
{
re += ((k >> (i - 1)) & 1);
}
return re;
}
(14)
/*將32位數(shù)分解為4個(gè)8位數(shù)處理后再合成32位數(shù)返回*/
DWORD GetDW(DWORD dw)
{
DWORD dwRet=0;
if (dw!=0)
{
BYTE b1=(dw>>24)&0xff,b2=(dw>>16)&0xff,b3=(dw>>8)&0xff,b4=dw&0xff;
//分別處理 b1,b2,b3,b4
dwRet=b1;
dwRet=(dwRet<<8)+b2;
dwRet=(dwRet<<8)+b3;
dwRet=(dwRet<<8)+b4;
return dwRet;
}
else{
return 0;
}
}
檢測(cè)一個(gè)無(wú)符號(hào)數(shù)是不為2^n-1(^為冪)： x&(x+1)
將最右側(cè)0位改為1位： x | (x+1)
二進(jìn)制補(bǔ)碼運(yùn)算公式：
-x = ~x + 1 = ~(x-1)
~x = -x-1
-(~x) = x+1
~(-x) = x-1
x+y = x - ~y - 1 = (x|y)+(x&y)
x-y = x + ~y + 1 = (x|~y)-(~x&y)
x^y = (x|y)-(x&y)
x|y = (x&~y)+y
x&y = (~x|y)-~x
x==y: ~(x-y|y-x)
x!=y: x-y|y-x
x< y: (x-y)^((x^y)&((x-y)^x))
x<=y: (x|~y)&((x^y)|~(y-x))
x< y: (~x&y)|((~x|y)&(x-y))//無(wú)符號(hào)x,y比較
x<=y: (~x|y)&((x^y)|~(y-x))//無(wú)符號(hào)x,y比較
使用位運(yùn)算的無(wú)分支代碼：
計(jì)算絕對(duì)值
int abs( int x )
{
int y ;
y = x >> 31 ;
return (x^y)-y ;//or: (x+y)^y
}
符號(hào)函數(shù)：sign(x) = -1, x<0; 0, x == 0 ; 1, x > 0
int sign(int x)
{
return (x>>31) | (unsigned(-x))>>31 ;//x=-2^31時(shí)失敗(^為冪)
}
三值比較：cmp(x,y) = -1, x<y; 0, x==y; 1, x > y
int cmp( int x, int y )
{
return (x>y)-(x-y) ;
}
doz=x-y, x>=y; 0, x<y
int doz(int x, int y )
{
int d ;
d = x-y ;
return d & ((~(d^((x^y)&(d^x))))>>31) ;
}
int max(int x, int y )
{
int m ;
m = (x-y)>>31 ;
return y & m | x & ~m ;
}
不使用第三方交換x,y:
1.x ^= y ; y ^= x ; x ^= y ;
2.x = x+y ; y = x-y ; x = x-y ;
3.x = x-y ; y = y+x ; x = y-x ;
4.x = y-x ; x = y-x ; x = x+y ;
雙值交換:x = a, x==b; b, x==a//常規(guī)編碼為x = x==a ? b :a ;
1.x = a+b-x ;
2.x = a^b^x ;
下舍入到2的k次方的倍數(shù):
1.x & ((-1)<<k)
2.(((unsigned)x)>>k)<<k
上舍入：
1. t = (1<<k)-1 ; x = (x+t)&~t ;
2.t = (-1)<<k ; x = (x-t-1)&t ;
位計(jì)數(shù),統(tǒng)計(jì)1位的數(shù)量：
1.
int pop(unsigned x)
{
x = x-((x>>1)&0x55555555) ;
x = (x&0x33333333) + ((x>>2) & 0x33333333 ) ;
x = (x+(x>>4)) & 0x0f0f0f0f ;
x = x + (x>>8) ;
x = x + (x>>16) ;
return x & 0x0000003f ;
}
2.
int pop(unsigned x) {
static char table[256] = { 0,1,1,2, 1,2,2,3, ...., 6,7,7,8 } ;
return table[x&0xff]+table[(x>>8)&0xff]+table[(x>>16)&0xff]+table[(x>>24)] ;
}
奇偶性計(jì)算:
x = x ^ ( x>>1 ) ;
x = x ^ ( x>>2 ) ;
x = x ^ ( x>>4 ) ;
x = x ^ ( x>>8 ) ;
x = x ^ ( x>>16 ) ;
結(jié)果中位于x最低位，對(duì)無(wú)符號(hào)x,結(jié)果的第i位是原數(shù)第i位到最左側(cè)位的奇偶性
位反轉(zhuǎn)：
unsigned rev(unsigned x)
{
x = (x & 0x55555555) << 1 | (x>>1) & 0x55555555 ;
x = (x & 0x33333333) << 2 | (x>>2) & 0x33333333 ;
x = (x & 0x0f0f0f0f) << 4 | (x>>4) & 0x0f0f0f0f ;
x = (x<<24) | ((x&0xff00)<<8) | ((x>>8) & 0xff00) | (x>>24) ;
return x ;
}
遞增位反轉(zhuǎn)后的數(shù)：
unsigned inc_r(unsigned x)
{
unsigned m = 0x80000000 ;
x ^= m ;
if( (int)x >= 0 )
do { m >>= 1 ; x ^= m ; } while( x < m ) ;
return x ;
}
混選位：
abcd efgh ijkl mnop ABCD EFGH IJKL MNOP->aAbB cCdD eEfF gGhH iIjJ kKlL mMnN oOpP
unsigned ps(unsigned x)
{
unsigned t ;
t = (x ^ (x>>8)) & 0x0000ff00; x = x ^ t ^ (t<<8) ;
t = (x ^ (x>>4)) & 0x00f000f0; x = x ^ t ^ (t<<4) ;
t = (x ^ (x>>2)) & 0x0c0c0c0c; x = x ^ t ^ (t<<2) ;
t = (x ^ (x>>1)) & 0x22222222; x = x ^ t ^ (t<<1) ;
return x ;
}
位壓縮：
選擇并右移字x中對(duì)應(yīng)于掩碼m的1位的位,如：compress(abcdefgh,01010101)=0000bdfh
compress_left(x,m)操作與此類似，但結(jié)果位在左邊: bdfh0000.
unsigned compress(unsigned x, unsigned m)
{
unsigned mk, mp, mv, t ;
int i ;
x &= m ;
mk = ~m << 1 ;
for( i = 0 ; i < 5 ; ++i ) {
mp = mk ^ ( mk << 1) ;
mp ^= ( mp << 2 ) ;
mp ^= ( mp << 4 ) ;
mp ^= ( mp << 8 ) ;
mp ^= ( mp << 16 ) ;
mv = mp & m ;
m = m ^ mv | (mv >> (1<<i) ) ;
t = x & mv ;
x = x ^ t | ( t >> ( 1<<i) ) ;
mk = mk & ~mp ;
}
return x ;
}
位置換：
用32個(gè)5位數(shù)表示從最低位開(kāi)始的位的目標(biāo)位置，結(jié)果是一個(gè)32*5的位矩陣，
將該矩陣沿次對(duì)角線轉(zhuǎn)置后用5個(gè)32位字p[5]存放。
SAG(x,m) = compress_left(x,m) | compress(x,~m) ;
準(zhǔn)備工作：
void init( unsigned *p ) {
p[1] = SAG( p[1], p[0] ) ;
p[2] = SAG( SAG( p[2], p[0]), p[1] ) ;
p[3] = SAG( SAG( SAG( p[3], p[0] ), p[1]), p[2] ) ;
p[4] = SAG( SAG( SAG( SAG( p[4], p[0] ), p[1]) ,p[2]), p[3] ) ;
}
實(shí)際置換：
int rep( unsigned x ) {
x = SAG(x,p[0]);
x = SAG(x,p[1]);
x = SAG(x,p[2]);
x = SAG(x,p[3]);
x = SAG(x,p[4]);
return x ;
}
二進(jìn)制碼到GRAY碼的轉(zhuǎn)換:
unsigned B2G(unsigned B )
{
return B ^ (B>>1) ;
}
GRAY碼到二進(jìn)制碼:
unsigned G2B(unsigned G)
{
unsigned B ;
B = G ^ (G>>1) ;
B = G ^ (G>>2) ;
B = G ^ (G>>4) ;
B = G ^ (G>>8) ;
B = G ^ (G>>16) ;
return B ;
}
找出最左0字節(jié)的位置:
int zbytel( unsigned x )
{
static cahr table[16] = { 4,3,2,2, 1,1,1,1, 0,0,0,0, 0,0,0,0 } ;
unsigned y ;
y = (x&0x7f7f7f7f) + 0x7f7f7f7f ;
y = ~(y|x|0x7f7f7f7f) ;
return table[y*0x00204081 >> 28] ;//乘法可用移位和加完成
}
C\C++支持比較低階的位運(yùn)算，在是眾人皆知的了。每本C\C++的教科書(shū)都會(huì)說(shuō)到這部分的內(nèi)容，不過(guò)都很簡(jiǎn)略，我想會(huì)有很多人不知道位運(yùn)算用在什么地方。這個(gè)帖子就簡(jiǎn)略說(shuō)說(shuō)位運(yùn)算的用處，更進(jìn)一步的用法要大家自己去體會(huì)。而主要說(shuō)的是操作標(biāo)志值方面。
/****************************************/
#define BTI_MSK(bit) (1 << (bit))
#define BIT_SET(x,bit) ((x) |= BTI_MSK (bit))
#define BIT_CLR(x,bit) ((x) &= ~BTI_MSK (bit))
#define BIT_TST(x,bit) ((x) & BTI_MSK (bit))
/****************************************/
考慮一個(gè)事物、一個(gè)系統(tǒng)、或者一個(gè)程序可能會(huì)出現(xiàn)一種或者幾種狀態(tài)。為了在不同的狀態(tài)下，作出不同的行為，你可以設(shè)立一些標(biāo)志值，再根據(jù)標(biāo)志值來(lái)做判斷。比如C++的文件流，你就可以設(shè)定一些標(biāo)志值，ios::app, ios::ate, ios::binary, ios::in, ios::out, ios::trunc，并且可以將它用|組合起來(lái)創(chuàng)建一個(gè)恰當(dāng)?shù)奈募鳌Ｄ憧赡軙?huì)將這些標(biāo)志值定義為bool類型，不過(guò)這樣要是設(shè)置的標(biāo)志值一多，就會(huì)很浪費(fèi)空間。
而假如定義一個(gè)整型數(shù)值，unsigned int flags; 在現(xiàn)在的系統(tǒng)，flags應(yīng)該是32位, 用1,2,3....32將位進(jìn)行編號(hào)，我們可以進(jìn)行這樣的判斷, 當(dāng)位1取1時(shí)，表示用讀方式打開(kāi)文件，當(dāng)位2取1時(shí)，表示用寫(xiě)方式打開(kāi)文件，當(dāng)位3取1時(shí)，用二進(jìn)制方式打開(kāi)文件....因?yàn)閒lags有32位，就可以設(shè)置32個(gè)不同的狀態(tài)值，也相當(dāng)于32個(gè)bool類型。這樣一方面省了空間, 另一方面也多了個(gè)好處，就是如前面所說(shuō)的，可以將標(biāo)志值組合起來(lái)。
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
好啦，上面有點(diǎn)不清不楚的。下面看看到底怎么操作這些標(biāo)志值。
設(shè)想C++的類ios這樣定義, 其實(shí)沒(méi)有這個(gè)類，只有ios_basic類，typedef basic_ios<char> ios;
class ios
{
public:
enum { app = 0x0001, ate = 0x0002, binary = 0x0004,
in = 0x0008, out = 0x0010, trunc = 0x0020 };
....
private:
unsigned int flags;
};
注意上面enum語(yǔ)句中，每一個(gè)數(shù)值只有1位是1，其余是0，這個(gè)很重要，你可以將它化成2進(jìn)制看看。
現(xiàn)在將flags相應(yīng)的位設(shè)置為1, 可以這樣做 flags |= app。這個(gè)等于flags = flags | app, 為什么呢? app只有1位是1，其余是0，因?yàn)? | 1 = 0， 0 | 0 = 0， 這樣0對(duì)應(yīng)的位是不變的。而1 | 1 = 1, 1 | 0 = 1, 1對(duì)應(yīng)的位不論原來(lái)是什么狀態(tài)，都一定為1。如果想要將幾個(gè)位都設(shè)置為1，可以這樣做 flags |= (app | ate | binary)。因?yàn)槊總€(gè)enum常數(shù)各有一位為1, 與運(yùn)算之后就有3位為1，就如上面的分析，就可以將那3位都設(shè)置為1, 其余位不變。這個(gè)就是標(biāo)志可以組合起來(lái)用的原因。也可以用+組合起來(lái)，原因在于(下面的數(shù)字是2進(jìn)制)0001 + 0010 + 0100 = 0111 跟與運(yùn)算結(jié)果一樣。不過(guò)不提倡用+, 考慮(app | ate | binary)要是我不小心寫(xiě)多了個(gè)標(biāo)志值，(app | ate | ate | binary)結(jié)果還是正確的，如果用+的話，就會(huì)產(chǎn)生進(jìn)位，結(jié)果就會(huì)錯(cuò)誤。通常我們不知道原先已經(jīng)組合了多少個(gè)標(biāo)志值了，用或運(yùn)算會(huì)安全。
現(xiàn)在將flags對(duì)應(yīng)的位設(shè)置為0, 可以這樣做 flags &= ~app。相當(dāng)于 flags = flags & (~app). app取反之后，只有1位是0，其余是1，做與運(yùn)算之后，1對(duì)應(yīng)的位并不會(huì)改變，0對(duì)應(yīng)的為不管原來(lái)是1是0，都肯定為0，這樣就將對(duì)應(yīng)的位設(shè)置了0。同樣同時(shí)設(shè)置幾個(gè)標(biāo)志位可以這樣做，flags &= ~(app | ate | binary)。
現(xiàn)在將flags對(duì)應(yīng)的位，如果是1就變成0，如果是0就變成1，可以這樣做 flags ^= app。同時(shí)設(shè)置幾個(gè)標(biāo)志位可以寫(xiě)成 flags ^= (app | ate | binary)。不再做分析了，不然就太羅嗦了。不過(guò)也給大家一個(gè)例子，你查查Ascii表，會(huì)發(fā)現(xiàn)對(duì)應(yīng)的大小寫(xiě)字母是相差倒數(shù)第6位，可以用這樣的函數(shù)統(tǒng)一的將大寫(xiě)變成小寫(xiě)，小寫(xiě)變成大寫(xiě)。
void xchgUppLow(string& letters)
{
const unsigned int mask = (1<<5);
for (size_t i=0; i<letters.length(); i++)
letters[i] ^= mask;
}
前提是輸入的string一定要全是字母, 而要想是操作字母，可以在原來(lái)基礎(chǔ)上加個(gè)判斷。
好啦，上面已經(jīng)可以設(shè)置flags的對(duì)應(yīng)位值了，要是判斷呢？可以這樣寫(xiě) if (flags & app) 這樣可以判斷對(duì)應(yīng)的位值是否為1, 因?yàn)镃\C++語(yǔ)言中非0就真。app只有一位是1，其余是0，如果, flags的對(duì)應(yīng)位也是0，在與操作下就得到結(jié)果0，反之非0，這樣就可以判斷標(biāo)志位了。
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
上面關(guān)于標(biāo)志值的操作就介紹完畢。其實(shí)在C++中已經(jīng)有了個(gè)bitset了，沒(méi)有必要去自己進(jìn)行低階的位運(yùn)算，上面的四個(gè)操作在bitset中分別叫做set, reset, flip, test。不過(guò)在C中，這樣的代碼還很常見(jiàn), 反正知道多點(diǎn)也沒(méi)有壞處。
用 windows API 編程，你也經(jīng)常會(huì)碰到這樣的標(biāo)志值，要互相組合，可以用|, 也可以用+(只是建議用|，理由上面說(shuō)了). 它的標(biāo)志值也是這樣定義的，不過(guò)用#define
#define WS_BORDER 0x0001
#define WS_CAPTION 0x0002
......
當(dāng)初我就是想不明白為什么可以用|或者用+來(lái)組合，現(xiàn)在知道了。
(注：上面出現(xiàn)的數(shù)字是我自己作的，到底實(shí)際怎么定義其實(shí)沒(méi)有關(guān)系，只要保證只有一位是1，其余是0就可以的了. 因?yàn)榫幊痰臅r(shí)候用的是常量值，沒(méi)有人這樣笨去直接用數(shù)值的)
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
其實(shí)，位運(yùn)算還有很多用處。比如移位相當(dāng)于乘除2的冪數(shù)(不過(guò)通常編譯器也將乘除2的冪數(shù)優(yōu)化成匯編的移位指令，所以沒(méi)有必要不要這樣賣弄了。匯編的移位指令有兩組，分別針對(duì)有符號(hào)和無(wú)符號(hào)的, 我猜想在C\C++的同一移位運(yùn)算針對(duì)有符號(hào)整數(shù)和無(wú)符號(hào)整數(shù)的不同，會(huì)根據(jù)情況編譯成不同的匯編移位指令，不過(guò)沒(méi)有去證實(shí)), 其實(shí)移位更用得多的地方是去構(gòu)造一個(gè)掩碼, 比如上面的mask = (1<<5);
還有&運(yùn)算，有時(shí)候可以用來(lái)求余數(shù)。比如 value & (1<<4 - 1) 這相當(dāng)于將value的高位全變成0了，效果等于 value % 8.
還有值得一提的是^運(yùn)算，它有個(gè)很特殊的性質(zhì)。比如 A ^= B, 變成另一個(gè)數(shù)，跟著再執(zhí)行A ^= B，又變回原來(lái)的數(shù)了，不信你可以列真值表或者化簡(jiǎn)邏輯式看看。就因?yàn)檫@個(gè)性質(zhì)，^有很多用途。比如加密，你將原文看成A, 用同一個(gè)B異或一次，就相當(dāng)于加密，跟著在用B異或一次，相當(dāng)于解密。不過(guò)這樣是很容易破解就是了。要是一個(gè)B不夠，還可以加個(gè)C, 比如A ^= B, A ^= C, A ^= C, A ^= B, 恢復(fù)原狀。
下面一個(gè)小程序，用異或交換兩個(gè)數(shù)字。
int x = 3;
int y = 4;
x ^= y;
y ^= x;
x ^= y;
其實(shí)何止交換數(shù)字，連交換對(duì)象也可以的
template <typename T>
void swap(T& obj1, T& obj2)
{
const int sizeOfObj = sizeof(T);
char* pt1 = (char*)&obj1;
char* pt2 = (char*)&obj2;
for (size_t i=0; i<sizeOfObj; i++)
{
pt1[i] ^= pt2[i];
pt2[i] ^= pt1[i];
pt1[i] ^= pt2[i];
}
}
還有異或操作還可以用在圖象的光柵操作。我們知道，顏色也是用二進(jìn)制來(lái)表示的，對(duì)顏色進(jìn)行不同的位運(yùn)算，就可以得到不同的光柵。因?yàn)楫惢虻奶厥庑再|(zhì)，我們用異或操作的光柵畫(huà)了副圖，跟著再在原來(lái)的地方畫(huà)一次，那副圖就刷除了。這樣可以用來(lái)顯示動(dòng)畫(huà)而不用保存原來(lái)的畫(huà)像信息。以前我寫(xiě)過(guò)個(gè)雙人的貪食蛇，就用了異或光柵。因?yàn)楸尘吧前咨模簿褪侨?，作A ^ 1 = A, 所以用畫(huà)刷畫(huà)一次是畫(huà)了設(shè)定的顏色，再畫(huà)一次就恢復(fù)。最有趣的是兩蛇相交的時(shí)候，顏色也會(huì)作異或疊加，產(chǎn)生一種新的顏色了，離開(kāi)的時(shí)候也會(huì)自動(dòng)恢復(fù)。
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
好啦，夠長(zhǎng)了，就停止吧。在最后再給大家一段代碼，是用來(lái)看看對(duì)象在內(nèi)存中的位值的。可以看看。
string bitsOfUChar(unsigned char c)
{
const int numOfBitsInUChar = 8;
unsigned int mask = (1<<7);
string result(8, '0');
for (size_t i=0; i<numOfBitsInUChar; i++)
{
if ( mask & c)
result[i] = '1';
mask >>= 1;
}
return result;
}
template <typename T>
string bitsInMemory(const T& obj)
{
int sizeOfObj = sizeof(obj);
unsigned char* pt = (unsigned char*)&obj;
string result;
for (size_t i=0; i<sizeOfObj; i++)
{
result += bitsOfUChar(pt[i]);
result += ' ';
}
return result;
}
比如bitsInMemory(12)，會(huì)輸出00001100 00000000 00000000 00000000, 我就知道我自己的機(jī)器是小尾順序的了。