位运算世界畅游指南
目录
概念介绍
我们都知道,计算机中的所有数据最终都是以二进制(bit)的形式存储在计算机的。而在我们平时开发中所接触数据的大多是字节为单位的,有了位运算之后我们就可以操作字节中的比特位了。在iOS的runtime源码以及NS_OPTIONS 中都运用了位运算的知识,可见其重要性了。另外值得一提的是,大部分语言的位运算符都相同,所以这是一篇老少皆宜的文章。
阅读本篇文章前,你需要知道的一些东西: - 我们在讨论二进制的时候,位序一般都是从右(低位)到左(高位)的。举个例子,对于二进制0011来说,第0位是1,第1位是1,第二位是0,第三位是0。 - 在大部分编程语言中,0x开头代表十六进制,比如0xff代表十六进制ff;0b开头代表二进制,比如0b11111111代表二进制的11111111;0开头代表8进制,比如0377代表8进制377;如果你不写前缀,那默认就是10进制。无论你是几进制,你所描述的本质其实是一样的,只是表现形式不同而已。比如前面的0xff、0b11111111、0377、255,它们都是等价的。你可以在编程语言中语言测试下。
1 | bool c = 0xff == 0b11111111; // true |
基本位运算符
位运算符就像是控制比特位的扳手,在学习位运算前先介绍下每个运算符的意义及其用法。
按位与 ( AND )
举个例子,10100001 & 10001001 = 10000001。(注:操作数都为二进制。)
按位或 ( OR )
运算规则: 两个值中有一个为1结果便为1,两个值都为0时结果才为0。在编程语言里一般用 | 表示或运算符。
举个例子,10100001 | 10001001 = 10101001。
按位异或 ( XOR )
运算规则: 只有当两个值不相同时结果才为1,两个值相同时结果为0。在编程语言里一般用 ^ 表示异或运算符。
举个例子,10100001 ^ 10001001 = 00101000。
取反 ( NOT )
在数值的二进制表示方式上,将0变为1,将1变为0。在编程语言里一般用 ~
表示取反运算符。
来看一个例子可能会更加直观:
右移 ( >> )
右移将操作数的二进制位整体向右移动N位,空出部分用0填充,在编程语言里一般用
>>表示右移运算符。
举个例子,下图对二进制 10111101
右移3位后,最右边的101被移除,左边空出来3位用0填充(本文章默认所有数据都为无符号类型,所以本操作为逻辑右移)。
左移 ( << )
左移将操作数的二进制位整体向左移动N位,空出部分用0填充,在编程语言里一般用
<< 表示左移运算符。
举个例子,下图对二进制 10111101
左移4位后,最左边的1011被移除,右边空出来4位用0填充。
基础技巧
这里先介绍一些比较简单实用的位运算技巧,这些技巧在日常开发中也是比较常用的。
将某些二进制位设置为1
假设x=0b10011010,现在我想将第5、6位置为1,将其变为0b11111010,那么执行 (x = x | 0b01100000) 就是我们想要的结果;那若是想将第0、5、6为置为1,变成0b11111011呢?那么执行(x = x | 0b01100001)就是我们想要的结果。 根据上面的两个例子,我们可以得到一个结论: - x = x | SET_ON ,该语句将x中对应于SET_ON中为1的二进制位设置为1;x中对应于SET_ON中为0的二进制位保持不变。
掩码
掩码这个词经常能在计算机网络里听到,比较熟悉的话就是子网掩码了。掩码是起的非常好的一个名字,当我们的操作数和掩码进行与运算(&)后,掩码中二进制为0的位会屏蔽掉原操作数对应的二进制位。 举个例子,假如现在我有一个2个字节的数据0xBA15,若要屏蔽掉中间0xA1这8位二进制变成0xB005,该如何设计掩码呢?答案很简单,只要将掩码中间8位设为0其他设为1即可,所以本例中的掩码应为0xF00F,0xBA15 & 0xF00F=0xB005。可以结合下图理解:
取出第i位二进制值
这个函数传入一个data,返回其二进制从右边开始数第i位的值。
1 | unsigned char getBit( unsigned long data , int i ) { |
{getBit(168,3)}
,168对应的二进制为10101000,右移3位后变成00010101,最后00010101
& 00000001 = 1,取出成功。
计算无符号变量的取值范围
笔者在mac上的unsigned long 是8个字节,可以存储64位二进制,由于没有符号位,故只需将这64位二进制都填充为1就得到unsigned long变量的最大值了。1 | // 将全0取反变为全1装进变量x中。 |
奇偶判断
如果最后一位二进制为0,那么这个数字就是偶数,如果为1就是奇数。这里给出实现函数:
1 | int isOdd(int value) { |
2+2^3+2^7 = 2*(1+2^2+2^6)
,故为偶数,大家可以多写几组数字验证。
关于负数:虽然负数在计算机中以补码的方式存储,但由于补码最后一位和原码最后一位相同,所以上面的函数同样适用于负数。为什么呢?举个例子: - 假如最后一位是0,取反后变成1,然后再+1又变成0。 - 假如最后一位是1,取反后变成0,然后再+1又变成1。
看到了吧,最后又变回去了。
统计二进制中1个数
1 | int x =0xba;//10111010 |
循环中每次执行x = x&(x-1)后,x的二进制的最后一个1就会被消去。当所有1都被消去后,count计数完毕,x=0,退出循环。
那么为什么x = x&(x-1)能够消去其二进制的最后一个1呢?举个例子: - 假如x=101000,那么 x-1=100111。 - 假如x=101011,那么 x-1=101010。
可以发现规律: - 当x=nn..nn100..00这种形式时,x-1=nn..nn011..11。 这个时候x & (x-1) = nn..nn100..00 & nn..nn011..11 = nn..nn000.00,x最后一个1被消去。 - 当x=nn..nn1这种形式时,x-1=nn..nn0。 这个时候x & (x-1) = nn..nn1 & nn..nn0 = nn..nn0,x最后一个1被消去。
交换两个变量的值(无临时变量)
1 | // 注:参数是c++的引用类型。 |
想要了解原理,需要先知道几个异或运算的性质:
- 交换律:a^b = b^a
- 结合律:(ab)c = a(bc)
- 恒等律:a^0 = a
- 规零律:a^a = 0
- 自反性:abb = a
假设一开始,a=k,b=t
。
- 执行
a=a^b
后a=k^t
; - 执行
b=a^b
后b = k^t^t=k
,注意这里用到了自反性; - 执行
a=a^b
后a=k^t^k=t^k^k=t
,注意这里用到了交换律和自反性; - 最后得到
a=t,b=k
,交换完成。
当然了,不仅限于交换整型变量。举一个不太常用的例子,我们可以不用临时变量交换两个c语言字符串。下面代码中的a和b本质上是在交换"a-a-a-a-a-a"和"b-b-b-b-b-b"地址,所以效果也是一样的。
1 | char *a = "a-a-a-a-a-a";// 存储在数据区的字符串常量 |
子集生成
假设现在有一集合A={a,b,c},要求生成这个集合的所有子集。构造子集时,我们可以使用二进制中第i位的值决定是否要选取集合A中的第i个元素。其中值为1代表选取,值为0代表不选取。举个例子,100代表只选第一个元素a,其构成的子集为{a};101代表选取第一个a以及第三个c,其构成的子集为{a,c}。
下面列举出A的所有子集:
编号 | A的子集 | 人类思考过程 | 二进制表示 |
---|---|---|---|
0 | {} | 什么都不选 | 000 |
1 | {c} | 不选a,不选b,选c | 001 |
2 | {b} | 不选a,选b,不选c | 010 |
3 | {b,c} | 不选a,选b,选c | 011 |
4 | {a} | 选a,不选b,不选c | 100 |
5 | {a,c} | 选a,不选b,选c | 101 |
6 | {a,b} | 选a,选b,不选c | 110 |
7 | {a,b,c} | 选a,选b,选c | 111 |
1 |
|
进阶技巧
这里介绍C语言程序设计这本书中的两个非常实用的函数,相信你在平时的项目中也能应用的到。
getBits
该函数用来返回x中从右边数第p位开始向右数n位二进制。
1 | unsigned getBits(unsigned x,int p,int n) { |
getBits(168,5,3)
后,返回168对应二进制10101000从右边数第5位开始向右3位二进制,也就是101。可以结合下图理解:
下面来说一下原理:
一开始执行(x>>(p+1-n))
这里是为了将期望获得的字段移动到最右边。用上面的例子,执行完后x变成:
~(~0<<n)
是为了生成右边n位全1的掩码。
对于上面的例子~(~0<<3)
,我们一起来分析下过程:
- 一开始执行~0生成全1的二进制,11111111。
- 然后左移3位变成11111000。
- 最后执行圆括号左边的~,取反变成00000111,现在掩码生成完成。
最后执行中间的那个&,将(x>>(p+1-n))
和~(~0<<n)
与运算,取出期望字段。对于上面的例子,对应过程图如下:
setBits
该函数返回x中从第p位开始的n个(二进制)位设置为y中最右边n位的值,x的其余各位保持不变。
1 | unsigned setBits(unsigned x, int p,int n , unsigned y) { |
举个例子(#2),调用setBits(168, 5, 4, 0b0101)
后,将168对应二进制10101000从右边数第5位开始的4个二进制位设置为0101,设置完后变成10010100,最后将结果返回。可以结合下图理解:
第一眼看到这个函数代码还是有一些恐怖的,不用害怕,我们一层层解析,相信你一定能感受位运算的精妙之处!
我们先要将函数拆成两个部分看待,第一部分是( x & ~( ~( ~0 << n ) << ( p+1-n ) ) )
记为$0;另一部分是(y & ~(~0 << n) ) << (p+1-n)
记为$1。
下面分析下$0和$1的作用:
- 其中,$0是为了将x中期望修改的n个二进制清0。在例子(#2)中,$0返回的二进制应该为:10000000,注意到红体部分已经被清0。
- $1是为了取出y最右边n个二进制,并与x中待修改的那n个二进制对齐。在例子(#2)中,$1返回的二进制应该:00010100。
- 最后$0 | $1 ,也就是将$1的值设置到$0当中。在在例子(#2)中,$0 | $1 = 10000000 | 00010100 = 10010100,设置完成。
下面具体分析下$0是如何将期望修改的n个二进制清0的:
- 既然是清0,我们可以想使用到最早所学的掩码,所以可以将$0以&为分割符拆成两段看待,其中
~( ~( ~0 << n ) << ( p+1-n ) )
生成x清0所需要的掩码。 - 一开始执行
~(~0 << n)
生成右边n个1,其余全为0的。代入例子(#2)的参数,也就是~(~0 << 4)
,结果为:00001111。这里为了方便记忆,把~(~0 << n)
记为?0 。 - 然后接着执行
?0 << (p+1-n)
,将右边n个1左移到相应位置上。代入例子(#2)的参数及上一步的结果,应执行00001111 << (5+1-4)
,结果为00111100。这里将?0 << (p+1-n)
记为?1。 - 最后执行最外层
~?1
,生成清零所需的掩码。代入例子(#2)的参数及上一步的结果,应执行~00111100
,结果为11000011,掩码生成完毕。 - 最后执行
x & ~?1
,用掩码将x中待清零的位清0。代入例子(#2)的参数及上一步的结果,应执行10101000 & 11000011
结果为10000000,清0成功。
下面具体分析下$1是如何取出y最右边n个二进制并与x中待修改的那n个二进制对齐的:
- 首先
~(~0 << n)
和$0第一个步骤一样,不过这次直接用这个结果当作掩码。代入例子(#2)的参数,也就是~(~0 << 4)
,结果为00001111。这里将~(~0 << n)
记为@@0
。 - 接着 执行
y & @@0
,用掩码的原理将y最右边的n位取出。代入例子(#2)的参数及上一步的结果,应执行00000101 & 00001111
,结果为00000101。这里将y & @@0
记为?1 。 - 最后执行
?1 << (p+1-n)
,左移到对应位置上。代入例子(#2)的参数及上一步的结果,也就是00000101 << (5+1-4)
,结果为00010100,生成结束。
Objective-C的Runtime中的位运算应用
这里会介绍一些runtime源码中使用位运算的例子。
判断是否是TaggedPointer
在runtime源码中,判断是否是TaggedPointer的函数定义如下:
1 | static inline bool |
const void * _Nullable ptr
为对象的地址。_OBJC_TAG_MASK是一个掩码
,其宏定义比较长,我将它简单的整理了一下:
1 |
|
- 64-bit Mac下, _OBJC_TAG_MASK为1UL,对应二进制为:00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001
- 其他平台下, _OBJC_TAG_MASK 为(1UL<<63),对应二进制为:10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
根据以上结论,结合_objc_isTaggedPointer
函数的代码,很容易理解它的原理:
- 在64-bit MAC下,取出对象地址二进制的最低位(LSB),若最低位为1则为TaggedPointer。
- 在其他平台下,取出对象地址二进制的最高位(MSB),若为1则为TaggedPointer。
isa_t
在ARM64架构之前,对象的isa指针直接指向类对象地址;在ARM64架构之后,一个8字节的isa变量额外存储了许多与当前对象相关的信息。 我们先看来看一下最新的isa结构定义:
1 | union isa_t { |
相关的宏定义:
1 |
1 |
|
- 是否使用isa指针优化:1
- 是否有用关联对象:0
- 是否有C++析构函数:0
- isa取出类对象:7fffb506f140
- class方法取出类对象:7fffb506f140
- 调试时是否完成初始化:3b
- 是否有被弱引用指向过:1
- 是否正在释放:0
- 是否使用了sidetable:0
- 引用计数器-1:2
方法缓存中的Hash函数
先给出Runtime源码里从缓存中查找方法的函数:
1 | bucket_t * cache_t::find(cache_key_t k, id receiver) |
再来看下cache_hash的实现:
1 | // Class points to cache. SEL is key. Cache buckets store SEL+IMP. |
- key: 方法SEL的地址(8字节64位)
- mask: 哈希表长度 -1
(key & mask)的结果能保证在[0,mask]整数范围内,所以可以正确的映射到Hash表上。
NS_OPTIONS
NS_OPTIONS如其名「选项」,可以让你在一个8字节NSUInteger变量中最多保存64个选项开关。 先来看看KVO中NSKeyValueObservingOptions的定义:
1 | typedef NS_OPTIONS(NSUInteger, NSKeyValueObservingOptions) { |
- 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000001
- 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000010
- 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000100
- 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000001000
可以看得出,每个选项都是独立一个1,并且和其他选项的位置不一样。如果对某几个选项进行或运算(|)就会合并它们的选项。 举个平时常用的例子:NSKeyValueObservingOptionNew | NSKeyValueObservingOptionOld 的结果为:
- 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 000000011
1 | - (void)readOptions:(NSKeyValueObservingOptions)options { |
1 | [self readOptions:NSKeyValueObservingOptionOld | NSKeyValueObservingOptionNew]; |
1 | /* |