C語(yǔ)言中位運(yùn)算的使用技巧

第第頁(yè)C語(yǔ)言中位運(yùn)算的使用技巧位運(yùn)算

程序中的所有數(shù)在計(jì)算機(jī)內(nèi)存中都是以二進(jìn)制的形式儲(chǔ)存的。位運(yùn)算就是直接對(duì)整數(shù)在內(nèi)存中的二進(jìn)制位進(jìn)行操作

位操作的優(yōu)勢(shì)

位運(yùn)算是一種底層的運(yùn)算，往往比普通的運(yùn)算要快上許多許多

位運(yùn)算是最高效而且占用內(nèi)存最少的（算法）操作，執(zhí)行效率非常高

位運(yùn)算操作的是二進(jìn)制數(shù)，會(huì)擁有一些二進(jìn)制的特性，在實(shí)際問(wèn)題可以方便運(yùn)用

位運(yùn)算只需較低的空間需求

位運(yùn)算使用能使程序變得更加簡(jiǎn)潔和優(yōu)美

位運(yùn)算可以表示一些狀態(tài)集合

運(yùn)算符號(hào)

下面的a和b都是整數(shù)類型，則：

含義（C語(yǔ)言）按位與areturn(n}

取余，(除數(shù)為2的n次方)

//得到余數(shù)intYu(intnum,intn){inti=1

指定二進(jìn)制位數(shù)截取

比如說(shuō)16位二進(jìn)制數(shù)A：1001100110011000，如果想獲A的哪一位的值，就把數(shù)字B：0000000000000000的那一位設(shè)置為1。

比如想獲得A的第三位就把B的第三位數(shù)字設(shè)置為1，則B為0000000000000100，設(shè)置完之后再把A、B求與，其結(jié)果若為0，說(shuō)明A的第三位為0，其結(jié)果為1，說(shuō)明A的第三位為1。

同理：若要獲得A的第五位，就把B設(shè)置為0000000000010000，之后再求與。

通常在程序中，數(shù)字B被稱為掩碼，其含義是專門(mén)用來(lái)測(cè)試某一位是否為0的數(shù)值。

統(tǒng)計(jì)二進(jìn)制中1的個(gè)數(shù)

利用x=xwhile(x){sum++;x=x}returnsum;}

or操作

生成組合編碼，進(jìn)行狀態(tài)壓縮

當(dāng)把二進(jìn)制當(dāng)作集合使用時(shí)，可以用or操作來(lái)增加元素。合并編碼在對(duì)字節(jié)碼進(jìn)行加密時(shí)，加密后的兩段bit需要重新合并成一個(gè)字節(jié)，這時(shí)就需要使用or操作。

求一個(gè)數(shù)的二進(jìn)制表達(dá)中0的個(gè)數(shù)

intGrial(intx){intcount=0;while(x+1){count++;x|=(x+1);}returncount;}

xor操作

兩個(gè)整數(shù)交換變量名

voidswap(intb^=a;a^=b;}

判斷兩個(gè)數(shù)是否異號(hào)

intx=-1,y=2;boolf=((x^y)

數(shù)據(jù)加密

將需要加密的內(nèi)容看做A，密鑰看做B，A^B=加密后的內(nèi)容C。而解密時(shí)只需要將C^密鑰B=原內(nèi)容A。如果沒(méi)有密鑰，就不能解密！

#include#include#include#defineKEY0x86intmain(){charp_data[16]={"HelloWorld!"};charEncrypt[16]={0},Decode[16]={0};inti;for(i=0;i

數(shù)字判重

利用了二進(jìn)制數(shù)的性質(zhì)：x^y^y=x。由此可見(jiàn)，當(dāng)同一個(gè)數(shù)累計(jì)進(jìn)行兩次xor操作，相當(dāng)于自行抵銷了，剩下的就是不重復(fù)的數(shù)

找出沒(méi)有重復(fù)的數(shù)

intfind(int[]arr){inttmp=arr[0];for(inti=1;i

not操作

交換符號(hào)

intreversal(inta){return~a+1;}

取絕對(duì)值（效率高）

n>>31取得n的符號(hào)

若n為正數(shù)，n>>31等于0

若n為負(fù)數(shù)，n>>31等于-1

若n為正數(shù)n^0=0，數(shù)不變

若n為負(fù)數(shù)，有n^-1需要計(jì)算n和-1的補(bǔ)碼，然后進(jìn)行異或運(yùn)算，結(jié)果n變符號(hào)并且為n的絕對(duì)值減1，再減去-1就是絕對(duì)值

intabs(intn){return(n^(n>>31))-(n>>31);}

也可以這樣使用

intabs(intn){inti=n>>31;returni==0?n:(~n+1);}

從低位到高位.將n的第m位置1

將1左移m-1位找到第m位，得到000...1...000，n在和這個(gè)數(shù)做或運(yùn)算

intsetBitToOne(intn,intm){returnn|(1

同理從低位到高位，將n的第m位置0，代碼如下

intsetBitToZero(intn,intm){returnn}

shl操作a=(a>>8)|(a

進(jìn)行二進(jìn)制逆序

unsignedshorta=34520;a=((aa=((aa=((aa=((a

獲得int型最大最小值

intgetMaxInt(){return(1

m的n次方

//自己重寫(xiě)的pow()方法intpow(intm,intn){intsum=1;while(n!=0){if(n}m*=m;n=n>>1;}returnsum;}

找出不大于N的最大的2的冪指數(shù)

intfindN(intn){n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8//整型一般是32位，上面我是假設(shè)8位。return(n+1)>>1;}

二分查找32位整數(shù)的前導(dǎo)0個(gè)數(shù)

intnlz(unsignedx){intn;if(x==0)return(32);n=1;if((x>>16)==0){n=n+16;x=x>24)==0){n=n+8;x=x>28)==0){n=n+4;x=x>30)==0){n=n+2;x=x>31);returnn;}

位圖的操作

將x的第n位置1，可以通過(guò)x|=(x

將x的第n位清0，可以通過(guò)x

取出x的第n位的值，可以通過(guò)(x>>n)

如下:

#defineclr_bit(x,n)((x)&=~(1>(n))&1)

綜合應(yīng)用

以下僅列出，感興趣可以參考下面鏈接：/~seander/bithacks.html

關(guān)于操作計(jì)數(shù)方法

計(jì)算整數(shù)的符號(hào)

（檢測(cè)）兩個(gè)整數(shù)是否具有相反的符號(hào)

計(jì)算無(wú)分支的整數(shù)絕對(duì)值（abs）

計(jì)算兩個(gè)整數(shù)的最小值（最小值）或最大值（最大值），而無(wú)需分支

確定整數(shù)是否為2的冪

標(biāo)志延伸

從恒定位寬擴(kuò)展的符號(hào)

從可變位寬擴(kuò)展的符號(hào)

通過(guò)3個(gè)操作從可變位寬擴(kuò)展符號(hào)有條件地設(shè)置或清除位而不分支

有條件地否定一個(gè)值而不分支

根據(jù)掩碼合并兩個(gè)值中的位

計(jì)數(shù)位設(shè)置

計(jì)數(shù)位設(shè)置，幼稚的方式

計(jì)算由查找表設(shè)置的位

數(shù)位集，BrianKernighan的方式

使用64位指令對(duì)14、24或32位字中設(shè)置的位進(jìn)行計(jì)數(shù)

并行設(shè)置計(jì)數(shù)位

從最高有效位到給定位置的計(jì)數(shù)位的設(shè)置（等級(jí)）

從給定的計(jì)數(shù)（等級(jí)）中選擇位位置（從最高有效位開(kāi)始）

計(jì)算奇偶校驗(yàn)（如果設(shè)置了奇數(shù)位數(shù)，則為1，否則為0）

天真地計(jì)算單詞的奇偶性

通過(guò)查找表計(jì)算奇偶校驗(yàn)

使用64位乘法和模數(shù)除法計(jì)算字節(jié)的奇偶校驗(yàn)

用乘法計(jì)算單詞的奇偶校驗(yàn)

并行計(jì)算奇偶校驗(yàn)

交換價(jià)值

用減法和加法交換值

用XOR交換值

用XOR交換單個(gè)位

反轉(zhuǎn)位序列

反轉(zhuǎn)位是顯而易見(jiàn)的方式

逐字查找表中的位反轉(zhuǎn)

通過(guò)3個(gè)操作（64位乘法和模數(shù)除法）反轉(zhuǎn)字節(jié)中的位

通過(guò)4個(gè)操作反轉(zhuǎn)字節(jié)中的位（64位乘法，無(wú)除法）

通過(guò)7個(gè)操作反轉(zhuǎn)字節(jié)中的位（無(wú)64位，僅32位）

與5*lg（N）個(gè)運(yùn)算并行地反轉(zhuǎn)N位數(shù)量

模數(shù)除法（又名計(jì)算余數(shù)）

在不進(jìn)行除法運(yùn)算的情況下，將模數(shù)除以1<<s（顯而易見(jiàn)）

在不進(jìn)行除法運(yùn)算的情況下以（1<<s）-1計(jì)算模數(shù)除法

不進(jìn)行除法運(yùn)算就并行計(jì)算（1<<s）-1的模數(shù)除法

查找整數(shù)的整數(shù)對(duì)數(shù)2（又稱最高位集的位置）

使用O（N）運(yùn)算找到MSBN設(shè)置為整數(shù)的對(duì)數(shù)2（顯而易見(jiàn)的方法）

查找具有64位IEEE浮點(diǎn)數(shù)的整數(shù)的整數(shù)對(duì)數(shù)2

使用查找表找到整數(shù)的對(duì)數(shù)2

在O（lg（N））運(yùn)算中找到N位整數(shù)的對(duì)數(shù)2

使用乘法和查找在O（lg（N））操作中找到N位整數(shù)的對(duì)數(shù)2

查找整數(shù)的對(duì)數(shù)以10為底的整數(shù)

查找整數(shù)的整數(shù)對(duì)數(shù)10

查找32位IEEE浮點(diǎn)數(shù)的整數(shù)對(duì)數(shù)基數(shù)2

查找32位IEEE浮點(diǎn)的pow（2，r）根的整數(shù)對(duì)數(shù)基數(shù)2（對(duì)于無(wú)符號(hào)整數(shù)r）

計(jì)算連續(xù)的尾隨零位（或查找位索引）

線性計(jì)算右邊的連續(xù)零位（后綴）

并行計(jì)算右側(cè)連續(xù)的零位（后綴）

通過(guò)二進(jìn)制搜索計(jì)算右邊連續(xù)的零位（跟蹤）

通過(guò)強(qiáng)制轉(zhuǎn)換為浮點(diǎn)數(shù)來(lái)計(jì)算右側(cè)連續(xù)的零位（跟蹤）

用模數(shù)除法和查找計(jì)算右邊連續(xù)的零位（跟蹤）

用乘法和查找計(jì)數(shù)右邊連續(xù)的零位（后跟）

通過(guò)浮法舍入到2的下一