汇编语言位向量(位映射)

< 上一页OR指令 XOR指令下一页 >

有些应用控制的对象是从一个有限全集中选出来的一组项目。就像公司里的雇员,或者气象监测站的环境读数。在这些情景中,二进制位可以代表集合成员。

Java HashSet 用指针或引用指向容器内对象不同,应用可以用位向量(或位映射)把一个二进制数中的位映射为数组中的对象。

如下例所示,二进制数的位从左边 0 号开始,到右边 31 号为止,该数表示了数组元素 0、1、2 和 31 是名为 SetX 的集合成员:

SetX = 10000000 00000000 00000000 00000111

(为了提供可读性,字节已经分开。)通过在特定位置与 1 进行 AND 运算,就可以方便地检测出该位是否为集合成员:

mov eax,SetX
and eax, 10000b   ;元素[4]是 SetX 的成员吗?

如果本例中的 AND 指令清除了零标志位,那么就可以知道元素[4]是 SetX 的成员。

1) 补集

补集可以用 NOT 指令生成,NOT 指令将所有位都取反。因此,可以用下面的指令生成上例中 SetX 的补集,并存放在 EAX 中:

mov eax,SetX
not eax                  ;Setx的补集

2) 交集

AND 指令可以生成位向量来表示两个集合的交集。下面的代码生成集合 SetX 和 SetY 的交集,并将其存放在 EAX 中:

mov eax,SetX
and eax,SetY

SetX 和 SetY 交集生成过程如下所示:

               1000000000000000000000000000111 (SetX)
AND       1000001010100000000011101100011 (SetY)
-------------------------------------------------------------
               1000000000000000000000000000011 (交集)

很难想象还有更快捷的方法生成交集。对于更大的集合来说,它所需要的位超过了单个寄存器的容量,因此,需要用循环来实现所有位的 AND 运算。

3) 并集

OR 指令生成位图表示两个集合的并集。下面的代码产生集合 SetX 和 SetY 的并集,并将其存放在 EAX 中:

mov eax,SetX
or eax,SetY

OR 指令生成 SetX 和 SetY 并集的过程如下所示:

             1000000000000000000000000000111 (SetX)
OR        1000001010100000000011101100011 (SetY)
-------------------------------------------------------------
             1000001010100000000011101100111 (并集)

< 上一页OR指令 XOR指令下一页 >

爱面试的程序媛,一个分享面试经验的公众号。跟着站长一起学习,每天都有进步。

通俗易懂,深入浅出,定时分享程序员面试的那点事。

面试如何造火箭?工作如何拧螺丝?都在这个公号哦。

扫描二维码关注公众号,免费领取价值 1000 元的求职面试资料(限时免费)!

当你决定关注「爱面试的程序媛」,你已然超越了90%的程序员!

爱面试的程序媛二维码
微信扫描二维码关注