11.2 位运算的具体应用
通过上一节的讲解,位运算的概念已经不陌生了,读者可能会有一个疑问,在实际工作中,位运算到底有什么用途?
其实,位运算主要用在算法和密码学方面居多,但算法或密码学这些分类对于通常的开发者来讲接触的并不会太深入,而且这两个分类也有一定的难度,并不好理解,所以这里不准备介绍位运算在算法或者密码学中的用途。本节中准备举一个好理解又常用的利用位运算解决实际问题的场景。
许多读者朋友都玩网络游戏,许多网络游戏为了刺激玩家每天上线,都在游戏中设有“每日任务”——每天让玩家做一些任务,如杀怪、采集来赚取积分、金钱、经验等。每日任务根据游戏不同,数量也不同,每日任务比较少的网络游戏中,可能每日任务只有几个,每日任务多的网络游戏,可能每日任务有几十个。
现在假设要做一款网络游戏,其中每日任务有10个,例如给好友送一次礼物、花金币购买一次物品、和其他玩家进行一次PK、杀死一个游戏中的怪等,都属于每日任务之一。现在的需求是:记录这10个任务是否完成,没完成的,用0表示,完成的,用1表示。
可能读者很快就能想到一个解决方法:定义10个变量,或者定义10个元素的整型数组,每个数组元素存一个任务标记0或者1:
试想,如果往数据库中记录该玩家的每日任务是否完成,是要记录10条数据,这显然很浪费数据库的存储空间。
针对这个问题,有两个前提条件先约定一下:
· 每日任务只有10个。
· 只需记录该任务是否完成:0(未完成)或者1(已完成)这两个状态之一。
由此,就想到了位运算。通过上一节学习,知道了一个unsignedint型数据有4字节,也就是32个二进制位,每个二进制位又都可以是0或者1,这样看来,只需要用一个unsignedint型变量,就可以记录多达32种状态,每个状态要么是0,要么是1。也就是说,其实只需要用一个unsigned int型变量,就能记录下每日这10个任务是否完成,甚至一个unsignedint型变量能记录多达32个每日任务是否完成(因为有32个二进制位),远远超过10个每日任务这个数量,这样,往数据库中保存玩家每日任务数据时,就只需要记录一条数据。
一个unsignedint型数据,一共32个位,最右边代表第1位,逐渐往左边来,最左边代表第32位,上一节讲解时曾说过,最左边的称为最高位,最右边的称为最低位,如图11.1所示。
图11.1 unsigned int一共32位(最右边是第1位,最左边是第32位)
现在每日任务只有10个,那么只需要使用其中的10位表示这10个任务是否做完就可以了,用0表示任务没做完,用1表示任务已经做完,用最右边的最低位表示第1个任务,然后依次往左,表示第2个任务,第3个任务……,一直到第10个任务,如图11.2所示。
图11.2 unsigned int一共32位(只使用最右边的10位)
这里需要写一些代码来做一些基本操作,要实现两个功能:
· 判断某个任务是否做完。
· 标记某个任务已经做完了。
下面要讲解一些前提代码,请注意看下面的代码:
分析一下这个带参数的宏定义,会得到如下结果:
· BIT(0)等价于(1≪(0)),代表1左移0位;
· BIT(1)等价于(1≪(1)),代表1左移1位;
· BIT(2)等价于(1≪(2)),代表1左移2位。
左移的概念上一节已经学过了,每左移一位相当于乘以2,所以,上面这个#define的功能就能够推测出来:
所以执行下面这段代码:
结果如图11.3所示。
看一下结果数字,这些数字是1、2、4、8、16、32、64、128、256、512,从表面看,可以观察到,每个数字都是前面的数字*2得到的。现在把这些数字变成二进制数再观察一下:
图11.3 宏定义BIT的一些输出结果
有了上面这些知识,就能判断某个任务是否做完了。定义一个无符号整型变量如下:
注意,这里给这个任务变量取名叫task,task变量一共32位长;如果想看第7个任务是否做完,怎么看呢?如果第7个位置是1,就说明第7个任务做完了;如果第7个位置是0,就说明第7个任务没做完,如图11.4所示。
图11.4 第7位设置为1,表示第7个任务已经完成
现在,问题的关键就是要把这第7个位置的数据提取出来。如何提取,就需要用到位运算。回忆一下上一节的按位与运算符“&”,如果两个相应的位都为1,则该位的结果为1,否则为0。回忆一下按位与的公式:
可以想象,如果把task与1000000(这是二进制数,第7位为1,其他位为0)做按位与运算,会出现什么结果?如果第7位为1,则结果肯定会如图11.5所示。
图11.5 第7位为1,与1000000做按位与运算得到的结果
那么,得到的结果描述如下:
如果task中(一共有32位)的第7位是0,那么task&1000000=0;如果第7位是1,那么task&1000000=1000000(二进制)=64(十进制)=BIT(6)。
所以,要判断某个任务是否做完,完整的判断代码应该这样写,这些代码具备商用价值,供读者参考和借鉴:
以上就判断出任务7做没做,核心代码就是这一句:if(task&ETask7)。
接着思考,如果任务7没做,如何把任务7做了,也就是让任务7这个位置标记上1?这就用到了按位或运算符“|”,参加运算的两个运算量,如果两个相应的位有一个为1,则该位的结果为1,否则为0。回忆一下按位或的公式:
所以,如果把task与1000000(这是二进制数,第7位为1,其他位为0)做按位或运算,会出现什么结果呢?结果就是其他位都不变,但是第7位肯定变为1(不管原来是什么);把第7位标记为1,就起到了标记任务7做完了的目的。所以代码继续完善如下:
这里,总结一下:
通过按位与操作来判断某个二进制位是否被标记为1,通过按位或操作将某个二进制位标记为1,然后,就可以把上面的task变量中的内容保存到数据库里,下次该玩家再上线,再把这个内容从数据库中取出,就能判断该玩家的某个任务是否做过,做过的话就可以有一些其他的处理,如不让他再重复做了。
上面这个范例,就是通过位操作的方法,把原本需要10个变量(数字)记录10个任务是否完成缩减成了用一个unsignedint类型变量来记录,一下子就节省了9个变量,这就是位运算在实际工作中的主要用途之一。