位運算在算法設計及教學中的實際應用

張嘉宇

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

關鍵詞：位運算；算法設計；二進制；教學；高級語言

中圖分類號：TP312 文獻標識碼：A 文章編號：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

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

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

1 位運算實際應用

1.1 枚舉排列

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

與數組長度相等的二進制字串的每一位均可以與數組中的數字位置對應，且二進制數的每一位上非“0”即“1”，就如同在程序中的“0”和“1”一樣，每一位上的“0”和“1”分別代表了該數字的有無，再配合數組下標與字串位數的對應，便可以表達其排列狀況。使用一個簡單的實例來解釋位運算在排列問題中的應用。

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

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

public static void main（String[] args）

{List> result = new ArrayList（）；

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

int total = 1 << array.length；

//i就是000到111十進制表達

for（int i=0；i

{List list = new ArrayList（）；

int index = array.length-1；

int mid = i；

while（mid>0）

{//判斷i的二進制表達每位是否為1

if（（mid&1）==1）

{list.add（array[index]）；

}

index—；

mid >>= 1；

}

result.add（list）；

}}

1.2 內存優化

算法的實現經常會用到數組，棧以及列表等“數據容器”對大量數據進行存儲以及相應的處理。在內存中會為這些容器開辟一段邏輯上連續的空間來存儲容器中的數據。（內存會為運行中的程序分配空間來存放程序中函數方法以及變量。局部變量存放于內存中的棧區，靜態變量存放于數據區，創建的對象以及申請的臨時空間存放于堆區）。但是當遇到一些較為特殊的情況時，所需要保存的數據量過大，占用的內存空間也更多，甚至導致內存不足。

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

例2：所有的DNA是由一系列的核苷酸組成，簡稱A，C，G，T，例如。“ACGCCTTAA”。在研究DNA時，有時識別DNA中的重復序列十分有用。寫一個函數來找到所有在一個DNA分子中出現不止一次的10個核苷酸的DNA序列。

首先用0（00），1（01），2（10），3（11）來分別表示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；

}

然后利用位運算的內存優化，每十位核苷酸鏈可以用20位二進制碼來表示（一個int類型的數32位）將每十位核苷酸構成的整數作為鍵來保存在hash表中，將其出現次數作為鍵所對應的值，當其出現次數大于一時則放入結果集中。重點在于位操作的處理。key = （（key<<2）|getValue（s.charAt（i））） & 0xfffff就是得到每十位核苷酸所構成的整數，先將原序列向左移兩位這樣該序列的最后兩位均變為0與遍歷到的核苷酸所代表的二進制數進行相或處理，那么最后兩位就會變成最近遍歷到的核苷酸的二進制數，例如"...CG"，現在遍歷到G，原序列"...01"向左移兩位變為"...0100"，與G所代表的二進制"10"進行相或處理，得到新序列"...0110"，因為十位核苷酸只需要用20位二進制數來表示，所以還要用0xfffff（轉化為二進制就是前12位為0，后20位為一）與新生成的序列進行相與操作，將前12位都變為0就可以得到每十位核苷酸所構成的整數。核心代碼如下：

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 去同存異

在算法的編寫過程中，需要在一些關鍵的運行節點上面找到一些特殊的數據來作為繼續運行的判斷條件或者對已有的數據進行刪改。而特殊數據的特殊之處一般在于兩點：值與其他數據不一樣；出現的次數與其他數據不一樣。

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

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

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]++；

}}

//因為只有一個出現一次的數，所以count[i]%n只可能是0或1

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

}

2 實用技巧

2.1 判斷數據的奇偶性

if（（n&1） == 1）

{

System.out.println（"n為奇數"）；

}

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

2.2 判斷數據的符號是否相同

int i=-4；

int j=6；

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

if（isNeg）

System.out.println（"i，j同號"）；

else

System.out.println（"i，j異號"）；

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

2.3 移位符的使用

int i=4；

int j=6；

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

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

將一個數向左移相當于該數乘2，向右移相當于除2，例如上面的4（省略到只有四位0100），向左移一位，就變成了8（1000），而6（0110）向右移一位則變為了（0011）。由此可以推得向左移N位相當于將該數乘以2的N次方，向右移動N位相當于將該數除以2的N次方。

3 結論

本文從位運算的角度對算法問題進行了詳細的分析，對算法運行效率的提升以及對內存空間消耗的降低有了可觀的進步，以及在位運算教學時有了一個新的角度去借鑒。同時也介紹了實用的位運算的技巧，令算法的實現變得簡單快捷。

參考文獻：

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

[2] 馬麗娟.常用計算機算法簡介及C語言舉例[J].軟件設計開發，2010，6（11）：2655-2662.

[3] 鄢德英.程序設計語言中的變量和算法[J].西南民族學院學報，1990，16（4）：34-37.

[4] 吳萍，蒲鵬.朱麗娟.Java程序設計[M].北京：北方交通大學出版社，2006.

[5] 劉堅.編譯原理基礎[M].西安：西安電子科技大學出版社，2008.

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

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

[8] 包健，章復嘉.計算機組成原理與系統結構[M].北京：高等教育出版社，2009.