位运算世界畅游指南

我会带着你远行 2022-10-01 06:49 170阅读 0赞

## 目录 ##

*  概念介绍
 *  基本位运算符
    
     *  按位与 （ AND ）
     *  按位或 （ OR ）
     *  按位异或 （ XOR ）
     *  取反 （ NOT ）
     *  右移 ( >> )
     *  左移 ( << )
 *  基础技巧
    
     *  将某些二进制位设置为1
     *  掩码
     *  取出第i位二进制值
     *  计算无符号变量的取值范围
     *  奇偶判断
     *  统计二进制中1个数
     *  交换两个变量的值（无临时变量）
     *  子集生成
 *  进阶技巧
    
     *  getBits
     *  setBits
 *  Objective-C的Runtime中的位运算应用
    
     *  判断是否是TaggedPointer
     *  isa\_t
     *  方法缓存中的Hash函数
 *  NS\_OPTIONS
 *  参考资料

## 概念介绍 ##

我们都知道，计算机中的所有数据最终都是以二进制(bit)的形式存储在计算机的。而在我们平时开发中所接触数据的大多是字节为单位的，有了位运算之后我们就可以操作字节中的比特位了。在iOS的runtime源码以及NS\_OPTIONS 中都运用了位运算的知识，可见其重要性了。另外值得一提的是，大部分语言的位运算符都相同，所以这是一篇老少皆宜的文章。

阅读本篇文章前，你需要知道的一些东西：

1.  我们在讨论二进制的时候，位序一般都是从右（低位）到左（高位）的。举个例子，对于二进制0011来说，第0位是1，第1位是1，第二位是0，第三位是0。
2.  在大部分编程语言中，0x开头代表十六进制，比如0xff代表十六进制ff；0b开头代表二进制，比如0b11111111代表二进制的11111111；0开头代表8进制，比如0377代表8进制377;如果你不写前缀，那默认就是10进制。无论你是几进制，你所描述的本质其实是一样的，只是表现形式不同而已。比如前面的0xff、0b11111111、0377、255，它们都是等价的。你可以在编程语言中语言测试下。

bool c  = 0xff == 0b11111111; // true
      bool c0 = 0b11111111 == 0377; // true
      bool c1 = 0377 == 255; //true
    复制代码

1.  之所以程序员都喜欢用16进制，首先是因为16进制和二进制的转换实在太方便了。比如0xFAFA，直把每个字母转成4位二进制拼接在一起即可，0xF：0b1111 ，0xA:0b1010，所以0xFAFA二进制是0b1111101011111010。另外一点，因为16进制中2个字母代表8位二进制（一个字节），所以当我们看到16进制的时候就能立马知道多少个字节了。比如前面的0xFAFA，第一个字节是0xFA，第二个字节也是0xFA，共两个字节。

## 基本位运算符 ##

位运算符就像是控制比特位的扳手，在学习位运算前先介绍下每个运算符的意义及其用法。

### 按位与 （ AND ） ###

运算规则：只有在两个值都为1时结果才为1，两个值中有一个为0结果便为0。在编程语言里一般用 & 表示与运算符。

举个例子，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填充（本文章默认所有数据都为无符号类型，所以本操作为[逻辑右移][Link 1]）。

### 左移 ( << ) ###

左移将操作数的二进制位整体向左移动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位的值。

unsigned char getBit( unsigned long data , int i ) {
    
        // i = 0时，代表取最右边的哪一位。
        data  = data >> i ;
        return data & 1 ;
    }
    复制代码

原理很简单，先将data右移i位，这样能保证第i位的值处于data的最右边，然后再用data & 1取出即可。 举个例子，如果我调用了`{getBit(168,3)}`，168对应的二进制为10101000，右移3位后变成00010101，最后00010101 & 00000001 = 1，取出成功。

### 计算无符号变量的取值范围 ###

笔者在mac上的unsigned long 是8个字节，可以存储64位二进制，由于没有符号位，故只需将这64位二进制都填充为1就得到unsigned long变量的最大值了。

// 将全0取反变为全1装进变量x中。 unsigned long x = ~0; // 输出二进制为全1的变量x printf("unsigned long max = %lu\n",x);复制代码

### 奇偶判断 ###

如果最后一位二进制为0，那么这个数字就是偶数，如果为1就是奇数。这里给出实现函数：

int isOdd(int value) {
        return (value & 1); // 取出最后一位二进制，若为1则是奇数
    }
    复制代码

说下大致原理：若最后一位二进制为0，那么二进制转成十进制后必然可以写成2n的形式，必为偶数。比如我随便写一个最后一位为0的二进制数字 10001010，那么其十进制数为`2+2^3+2^7 = 2*(1+2^2+2^6)`,故为偶数，大家可以多写几组数字验证。

关于负数：虽然负数在计算机中以[补码][Link 2]的方式存储，但由于补码最后一位和原码最后一位相同，所以上面的函数同样适用于负数。为什么呢？举个例子：

*  假如最后一位是0，取反后变成1，然后再+1又变成0。
 *  假如最后一位是1，取反后变成0，然后再+1又变成1。

看到了吧，最后又变回去了。

### 统计二进制中1个数 ###

int x =0xba;//10111010
    int count = 0;
    while (x!=0) {
        x = x&(x-1);
        count++;
    }
    printf("%d\n",count);
    复制代码

循环中每次执行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被消去。

### 交换两个变量的值（无临时变量） ###

// 注：参数是c++的引用类型。
    void swap(int &a,int &b) {
        a=a^b;
        b=a^b;
        a=a^b;
    }
    复制代码

想要了解原理，需要先知道几个异或运算的性质:

*  交换律：a^b = b^a
 *  结合律：(a^b)^c = a^(b^c)
 *  恒等律：a^0 = a
 *  规零律：a^a = 0
 *  自反性：a^b^b = 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"地址，所以效果也是一样的。

char *a = "a-a-a-a-a-a";// 存储在数据区的字符串常量
     char *b = "b-b-b-b-b-b";//存储在数据区的字符串常量
     printf("before exchange: a=%s,b=%s\n",a,b);
     a = (char*)((long)a^(long)b);
     b = (char*)((long)a^(long)b);
     a = (char*)((long)a^(long)b);
     printf("after exchange: a=%s,b=%s\n",a,b);
     /* 最终输出为： /* 最终输出为： before exchange: a=a-a-a-a-a-a,b=b-b-b-b-b-b after exchange: a=b-b-b-b-b-b,b=a-a-a-a-a-a */
    复制代码

### 子集生成 ###

假设现在有一集合A=\{a,b,c\}，要求生成这个集合的所有子集。构造子集时，我们可以使用二进制中第i位的值决定是否要选取集合A中的第i个元素。其中值为1代表选取，值为0代表不选取。举个例子，100代表只选第一个元素a，其构成的子集为\{a\};101代表选取第一个a以及第三个c，其构成的子集为\{a,c\}。

下面列举出A的所有子集：

<table> 
 <thead> 
  <tr> 
   <th>编号</th> 
   <th>A的子集</th> 
   <th>人类思考过程</th> 
   <th>二进制表示</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>0</td> 
   <td>{}</td> 
   <td>什么都不选</td> 
   <td>000</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>{c}</td> 
   <td>不选a，不选b，选c</td> 
   <td>001</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>{b}</td> 
   <td>不选a，选b，不选c</td> 
   <td>010</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>{b,c}</td> 
   <td>不选a，选b，选c</td> 
   <td>011</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>{a}</td> 
   <td>选a，不选b，不选c</td> 
   <td>100</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>{a,c}</td> 
   <td>选a，不选b，选c</td> 
   <td>101</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>{a,b}</td> 
   <td>选a，选b，不选c</td> 
   <td>110</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>{a,b,c}</td> 
   <td>选a，选b，选c</td> 
   <td>111</td> 
  </tr> 
 </tbody> 
</table>

细心的话，应该能发现上面的表格中的编号和二进制刚刚好能对的上。所以对于有个n个元素的集合，只要生成0到2^n-1个整数编号，然后根据每个编号对应的二进制解析出相应的子集即可。 下面是c语言实现的代码：

#include <stdio.h>
    #include <string.h>
    void prinstSubSet(char *S,int id) {
        int n = (int)strlen(S);// 集合的元素个数
        char result[100];
        int index=0;
        printf("{");
        for(int i=n-1;i>=0;i--){
            if ((id>>i)&1) {
                // 若第i位值为1，代表选择第i个元素（从右边开始数）
                result[index++]=S[n-1-i];//由于字符串第0个字符是最左边，所以要颠倒下。
            }
        }
        for(int i =0;i<index;i++) {
            printf("%c",result[i]);
            if(i!=index-1)
                printf(",");
        }
        printf("}\n");
    }
    void create(char *S) {
        int n = (int)strlen(S);// 集合的元素个数
        int begin = 0;
        int end = (1<<n)-1; // 2^n-1
        
        //生成0到2^n-1个编号(id)
        for (int id = begin;id<=end;id++) {
            prinstSubSet(S, id);// 根据编号对应的二进制输出子集
        }
    }
    int main(int argc, const char * argv[]) {
        create("abc");// 生成{a,b,c}的子集
        return 0;
    }
    复制代码

## 进阶技巧 ##

这里介绍[C语言程序设计][C]这本书中的两个非常实用的函数，相信你在平时的项目中也能应用的到。

### getBits ###

该函数用来返回x中从右边数第p位开始向右数n位二进制。

unsigned getBits(unsigned x,int p,int n) {
        return (x>>(p+1-n)) & ~(~0<<n);
    }
    复制代码

举个例子，调用`getBits(168,5,3)`后，返回168对应二进制10101000从右边数第5位开始向右3位二进制，也就是101。可以结合下图理解：

下面来说以下原理：

*  一开始执行`(x>>(p+1-n))` 这里是为了将期望获得的字段移动到最右边。用上面的例子，执行完后x变成：
    
      
    
 *  `~(~0<<n)` 是为了生成右边n位全1的[掩码][Link 3]。 对于上面的例子`~(~0<<3)` ,我们一起来分析下过程。
    
    1.  一开始执行~0生成全1的二进制,11111111。
    2.  然后左移3位变成11111000。
    3.  最后执行圆括号左边的~，取反变成00000111，现在掩码生成完成。

*  最后执行中间的那个&，将`(x>>(p+1-n))`和`~(~0<<n)`与运算，取出期望字段。对于上面的例子，对应过程图如下：

### setBits ###

该函数返回x中从第p位开始的n个（二进制）位设置为y中最右边n位的值，x的其余各位保持不变。

unsigned setBits(unsigned x, int p,int n , unsigned y) {
        return (  x & ~( ~( ~0 << n ) << ( p+1-n ) ) ) |
               (y & ~(~0 << n) ) << (p+1-n);
    }
    复制代码

举个例子(\#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的函数定义如下：

static inline bool 
    _objc_isTaggedPointer(const void * _Nullable ptr)
    {
        return ((uintptr_t)ptr & _OBJC_TAG_MASK) == _OBJC_TAG_MASK;
    }
    复制代码

其中参数`const void * _Nullable ptr`为对象的地址。\_OBJC\_TAG\_MASK是一个`掩码`,其宏定义比较长，我将它简单的整理了一下：

#if (TARGET_OS_OSX || TARGET_OS_IOSMAC) && __x86_64__
        // 64-bit Mac - tag bit is LSB
    # define _OBJC_TAG_MASK 1UL
    #else
        // Everything else - tag bit is MSB
    # define _OBJC_TAG_MASK (1UL<<63)
    #endif
    复制代码

我们得到了结论：

*  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结构定义：

union isa_t {
        isa_t() { }
        isa_t(uintptr_t value) : bits(value) { }
    
        Class cls;
        uintptr_t bits;
    #if defined(ISA_BITFIELD)
        struct { 
            ISA_BITFIELD;  // defined in isa.h
        };
    #endif
    };
    
    复制代码

相关的宏定义：

# if __arm64__
    # define ISA_MASK 0x0000000ffffffff8ULL
    # define ISA_MAGIC_MASK 0x000003f000000001ULL
    # define ISA_MAGIC_VALUE 0x000001a000000001ULL
    # define ISA_BITFIELD \ uintptr_t nonpointer : 1; \ uintptr_t has_assoc : 1; \ uintptr_t has_cxx_dtor : 1; \ uintptr_t shiftcls : 33; /*MACH_VM_MAX_ADDRESS 0x1000000000*/ \ uintptr_t magic : 6; \ uintptr_t weakly_referenced : 1; \ uintptr_t deallocating : 1; \ uintptr_t has_sidetable_rc : 1; \ uintptr_t extra_rc : 19
    # define RC_ONE (1ULL<<45)
    # define RC_HALF (1ULL<<18)
    
    # elif __x86_64__
    # define ISA_MASK 0x00007ffffffffff8ULL
    # define ISA_MAGIC_MASK 0x001f800000000001ULL
    # define ISA_MAGIC_VALUE 0x001d800000000001ULL
    # define ISA_BITFIELD \ uintptr_t nonpointer : 1; \ uintptr_t has_assoc : 1; \ uintptr_t has_cxx_dtor : 1; \ uintptr_t shiftcls : 44; /*MACH_VM_MAX_ADDRESS 0x7fffffe00000*/ \ uintptr_t magic : 6; \ uintptr_t weakly_referenced : 1; \ uintptr_t deallocating : 1; \ uintptr_t has_sidetable_rc : 1; \ uintptr_t extra_rc : 8
    # define RC_ONE (1ULL<<56)
    # define RC_HALF (1ULL<<7)
    
    # else
    # error unknown architecture for packed isa
    # endif
    复制代码

上面代码中用了c语言的联合体以及[位段][Link 4]的技术，当然这不是我们的重点，有兴趣的话可以去了解下。 我在Mac上编写了一段代码，用来展示这8个字节里所存储的数据有多么丰富。要知道，8个字节仅仅是一个long变量的大小。

#import <Foundation/Foundation.h>
    # define ISA_MASK 0x00007ffffffffff8ULL
    union isa_t {
        Class cls;
        uintptr_t bits;
        struct { 
            uintptr_t nonpointer        : 1;
            uintptr_t has_assoc         : 1;
            uintptr_t has_cxx_dtor      : 1;
            uintptr_t shiftcls          : 44;
            uintptr_t magic             : 6;
            uintptr_t weakly_referenced : 1;
            uintptr_t deallocating      : 1;
            uintptr_t has_sidetable_rc  : 1;
            uintptr_t extra_rc          : 8;
        };
    };
    
    int main(int argc, const char * argv[]) {
        @autoreleasepool {
            NSObject *obj =  [[NSObject alloc]init]; // 这块内存记为#1，obj指向#1，#1的引用计数器+1
            NSObject *obj2 = obj; // obj2也指向#1，#1的引用计数器+1
            NSObject *obj3 = obj; // obj3也指向#1，#1的引用计数器+1
            __weak NSObject *weak_obj = obj;// 弱引用
            union isa_t _isa_t;
            void *_obj = (__bridge void *)(obj);
            _isa_t.bits = *((uintptr_t*)_obj);
            printf("是否使用isa指针优化:%x\n",_isa_t.nonpointer);
            printf("是否有用关联对象:%x\n",_isa_t.has_assoc);
            printf("是否有C++析构函数:%x\n",_isa_t.has_cxx_dtor);
            printf("isa取出类对象:%llx\n",_isa_t.bits & ISA_MASK);
            printf("class方法取出类对象:%lx\n",(long)[NSObject class]);
            printf("调试时是否完成初始化:%x\n",_isa_t.magic);
            printf("是否有被弱引用指向过:%x\n",_isa_t.weakly_referenced);
            printf("是否正在释放:%x\n",_isa_t.deallocating);
            printf("是否使用了sidetable:%x\n",_isa_t.has_sidetable_rc);
            printf("引用计数器-1:%x\n",_isa_t.extra_rc);
        }
        return 0;
    }
    复制代码

输出的结果：

*  是否使用isa指针优化:1
 *  是否有用关联对象:0
 *  是否有C++析构函数:0
 *  isa取出类对象:7fffb506f140
 *  class方法取出类对象:7fffb506f140
 *  调试时是否完成初始化:3b
 *  是否有被弱引用指向过:1
 *  是否正在释放:0
 *  是否使用了sidetable:0
 *  引用计数器-1:2

### 方法缓存中的Hash函数 ###

先给出Runtime源码里从缓存中查找方法的函数：

bucket_t * cache_t::find(cache_key_t k, id receiver)
    {
        assert(k != 0);
    
        bucket_t *b = buckets();
        mask_t m = mask();
        mask_t begin = cache_hash(k, m);
        mask_t i = begin;
        do {
            if (b[i].key() == 0  ||  b[i].key() == k) {
                return &b[i];
            }
        } while ((i = cache_next(i, m)) != begin);
    
        // hack
        Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
        cache_t::bad_cache(receiver, (SEL)k, cls);
    }
    复制代码

再来看下cache\_hash的实现：

// Class points to cache. SEL is key. Cache buckets store SEL+IMP.
    // Caches are never built in the dyld shared cache.
    static inline mask_t cache_hash(cache_key_t key, mask_t mask) {
        return (mask_t)(key & mask);
    }
    复制代码

这里需要说明cache\_hash函数中几个参数的意义：

*  key： 方法SEL的地址（8字节64位）
 *  mask： 哈希表长度 -1

(key & mask)的结果能保证在\[0,mask\]整数范围内，所以可以正确的映射到Hash表上。

## NS\_OPTIONS ##

NS\_OPTIONS如其名「选项」，可以让你在一个8字节NSUInteger变量中最多保存64个选项开关。 先来看看KVO中NSKeyValueObservingOptions的定义：

typedef NS_OPTIONS(NSUInteger, NSKeyValueObservingOptions) {
    
        NSKeyValueObservingOptionNew = 0x01,
        NSKeyValueObservingOptionOld = 0x02,
        NSKeyValueObservingOptionInitial = 0x04,
        NSKeyValueObservingOptionPrior = 0x08
    };
    复制代码

一共有4个选项，其对应的二进制分别为：

*  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

下面给出读取这些选项的代码：

- (void)readOptions:(NSKeyValueObservingOptions)options {
        NSLog(@"---------------begin---------------");
        if (options & NSKeyValueObservingOptionNew ) {
            NSLog(@"contain NSKeyValueObservingOptionNew");
        }
        if (options & NSKeyValueObservingOptionOld ) {
            NSLog(@"contain NSKeyValueObservingOptionOld");
        }
        if (options & NSKeyValueObservingOptionInitial ) {
             NSLog(@"contain NSKeyValueObservingOptionInitial");
        }
        if (options & NSKeyValueObservingOptionPrior ) {
             NSLog(@"contain NSKeyValueObservingOptionPrior");
        }
         NSLog(@"---------------end-----------------");
    }
    
    // 输出
    /* ---------------begin--------------- contain NSKeyValueObservingOptionNew contain NSKeyValueObservingOptionOld ---------------end----------------- ---------------begin--------------- contain NSKeyValueObservingOptionNew contain NSKeyValueObservingOptionInitial contain NSKeyValueObservingOptionPrior ---------------end----------------- */
    复制代码

调用：

[self readOptions:NSKeyValueObservingOptionOld | NSKeyValueObservingOptionNew];
     [self readOptions:NSKeyValueObservingOptionNew | NSKeyValueObservingOptionInitial |NSKeyValueObservingOptionPrior];
    复制代码

输出:

/* ---------------begin--------------- contain NSKeyValueObservingOptionNew contain NSKeyValueObservingOptionOld ---------------end----------------- ---------------begin--------------- contain NSKeyValueObservingOptionNew contain NSKeyValueObservingOptionInitial contain NSKeyValueObservingOptionPrior ---------------end----------------- */
    复制代码

## 参考资料 ##

*  [《C语言程序设计（K & R）》][C]

--------------------

本篇已同步到个人博客：[位运算世界畅游指南][Link 5]

转载于:https://juejin.im/post/5ce1324af265da1b8f1a9162

[Link 1]: https://link.juejin.im?target=https%3A%2F%2Fwww.cnblogs.com%2Fcodingbylch%2Fp%2F5398342.html
[Link 2]: https://juejin.im/post/5c400edfe51d452a167bacf4
[C]: https://link.juejin.im?target=https%3A%2F%2Fbook.douban.com%2Fsubject%2F1139336%2F
[Link 3]: https://link.juejin.im?target=https%3A%2F%2Fobjc94.com%2Fbit-operation%2F%233.0
[Link 4]: https://link.juejin.im?target=https%3A%2F%2Fwww.runoob.com%2Fcprogramming%2Fc-bit-fields.html
[Link 5]: https://link.juejin.im?target=https%3A%2F%2Fobjc94.com%2Fbit-operation%2F