位运算在算法设计及教学中的实际应用

张嘉宇

摘要：现代数字计算机只能对由“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循环来枚举各种可能出现的情况。可是由于递归算法本身的特性，需要不断调用自身函数，每调用一次函数便需要在内存中为函数分配空间用于保存函数中的返回结果，变量以及传入的实参，所以使用递归算法虽然可以得到最后的结果，却会浪费大量的时间和内存空间。而利用位运算中二进制位的特性可以高效地解决该类问题。

与数组长度相等的二进制字串的每一位均可以与数组中的数字位置对应，且二进制数的每一位上非“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.