1) int型變量循環左移k次，即a=a < <k |a>>16-k (設sizeof(int)=16)
(2) int型變量a循環右移k次，即a=a>>k |a < <16-k (設sizeof(int)=16)
(3)整數的平均值
對于兩個整數x,y，如果用 (x+y)/2 求平均值，會產生溢出，因為 x+y 可能會大于INT_MAX，但是我們知道它們的平均值是肯定不會溢出的，我們用如下算法：
int average(int x, int y) //返回X,Y 的平均值
{
return (x&y)+((x^y)>>1);
}
(4)判斷一個整數是不是2的冪,對于一個數 x >= 0，判斷他是不是2的冪
boolean power2(int x)
{
return ((x&(x-1))==0)&&(x!=0)；
}
(5)不用temp交換兩個整數
void swap(int x , int y)
{
x ^= y;
y ^= x;
x ^= y;
}
(6)計算絕對值
int abs( int x )
{
int y ;
y = x >> 31 ;
return (x^y)-y ; //or: (x+y)^y
}
(7)取模運算轉化成位運算 (在不產生溢出的情況下)
a % (2^n) 等價于 a & (2^n - 1)
(8)乘法運算轉化成位運算 (在不產生溢出的情況下)
a * (2^n) 等價于 a < < n
(9)除法運算轉化成位運算 (在不產生溢出的情況下)
a / (2^n) 等價于 a>> n
例: 12/8 == 12>>3
(10) a % 2 等價于 a & 1
(11) if (x == a) x= b;
else x= a;
等價于 x= a ^ b ^ x;
(12) x 的 相反數 表示為 (~x+1)
(13)求從x位（高）到y位（低）間共有多少個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位數分解為4個8位數處理后再合成32位數返回*/
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;
}
}
檢測一個無符號數是不為2^n-1(^為冪)： x&(x+1)
將最右側0位改為1位： x | (x+1)
二進制補碼運算公式：
-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))//無符號x,y比較
x<=y: (~x|y)&((x^y)|~(y-x))//無符號x,y比較
使用位運算的無分支代碼：
計算絕對值
int abs( int x )
{
int y ;
y = x >> 31 ;
return (x^y)-y ;//or: (x+y)^y
}
符號函數：sign(x) = -1, x<0; 0, x == 0 ; 1, x > 0
int sign(int x)
{
return (x>>31) | (unsigned(-x))>>31 ;//x=-2^31時失敗(^為冪)
}
三值比較：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//常規編碼為x = x==a ? b :a ;
1.x = a+b-x ;
2.x = a^b^x ;
下舍入到2的k次方的倍數:
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 ;
位計數,統計1位的數量：
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)] ;
}
奇偶性計算:
x = x ^ ( x>>1 ) ;
x = x ^ ( x>>2 ) ;
x = x ^ ( x>>4 ) ;
x = x ^ ( x>>8 ) ;
x = x ^ ( x>>16 ) ;
結果中位于x最低位，對無符號x,結果的第i位是原數第i位到最左側位的奇偶性
位反轉：
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 ;
}
遞增位反轉后的數：
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中對應于掩碼m的1位的位,如：compress(abcdefgh,01010101)=0000bdfh
compress_left(x,m)操作與此類似，但結果位在左邊: 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個5位數表示從最低位開始的位的目標位置，結果是一個32*5的位矩陣，
將該矩陣沿次對角線轉置后用5個32位字p[5]存放。
SAG(x,m) = compress_left(x,m) | compress(x,~m) ;
準備工作：
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] ) ;
}
實際置換：
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 ;
}
二進制碼到GRAY碼的轉換:
unsigned B2G(unsigned B )
{
return B ^ (B>>1) ;
}
GRAY碼到二進制碼:
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字節的位置:
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++支持比較低階的位運算，在是眾人皆知的了。每本C\C++的教科書都會說到這部分的內容，不過都很簡略，我想會有很多人不知道位運算用在什么地方。這個帖子就簡略說說位運算的用處，更進一步的用法要大家自己去體會。而主要說的是操作標志值方面。
/****************************************/
#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))
/****************************************/
考慮一個事物、一個系統、或者一個程序可能會出現一種或者幾種狀態。為了在不同的狀態下，作出不同的行為，你可以設立一些標志值，再根據標志值來做判斷。比如C++的文件流，你就可以設定一些標志值，ios::app, ios::ate, ios::binary, ios::in, ios::out, ios::trunc，并且可以將它用|組合起來創建一個恰當的文件流。你可能會將這些標志值定義為bool類型，不過這樣要是設置的標志值一多，就會很浪費空間。
而假如定義一個整型數值，unsigned int flags; 在現在的系統，flags應該是32位, 用1,2,3....32將位進行編號，我們可以進行這樣的判斷, 當位1取1時，表示用讀方式打開文件，當位2取1時，表示用寫方式打開文件，當位3取1時，用二進制方式打開文件....因為flags有32位，就可以設置32個不同的狀態值，也相當于32個bool類型。這樣一方面省了空間, 另一方面也多了個好處，就是如前面所說的，可以將標志值組合起來。
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
好啦，上面有點不清不楚的。下面看看到底怎么操作這些標志值。
設想C++的類ios這樣定義, 其實沒有這個類，只有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語句中，每一個數值只有1位是1，其余是0，這個很重要，你可以將它化成2進制看看。
現在將flags相應的位設置為1, 可以這樣做 flags |= app。這個等于flags = flags | app, 為什么呢? app只有1位是1，其余是0，因為0 | 1 = 0， 0 | 0 = 0， 這樣0對應的位是不變的。而1 | 1 = 1, 1 | 0 = 1, 1對應的位不論原來是什么狀態，都一定為1。如果想要將幾個位都設置為1，可以這樣做 flags |= (app | ate | binary)。因為每個enum常數各有一位為1, 與運算之后就有3位為1，就如上面的分析，就可以將那3位都設置為1, 其余位不變。這個就是標志可以組合起來用的原因。也可以用+組合起來，原因在于(下面的數字是2進制)0001 + 0010 + 0100 = 0111 跟與運算結果一樣。不過不提倡用+, 考慮(app | ate | binary)要是我不小心寫多了個標志值，(app | ate | ate | binary)結果還是正確的，如果用+的話，就會產生進位，結果就會錯誤。通常我們不知道原先已經組合了多少個標志值了，用或運算會安全。
現在將flags對應的位設置為0, 可以這樣做 flags &= ~app。相當于 flags = flags & (~app). app取反之后，只有1位是0，其余是1，做與運算之后，1對應的位并不會改變，0對應的為不管原來是1是0，都肯定為0，這樣就將對應的位設置了0。同樣同時設置幾個標志位可以這樣做，flags &= ~(app | ate | binary)。
現在將flags對應的位，如果是1就變成0，如果是0就變成1，可以這樣做 flags ^= app。同時設置幾個標志位可以寫成 flags ^= (app | ate | binary)。不再做分析了，不然就太羅嗦了。不過也給大家一個例子，你查查Ascii表，會發現對應的大小寫字母是相差倒數第6位，可以用這樣的函數統一的將大寫變成小寫，小寫變成大寫。
void xchgUppLow(string& letters)
{
const unsigned int mask = (1<<5);
for (size_t i=0; i<letters.length(); i++)
letters[i] ^= mask;
}
前提是輸入的string一定要全是字母, 而要想是操作字母，可以在原來基礎上加個判斷。
好啦，上面已經可以設置flags的對應位值了，要是判斷呢？可以這樣寫 if (flags & app) 這樣可以判斷對應的位值是否為1, 因為C\C++語言中非0就真。app只有一位是1，其余是0，如果, flags的對應位也是0，在與操作下就得到結果0，反之非0，這樣就可以判斷標志位了。
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
上面關于標志值的操作就介紹完畢。其實在C++中已經有了個bitset了，沒有必要去自己進行低階的位運算，上面的四個操作在bitset中分別叫做set, reset, flip, test。不過在C中，這樣的代碼還很常見, 反正知道多點也沒有壞處。
用 windows API 編程，你也經常會碰到這樣的標志值，要互相組合，可以用|, 也可以用+(只是建議用|，理由上面說了). 它的標志值也是這樣定義的，不過用#define
#define WS_BORDER 0x0001
#define WS_CAPTION 0x0002
......
當初我就是想不明白為什么可以用|或者用+來組合，現在知道了。
(注：上面出現的數字是我自己作的，到底實際怎么定義其實沒有關系，只要保證只有一位是1，其余是0就可以的了. 因為編程的時候用的是常量值，沒有人這樣笨去直接用數值的)
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
其實，位運算還有很多用處。比如移位相當于乘除2的冪數(不過通常編譯器也將乘除2的冪數優化成匯編的移位指令，所以沒有必要不要這樣賣弄了。匯編的移位指令有兩組，分別針對有符號和無符號的, 我猜想在C\C++的同一移位運算針對有符號整數和無符號整數的不同，會根據情況編譯成不同的匯編移位指令，不過沒有去證實), 其實移位更用得多的地方是去構造一個掩碼, 比如上面的mask = (1<<5);
還有&運算，有時候可以用來求余數。比如 value & (1<<4 - 1) 這相當于將value的高位全變成0了，效果等于 value % 8.
還有值得一提的是^運算，它有個很特殊的性質。比如 A ^= B, 變成另一個數，跟著再執行A ^= B，又變回原來的數了，不信你可以列真值表或者化簡邏輯式看看。就因為這個性質，^有很多用途。比如加密，你將原文看成A, 用同一個B異或一次，就相當于加密，跟著在用B異或一次，相當于解密。不過這樣是很容易破解就是了。要是一個B不夠，還可以加個C, 比如A ^= B, A ^= C, A ^= C, A ^= B, 恢復原狀。
下面一個小程序，用異或交換兩個數字。
int x = 3;
int y = 4;
x ^= y;
y ^= x;
x ^= y;
其實何止交換數字，連交換對象也可以的
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];
}
}
還有異或操作還可以用在圖象的光柵操作。我們知道，顏色也是用二進制來表示的，對顏色進行不同的位運算，就可以得到不同的光柵。因為異或的特殊性質，我們用異或操作的光柵畫了副圖，跟著再在原來的地方畫一次，那副圖就刷除了。這樣可以用來顯示動畫而不用保存原來的畫像信息。以前我寫過個雙人的貪食蛇，就用了異或光柵。因為背景色是白色的，也就是全1，作A ^ 1 = A, 所以用畫刷畫一次是畫了設定的顏色，再畫一次就恢復。最有趣的是兩蛇相交的時候，顏色也會作異或疊加，產生一種新的顏色了，離開的時候也會自動恢復。
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
好啦，夠長了，就停止吧。在最后再給大家一段代碼，是用來看看對象在內存中的位值的?？梢钥纯?。
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)，會輸出00001100 00000000 00000000 00000000, 我就知道我自己的機器是小尾順序的了。