版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎ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的下一
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 證券市場(chǎng)資產(chǎn)證券化業(yè)務(wù)考核試卷
- 染整工藝在戶外服裝面料中的應(yīng)用考核試卷
- 石材開(kāi)采與加工技術(shù)培訓(xùn)班考核試卷
- 聚合纖維在環(huán)境保護(hù)領(lǐng)域的應(yīng)用考核試卷
- 糖果的工廠參觀與體驗(yàn)營(yíng)銷考核試卷
- 建筑工程用機(jī)械設(shè)備的故障預(yù)測(cè)與維護(hù)策略考核試卷
- 玻璃行業(yè)的人力資源培訓(xùn)與發(fā)展考核試卷
- 液壓系統(tǒng)在輻射環(huán)境中的作用考核試卷
- 人教版四上美術(shù)每一課教學(xué)反思簡(jiǎn)短
- 保護(hù)衣領(lǐng)用衣領(lǐng)墊項(xiàng)目可行性實(shí)施報(bào)告
- 期中測(cè)試卷(1-4單元)(試題)-2024-2025學(xué)年四年級(jí)上冊(cè)數(shù)學(xué)人教版
- 月考測(cè)試卷(第1~3單元)(試題)-2024-2025學(xué)年六年級(jí)上冊(cè)數(shù)學(xué)人教版
- 湖北省武漢海淀外國(guó)語(yǔ)實(shí)驗(yàn)學(xué)校2024-2025學(xué)年九年級(jí)上學(xué)期9月英語(yǔ)月考試題
- 質(zhì)監(jiān)系統(tǒng)國(guó)家質(zhì)檢中心命名規(guī)范
- 智慧林業(yè)綜合管理平臺(tái)解決方案
- 2024年4月至2008年10月自考03708中國(guó)近現(xiàn)代史綱要?dú)v年試題及答案含解析30套
- GB/T 44500-2024新能源汽車運(yùn)行安全性能檢驗(yàn)規(guī)程
- 2025屆高考語(yǔ)文復(fù)習(xí):鑒賞詩(shī)歌的表達(dá)技巧+導(dǎo)學(xué)案
- 2024至2030年中國(guó)全域旅游行業(yè)前景預(yù)測(cè)與“十四五”企業(yè)戰(zhàn)略規(guī)劃研究報(bào)告
- 2024屆中國(guó)誠(chéng)通控股集團(tuán)限公司校園招聘高頻考題難、易錯(cuò)點(diǎn)模擬試題(共500題)附帶答案詳解
- 2025屆高考語(yǔ)文一輪復(fù)習(xí)備考指導(dǎo)++課件
評(píng)論
0/150
提交評(píng)論