位運(yùn)算在算法設(shè)計(jì)及教學(xué)中的實(shí)際應(yīng)用

張嘉宇

摘要：現(xiàn)代數(shù)字計(jì)算機(jī)只能對(duì)由“0”和“1”所組成的二進(jìn)制形式的數(shù)據(jù)進(jìn)行識(shí)別和處理，任何使用高級(jí)語(yǔ)言所編寫的程序都需要先被編譯為機(jī)器指令之后才能真正被計(jì)算機(jī)所執(zhí)行。由此可見高級(jí)語(yǔ)言所編寫的程序和二進(jìn)制之間有著千絲萬(wàn)縷的關(guān)系，因此幾乎每一種高級(jí)語(yǔ)言都提供了對(duì)程序中的數(shù)據(jù)在內(nèi)存中所保存的二進(jìn)制字串進(jìn)行直接操作的運(yùn)算符，即位運(yùn)算符。位運(yùn)算看似并不復(fù)雜，實(shí)則用途十分廣泛，在程序中適當(dāng)使用位運(yùn)算可以提高程序運(yùn)行效率以及節(jié)省大量?jī)?nèi)存空間。該文使用JAVA這門高級(jí)編程語(yǔ)言介紹了位運(yùn)算在算法實(shí)現(xiàn)中的實(shí)際應(yīng)用以及實(shí)用技巧。希望通過該文對(duì)算法設(shè)計(jì)中效率的提升以及二進(jìn)制教學(xué)有借鑒意義。

關(guān)鍵詞：位運(yùn)算；算法設(shè)計(jì)；二進(jìn)制；教學(xué)；高級(jí)語(yǔ)言

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）04-0098-03

The Practical Application of Bit Arithmetic in Algorithm Design and Education

ZHANG Jia-yu

（School of Software，Shanxi Agricultural University， Taigu 030801，China）

Abstract：The modern digital computer can only be identified and processed by the binary data consisting of the number 0 and 1， and any programs written in high-level languages can only be executed by the computers after being compiled into machine instructions. Programs written in high-levellanguages， therefore， can be cluttered with the binary system. So almost each high-level language provides operator ─ bit operator， directly operating on the binary string， kept in memory. Bit arithmetic may not seem complicated. However， in fact， it is widely used， and the proper use of bit arithmetic in the program can be more effective and save lots of memories. This paper， using the high-level programming language of JAVA ， introduces the practical application and practical skills of bit arithmeticin the algorithm implementation. It is hopeful that this paper can help to improve the efficiency of algorithm design and education of binary.

Key words：bit arithmetic；algorithm design；binary system；education；high-level programming language

計(jì)算機(jī)運(yùn)算模式以二進(jìn)制為基礎(chǔ)。所以不論是數(shù)據(jù)在內(nèi)存中的存儲(chǔ)形式，還是計(jì)算機(jī)處理數(shù)據(jù)時(shí)所執(zhí)行的機(jī)器指令都是由“0”和“1”組成的二進(jìn)制字串。位運(yùn)算從本質(zhì)上面來(lái)講是就對(duì)數(shù)據(jù)在內(nèi)存中所保存二進(jìn)制字串進(jìn)行直接操作，避免了十進(jìn)制轉(zhuǎn)化為二進(jìn)制之后再進(jìn)行運(yùn)算的過程，所以使用位運(yùn)算來(lái)處理數(shù)據(jù)會(huì)大大提高程序的運(yùn)行效率。對(duì)于一些對(duì)時(shí)間復(fù)雜度或空間復(fù)雜度要求較高的算法來(lái)說(shuō)，在實(shí)現(xiàn)算法的過程之中使用位運(yùn)算可以很便捷迅速的解決問題。在高級(jí)編程語(yǔ)言中一般都會(huì)提供：“按位與”，“按位或”，“按位取反”，“異或”，“右移位”，“左移位”以上六種位運(yùn)算符，這六種運(yùn)算符之間的優(yōu)先級(jí)以及具體使用方法詳見表1。

不過值得注意的是位運(yùn)算所處理的數(shù)據(jù)類型只能是整型數(shù)據(jù)（包括int，char，short，long等），并且在高級(jí)編程語(yǔ)言中相較于其他運(yùn)算符號(hào)，位運(yùn)算符的優(yōu)先級(jí)較低，所以在實(shí)現(xiàn)算法的過程之中存在多種運(yùn)算符時(shí)，要添加括號(hào)確保位運(yùn)算的優(yōu)先執(zhí)行。

1 位運(yùn)算實(shí)際應(yīng)用

1.1 枚舉排列

排列問題是很多算法的實(shí)現(xiàn)過程之中的重要組成部分，也是現(xiàn)實(shí)生活中難免會(huì)遇到的問題。例如，給定一組數(shù)據(jù)以及一個(gè)特定的公式或限制條件，要找到這組數(shù)據(jù)中所有符合這個(gè)公式或條件的數(shù)據(jù)組合情況。此類問題的基礎(chǔ)方法均是找到所有的排列情況再根據(jù)所給出的公式以及限制條件篩選出正確的排列組合。 在實(shí)現(xiàn)算法的時(shí)候，最普遍的思想便是利用遞歸以及for循環(huán)來(lái)枚舉各種可能出現(xiàn)的情況。可是由于遞歸算法本身的特性，需要不斷調(diào)用自身函數(shù)，每調(diào)用一次函數(shù)便需要在內(nèi)存中為函數(shù)分配空間用于保存函數(shù)中的返回結(jié)果，變量以及傳入的實(shí)參，所以使用遞歸算法雖然可以得到最后的結(jié)果，卻會(huì)浪費(fèi)大量的時(shí)間和內(nèi)存空間。而利用位運(yùn)算中二進(jìn)制位的特性可以高效地解決該類問題。

與數(shù)組長(zhǎng)度相等的二進(jìn)制字串的每一位均可以與數(shù)組中的數(shù)字位置對(duì)應(yīng)，且二進(jìn)制數(shù)的每一位上非“0”即“1”，就如同在程序中的“0”和“1”一樣，每一位上的“0”和“1”分別代表了該數(shù)字的有無(wú)，再配合數(shù)組下標(biāo)與字串位數(shù)的對(duì)應(yīng)，便可以表達(dá)其排列狀況。使用一個(gè)簡(jiǎn)單的實(shí)例來(lái)解釋位運(yùn)算在排列問題中的應(yīng)用。

例1：給定一組整數(shù)，返回其所有可能的子集。

數(shù)組的子集均可以看為一個(gè)二進(jìn)制字串，字串上某一位為“1”則代表該子集中含有與該位對(duì)應(yīng)的數(shù)組中的數(shù)，為“0”則反之。例如以一個(gè)數(shù)組[1，2，3]為例：“101”代表子集[1，3]；“010”代表子集[2]。一個(gè)含有N個(gè)元素的數(shù)組一共有2^N個(gè)子集，而N位全“0”的二進(jìn)制數(shù)到N位全“1”的二進(jìn)制數(shù)之間的2^N個(gè)二進(jìn)制數(shù)恰好和數(shù)組子集一一對(duì)應(yīng)，所以遍歷這些二進(jìn)制字串，然后將每個(gè)二進(jìn)制串中的為“1”的位找到，再將該位對(duì)應(yīng)的數(shù)放入相應(yīng)子集即可以得到所有子集，而不需要過多的內(nèi)存空間和運(yùn)行時(shí)間。相應(yīng)關(guān)鍵代碼實(shí)現(xiàn)如下：

public static void main（String[] args）

{List> result = new ArrayList（）；

int array[] = {1，2，3}；

int total = 1 << array.length；

//i就是000到111十進(jìn)制表達(dá)

for（int i=0；i

{List list = new ArrayList（）；

int index = array.length-1；

int mid = i；

while（mid>0）

{//判斷i的二進(jìn)制表達(dá)每位是否為1

if（（mid&1）==1）

{list.add（array[index]）；

}

index—；

mid >>= 1；

}

result.add（list）；

}}

1.2 內(nèi)存優(yōu)化

算法的實(shí)現(xiàn)經(jīng)常會(huì)用到數(shù)組，棧以及列表等“數(shù)據(jù)容器”對(duì)大量數(shù)據(jù)進(jìn)行存儲(chǔ)以及相應(yīng)的處理。在內(nèi)存中會(huì)為這些容器開辟一段邏輯上連續(xù)的空間來(lái)存儲(chǔ)容器中的數(shù)據(jù)。（內(nèi)存會(huì)為運(yùn)行中的程序分配空間來(lái)存放程序中函數(shù)方法以及變量。局部變量存放于內(nèi)存中的棧區(qū)，靜態(tài)變量存放于數(shù)據(jù)區(qū)，創(chuàng)建的對(duì)象以及申請(qǐng)的臨時(shí)空間存放于堆區(qū)）。但是當(dāng)遇到一些較為特殊的情況時(shí)，所需要保存的數(shù)據(jù)量過大，占用的內(nèi)存空間也更多，甚至導(dǎo)致內(nèi)存不足。

使用二進(jìn)制字串作為數(shù)據(jù)的容器可以大大減小內(nèi)存的開銷，完成對(duì)內(nèi)存的優(yōu)化：使用二進(jìn)制中的N位來(lái)表示一個(gè)數(shù)據(jù)，而M個(gè)數(shù)據(jù)只需要MxN位的字串即可取代一個(gè)傳統(tǒng)的“數(shù)據(jù)容器”。若MxN小于等于32，那么用一個(gè)int類型的數(shù)據(jù)即可存儲(chǔ)數(shù)據(jù)，若MxN小于64，則使用long類型數(shù)據(jù)來(lái)存儲(chǔ)數(shù)據(jù)。例如數(shù)組[1，4，7，3]便可以使用一個(gè)整數(shù)827（001/100/111/011）來(lái)表示。下面使用一個(gè)例子來(lái)詳細(xì)解釋位運(yùn)算在內(nèi)存優(yōu)化方面的應(yīng)用。

例2：所有的DNA是由一系列的核苷酸組成，簡(jiǎn)稱A，C，G，T，例如?！癆CGCCTTAA”。在研究DNA時(shí)，有時(shí)識(shí)別DNA中的重復(fù)序列十分有用。寫一個(gè)函數(shù)來(lái)找到所有在一個(gè)DNA分子中出現(xiàn)不止一次的10個(gè)核苷酸的DNA序列。

首先用0（00），1（01），2（10），3（11）來(lái)分別表示ACGT四種核苷酸，示例代碼如下：

public static int getValue（char c）

{if（c=='A'）

return 0；

if（c=='C'）

return 1；

if（c=='G'）

return 2；

if（c=='T'）

return 3；

return 4；

}

然后利用位運(yùn)算的內(nèi)存優(yōu)化，每十位核苷酸鏈可以用20位二進(jìn)制碼來(lái)表示（一個(gè)int類型的數(shù)32位）將每十位核苷酸構(gòu)成的整數(shù)作為鍵來(lái)保存在hash表中，將其出現(xiàn)次數(shù)作為鍵所對(duì)應(yīng)的值，當(dāng)其出現(xiàn)次數(shù)大于一時(shí)則放入結(jié)果集中。重點(diǎn)在于位操作的處理。key = （（key<<2）|getValue（s.charAt（i））） & 0xfffff就是得到每十位核苷酸所構(gòu)成的整數(shù)，先將原序列向左移兩位這樣該序列的最后兩位均變?yōu)?與遍歷到的核苷酸所代表的二進(jìn)制數(shù)進(jìn)行相或處理，那么最后兩位就會(huì)變成最近遍歷到的核苷酸的二進(jìn)制數(shù)，例如"...CG"，現(xiàn)在遍歷到G，原序列"...01"向左移兩位變?yōu)?...0100"，與G所代表的二進(jìn)制"10"進(jìn)行相或處理，得到新序列"...0110"，因?yàn)槭缓塑账嶂恍枰?0位二進(jìn)制數(shù)來(lái)表示，所以還要用0xfffff（轉(zhuǎn)化為二進(jìn)制就是前12位為0，后20位為一）與新生成的序列進(jìn)行相與操作，將前12位都變?yōu)?就可以得到每十位核苷酸所構(gòu)成的整數(shù)。核心代碼如下：

public List solve（String s）

{List result = new ArrayList（）；

HashMap map = new HashMap（）；

int key = 0；

for（int i=0；i

{key = （（key<<2）|getValue（s.charAt（i））） & 0xfffff；

if（i>=9）

{if（map.get（key）==null）

{map.put（key，1）；

}

else

{if（map.get（key）==1）

{

result.add（s.substring（i-9，i+1））；

map.put（key，Integer.MAX_VALUE）；

}}}}

return result；

}

1.3 去同存異

在算法的編寫過程中，需要在一些關(guān)鍵的運(yùn)行節(jié)點(diǎn)上面找到一些特殊的數(shù)據(jù)來(lái)作為繼續(xù)運(yùn)行的判斷條件或者對(duì)已有的數(shù)據(jù)進(jìn)行刪改。而特殊數(shù)據(jù)的特殊之處一般在于兩點(diǎn)：值與其他數(shù)據(jù)不一樣；出現(xiàn)的次數(shù)與其他數(shù)據(jù)不一樣。

值與其他數(shù)據(jù)不一樣的情況只需要一個(gè)for循環(huán)找到不同的值即可。在程序中找到出現(xiàn)的次數(shù)與其他數(shù)據(jù)不一樣這種類型的的特殊的值以一般的思路來(lái)講，創(chuàng)建一個(gè)hash表，將數(shù)組中的數(shù)字設(shè)為鍵，將出現(xiàn)次數(shù)設(shè)為值，在遍歷完所有元素之后將值與其他值不一樣的鍵找出便找到了該特殊值，該算法時(shí)間復(fù)雜度為O（n）。利用位運(yùn)算本身的高效性可以更加快速地求解答案。

假定有一個(gè)number數(shù)組，其中除了一個(gè)數(shù)出現(xiàn)一次之外，其余數(shù)均出現(xiàn)了n次，找出這個(gè)特殊的數(shù)。用一個(gè)大小為32的count數(shù)組來(lái)保存number數(shù)組中所有整數(shù)轉(zhuǎn)化為二進(jìn)制之后i位上1的個(gè)數(shù)，如果說(shuō)所有數(shù)據(jù)均出現(xiàn)n次，那么count數(shù)組各位上的值一定是n，現(xiàn)在有一個(gè)只出現(xiàn)一次的數(shù)，那么這個(gè)數(shù)的出現(xiàn)會(huì)導(dǎo)致count數(shù)組有些位上的值不是n，找到這些位就可以還原只出現(xiàn)一次的數(shù)。算法的時(shí)間復(fù)雜度為O（32n），依舊為線性復(fù)雜度。核心代碼如下：

int count[] = new int[32]；

int result = 0；

for（int i=0；i<32；i++）

{for（int j=0；j

{

if（（（number[j]>>i）&1）==1）

{count[i]++；

}}

//因?yàn)橹挥幸粋€(gè)出現(xiàn)一次的數(shù)，所以count[i]%n只可能是0或1

result = result|（（count[i]%n）<

}

2 實(shí)用技巧

2.1 判斷數(shù)據(jù)的奇偶性

if（（n&1） == 1）

{

System.out.println（"n為奇數(shù)"）；

}

n&1是n和1做"按位與"運(yùn)算，1的二進(jìn)制只有末位是1，所以n&1就是只保留n的末位（二進(jìn)制）.n&1就表示了n的奇偶性.n若為偶數(shù)，其二進(jìn)制表示最后一位一定為0，所以與1相與得0，而奇數(shù)則相反，其二進(jìn)制最后一位一定為1，所以與1相與得1，這樣就可以判斷一個(gè)數(shù)的奇偶性，而不是使用%2的方法來(lái)判斷，效率更加高。

2.2 判斷數(shù)據(jù)的符號(hào)是否相同

int i=-4；

int j=6；

boolean isNeg = （i^j）>>>31 == 0；

if（isNeg）

System.out.println（"i，j同號(hào)"）；

else

System.out.println（"i，j異號(hào)"）；

異或的規(guī)則是同0異1，通常和>>>（無(wú)符號(hào)右移）搭配使用，>>表示有符號(hào)右移，如果該數(shù)為正，則高位補(bǔ)0，若為負(fù)數(shù)，則高位補(bǔ)1；>>>表示無(wú)符號(hào)右移，也叫邏輯右移，即若該數(shù)為正，則高位補(bǔ)0，而若該數(shù)為負(fù)數(shù)，則右移后高位同樣補(bǔ)0。int類型32位，無(wú)符號(hào)右移31位則只剩下符號(hào)位，進(jìn)行異或便可知道兩數(shù)是不是同號(hào)。而且這樣寫最大的好處是不需要考慮數(shù)值越界的問題。

2.3 移位符的使用

int i=4；

int j=6；

System.out.println（i<<1）；

System.out.println（j>>1）；

將一個(gè)數(shù)向左移相當(dāng)于該數(shù)乘2，向右移相當(dāng)于除2，例如上面的4（省略到只有四位0100），向左移一位，就變成了8（1000），而6（0110）向右移一位則變?yōu)榱耍?011）。由此可以推得向左移N位相當(dāng)于將該數(shù)乘以2的N次方，向右移動(dòng)N位相當(dāng)于將該數(shù)除以2的N次方。

3 結(jié)論

本文從位運(yùn)算的角度對(duì)算法問題進(jìn)行了詳細(xì)的分析，對(duì)算法運(yùn)行效率的提升以及對(duì)內(nèi)存空間消耗的降低有了可觀的進(jìn)步，以及在位運(yùn)算教學(xué)時(shí)有了一個(gè)新的角度去借鑒。同時(shí)也介紹了實(shí)用的位運(yùn)算的技巧，令算法的實(shí)現(xiàn)變得簡(jiǎn)單快捷。

參考文獻(xiàn)：

[1] 周嵐.C語(yǔ)言中位運(yùn)算鮮為人知的事[J].軟件工程師，2014，17（5）：20-21.

[2] 馬麗娟.常用計(jì)算機(jī)算法簡(jiǎn)介及C語(yǔ)言舉例[J].軟件設(shè)計(jì)開發(fā)，2010，6（11）：2655-2662.

[3] 鄢德英.程序設(shè)計(jì)語(yǔ)言中的變量和算法[J].西南民族學(xué)院學(xué)報(bào)，1990，16（4）：34-37.

[4] 吳萍，蒲鵬.朱麗娟.Java程序設(shè)計(jì)[M].北京：北方交通大學(xué)出版社，2006.

[5] 劉堅(jiān).編譯原理基礎(chǔ)[M].西安：西安電子科技大學(xué)出版社，2008.

[6] 蔣立源，康慕寧.編譯原理第三版[M].西安.西北工業(yè)大學(xué)出版社，2005.

[7] 鮑家元，毛文林.數(shù)字邏輯[M].北京：高等教育出版社，2011.

[8] 包健，章復(fù)嘉.計(jì)算機(jī)組成原理與系統(tǒng)結(jié)構(gòu)[M].北京：高等教育出版社，2009.