iOS开发之位运算
stevenshi
8年前
<h2><strong>前言</strong></h2> <p>从现代计算机电路来说，只有 通电/没电 两种状态，即为 0/1 状态，计算机中所有的数据按照具体的编码格式以二进制的形式存储在设备中。</p> <p>直接操作这些二进制数据的位数据就是位运算，在iOS中基本所有的位运算都通过枚举声明传值的方式将位运算的实现细节隐藏了起来：</p> <pre> <code class="language-objectivec">typedef NS_OPTIONS(NSUInteger, UIRectEdge) { UIRectEdgeNone = 0, UIRectEdgeTop = 1 << 0, UIRectEdgeLeft = 1 << 1, UIRectEdgeBottom = 1 << 2, UIRectEdgeRight = 1 << 3, UIRectEdgeAll = UIRectEdgeTop | UIRectEdgeLeft | UIRectEdgeBottom | UIRectEdgeRight } NS_ENUM_AVAILABLE_IOS(7_0);</code></pre> <p>位运算是一种极为高效乃至可以说最为高效的计算方式，虽然现代程序开发中编译器已经为我们做了大量的优化，但是合理的使用位运算可以提高代码的可读性以及执行效率。</p> <h2><strong>基础计算</strong></h2> <p>在了解怎么使用位运算之前，笔者简单说一下CPU处理计算的过程。如果你对 CPU 的计算方式有所了解，可以跳过这一节。</p> <p>当代码 int sum = 11 + 79 被执行的时候，计算机直接将两个数的二进制位进行相加和进位操作：</p> <pre> <code class="language-objectivec">11: 0 0 0 0 1 0 1 1 79: 0 1 0 0 1 1 1 1 ———————————————————— 90: 0 1 0 1 1 0 1 0</code></pre> <p>通常来说CPU执行两个数相加操作所花费的时间被我们称作一个时钟周期，而2.0GHz频率的CPU表示可以在一秒执行运算 2.0*1024*1024*1024 个时钟周期。相较于加法运算，下面看一下 11*2 、 11*4 的二进制结果：</p> <pre> <code class="language-objectivec">11: 0 0 0 0 1 0 1 1 * 2 ———————————————————— 22: 0 0 0 1 0 1 1 0 11: 0 0 0 0 1 0 1 1 * 4 ———————————————————— 44: 0 0 1 0 1 1 0 0</code></pre> <p>简单来说，不难发现当某个数乘以 2的N次幂 的时候，结果等同于将这个数的二进制位置向左移动 N 位，在代码中我们使用 num << N 表示将 num 的二进制数据左移 N 个位置，其效果等同于下面这段代码：</p> <pre> <code class="language-objectivec">for (int idx = 0; idx < N; idx++) { num *= 2; }</code></pre> <p>假如相乘的两个数都不是 2的N次幂 ，这时候编译器会将其中某个值分解成多个 2的N次幂 相加的结果进行运算。比如 37 * 69 ，这时候CPU会将 37 分解成 32+4+1 ，然后换算成 (69<<5) + (69<<2) + (69<<0) 的方式计算出结果。因此，计算两个数相乘通常需要十个左右的时钟周期。 同理，代码 num >> N 的作用等效于：</p> <pre> <code class="language-objectivec">for (int idx = 0; idx < N; idx++) { num /= 2; }</code></pre> <p>但是两个数相除花费的时钟周期要比乘法还要多得多，其大部分消耗在将数值分解成多个 2的N次幂 上。除此之外，浮点数涉及到的计算更为复杂，这里也简单聊聊浮点数的准确度问题。拿 float 类型来说，总共使用了 32bit 的存储空间，其中第一位表示正负， 2~13位 表示整数部分的值， 14~32位 之中分别存储了小数位以及科学计数的标识值（这里可能并不那么准确，主要是为了给读者一个大概的介绍）。由于小数位的二进制数据依旧保持 2的N次幂 特性，假如下面的二进制属于小数位：</p> <p>那么这部分小数位的值等于： 1/2 + 1/4 + 1/8 + 1/16 + 1/128 = 0.9453125 。因此，当你把一个没有任何规律的小数例如 3.1415926535898 存入计算机的时候，小数点后面会被拆解成很多的 2的N次幂 进行保存。由于小数位总是有限的，因此当分解的 N 超出这些位数时导致存储不下，就会出现精度偏差。另一方面，这样的分解计算势必要消耗大量的时钟周期，这也是大量的浮点数运算 (cell动态计算) 容易引发卡顿的原因。所以，当小数位过多时，改用字符串存储是一个更优的选择。</p> <h2><strong>位运算符</strong></h2> <p>使用的运算符包括下面：</p> <table> <thead> <tr> <th>含义</th> <th>运算符</th> </tr> </thead> <tbody> <tr> <td>左移</td> <td>«</td> </tr> <tr> <td>右移</td> <td>»</td> </tr> <tr> <td>按位或</td> <td>︳</td> </tr> <tr> <td>按位并</td> <td>&</td> </tr> <tr> <td>按位取反</td> <td>~</td> </tr> <tr> <td>按位异或</td> <td>^</td> </tr> </tbody> </table> <ul> <li> <p>& 操作</p> <pre> <code class="language-objectivec">0 0 1 0 1 1 1 0 46 1 0 0 1 1 1 0 1 157 ——————————————— 0 0 0 0 1 1 0 0 12</code></pre> </li> <li> <p>操作</p> <pre> <code class="language-objectivec">0 0 1 0 1 1 1 0 46 1 0 0 1 1 1 0 1 157 ——————————————— 1 0 1 1 1 1 1 1 191</code></pre> </li> <li> <p>~ 操作</p> <pre> <code class="language-objectivec">0 0 1 0 1 1 1 0 46 ——————————————— 1 1 0 1 0 0 0 1 225</code></pre> </li> <li> <p>^ 操作</p> <pre> <code class="language-objectivec">0 0 1 0 1 1 1 0 46 1 0 0 1 1 1 0 1 157 ——————————————— 1 0 1 1 0 0 1 1 179</code></pre> </li> </ul> <h2><strong>色彩存储</strong></h2> <p>使用位运算包括下面几个原因： 1、代码更简洁 2、更高的效率 3、更少的内存</p> <p>简单来说，我们如何单纯的保存一张 RGB 色彩空间下的图片？由于图片由一系列的像素组成，每个像素有着自己表达的颜色，因此需要这么一个类用来表示图片的单个像素：</p> <pre> <code class="language-objectivec">@interface Pixel @property (nonatomic, assign) CGFloat red; @property (nonatomic, assign) CGFloat green; @property (nonatomic, assign) CGFloat blue; @property (nonatomic, assign) CGFloat alpha; @end</code></pre> <p>那么在4.7寸的屏幕上，启动图需要 750*1334 个这样的类，不计算其他数据，单单是变量的存储需要 750*1334*4*8 = 32016000 个字节的占用内存。但实际上我们使用到的图片总是将 RGBA 这四个属性保存在一个 int 类型或者其它相似的少字节变量中。</p> <p>由于色彩取值范围为 0~255 ，即 2^1 ~ 2^8-1 不超过一个字节的整数占用内存。因此可以通过左移运算保证每一个字节只存储了一个决定色彩的值：</p> <pre> <code class="language-objectivec">- (int)rgbNumberWithRed: (int)red green: (int)green blue: (int)blue alpha: (float)alpha { int bitPerByte = 8; int maxNumber = 255; int alphaInt = alpha * maxNumber; int rgbNumber = (red << (bitPerByte*3)) + (green << (bitPerByte*2)) + (blue << bitPerByte) + alphaInt; }</code></pre> <p>同理，通过右移操作保证数值的最后一个字节存储着需要的数据，并用 0xff 将值取出来：</p> <pre> <code class="language-objectivec">- (void)obtainRGBA: (int)rgbNumber { int mask = 0xff; int bitPerByte = 8; double alphaInt = (rgbNumber & mask) / 255.0; int blue = ((rgbNumber >> bitPerByte) & mask); int green = ((rgbNumber >> (bitPerByte*2)) & mask); int red = ((rgbNumber >> (bitPerByte*3)) & mask); }</code></pre> <p>对比使用类和位运算存储，效率跟内存占用上可以说是完败。</p> <h2><strong>位运算应用</strong></h2> <p>苹果在类对象的结构中使用了位运算这一设计：每个对象都有一个整型类型的标识符 flags ，其中多个不同的位表示了是否存在弱引用、是否被初始化等信息，对于这些存储的数据通过 & 、 | 等运算符获取出来。这些在 <a href="/misc/goto?guid=4958971075686849179" rel="nofollow,noindex">runtime源码</a> 中都能看到，下面是一段伪代码（参数请勿对号入座）</p> <pre> <code class="language-objectivec">#define IS_TAGGED_POINTER (1 << 12); #define HAS_WEAK_REFERENCE (1 << 13); inline void objc_object::free() { if (this->flags | HAS_WEAK_REFERENCE) { /// set all weak reference point to nil } } inline int objc_object::retainCount() { if (this.flags | IS_TAGGED_POINTER) { return (int)INT_MAX; } else { return this->retainCount; } } ......</code></pre> <p>借鉴苹果的运算操作，可以声明一个应用常用权限的枚举，来获取我们的应用权限：</p> <pre> <code class="language-objectivec">typedef NS_ENUM(NSInteger, LXDAuthorizationType) { LXDAuthorizationTypeNone = 0, LXDAuthorizationTypePush = 1 << 0, ///< 推送授权 LXDAuthorizationTypeLocation = 1 << 1, ///< 定位授权 LXDAuthorizationTypeCamera = 1 << 2, ///< 相机授权 LXDAuthorizationTypePhoto = 1 << 3, ///< 相册授权 LXDAuthorizationTypeAudio = 1 << 4, ///< 麦克风授权 LXDAuthorizationTypeContacts = 1 << 5, ///< 通讯录授权 };</code></pre> <p>通过声明一个全局的权限变量来保存不同的授权信息。当应用拥有对应的授权时，通过 | 操作符保证对应的二进制位的值被修改成 1 。否则对对应授权枚举进行 ~ 取反后再 & 操作消除二进制位的授权表达。为了完成这些工作，建立一个工具类来获取以及更新授权的状态：</p> <pre> <code class="language-objectivec">/*! * @brief 获取应用授权信息工具，最低使用版本：iOS8.0 */ NS_CLASS_AVAILABLE_IOS(8_0) @interface LXDAuthObtainTool : NSObject /// 获取当前应用权限 + (LXDAuthorizationType)obtainAuthorization; /// 更新应用权限 + (void)updateAuthorization; @end #pragma mark - LXDAuthObtainTool.m static LXDAuthorizationType kAuthorization; @implementation LXDAuthObtainTool + (void)initialize { kAuthorization = LXDAuthorizationTypeNone; [self updateAuthorization]; } /// 获取当前应用权限 + (LXDAuthorizationType)obtainAuthorization { return kAuthorization; } /// 更新应用权限 + (void)updateAuthorization { /// 推送 if ([UIApplication sharedApplication].currentUserNotificationSettings.types == UIUserNotificationTypeNone) { kAuthorization &= (~LXDAuthorizationTypePush); } else { kAuthorization |= LXDAuthorizationTypePush; } /// 定位 if ([CLLocationManager authorizationStatus] == kCLAuthorizationStatusAuthorizedAlways || [CLLocationManager authorizationStatus] == kCLAuthorizationStatusAuthorizedWhenInUse) { kAuthorization |= LXDAuthorizationTypeLocation; } else { kAuthorization &= (~LXDAuthorizationTypeLocation); } /// 相机 if ([AVCaptureDevice authorizationStatusForMediaType: AVMediaTypeVideo] == AVAuthorizationStatusAuthorized) { kAuthorization |= LXDAuthorizationTypeCamera; } else { kAuthorization &= (~LXDAuthorizationTypeCamera); } /// 相册 if ([PHPhotoLibrary authorizationStatus] == PHAuthorizationStatusAuthorized) { kAuthorization |= LXDAuthorizationTypePhoto; } else { kAuthorization &= (~LXDAuthorizationTypePhoto); } /// 麦克风 [[AVAudioSession sharedInstance] requestRecordPermission: ^(BOOL granted) { if (granted) { kAuthorization |= LXDAuthorizationTypeAudio; } else { kAuthorization &= (~LXDAuthorizationTypeAudio); } }]; /// 通讯录 if ([UIDevice currentDevice].systemVersion.doubleValue >= 9) { if ([CNContactStore authorizationStatusForEntityType: CNEntityTypeContacts] == CNAuthorizationStatusAuthorized) { kAuthorization |= LXDAuthorizationTypeContacts; } else { kAuthorization &= (~LXDAuthorizationTypeContacts); } } else { if (ABAddressBookGetAuthorizationStatus() == kABAuthorizationStatusAuthorized) { kAuthorization |= LXDAuthorizationTypeContacts; } else { kAuthorization &= (~LXDAuthorizationTypeContacts); } } } @end</code></pre> <p>在我们需要使用某些授权的时候，例如打开相册时，直接使用 & 运算符判断权限即可：</p> <pre> <code class="language-objectivec">- (void)openCamera { LXDAuthorizationType type = [LXDAuthObtainTool obtainAuthorization]; if (type & LXDAuthorizationTypeCamera) { /// open camera } else { /// alert } }</code></pre> <p>在数据存储的方面位运算拥有着占用内存少，高效率的优点，当然位运算能做的不仅仅是这些，比如笔者项目有这样的一个需求：用户登录成功之后在首页界面请求服务器下载所有金额相关的数据。这个需求最大的问题是：</p> <p>AFN2.3+ 版本的请求库不支持同步请求，当需要多个请求任务一次性执行时，判断请求任务完成是很麻烦的一件事情。</p> <p>由于 NSInteger 拥有8个字节64位的二进制位，因此笔者将每一个二进制位用来表示单个任务请求的完成状态。已知登陆后需要同步数据的接口为 N(<64) 个，因此可以声明一个全部请求任务完成后的状态变量：</p> <pre> <code class="language-objectivec">NSInteger complete = 0; for (int idx = 0; idx < N; idx++) { complete |= (1 << idx); }</code></pre> <p>然后使用一个标志变量 flags 用来记录当前任务请求的完成情况，每一个数据同步的任务完成之后对应的二进制位就置为 1 ：</p> <pre> <code class="language-objectivec">__block NSInteger flags = 0; NSArray<NSString *> * urls = @[......]; NSArray<NSDictionary *> * params = @[......]; for (NSInteger idx = 0; idx < urls.count; idx++) { NSString * url = urls[idx]; NSDictionary * param = params[idx]; [LXDDataSyncTool syncWithUrl: url params: param complete: ^{ flags |= (1 << idx); if ( (flags ^ complete) == 0 ) { [self completeDataSync]; } }]; }</code></pre> <h2><strong>位运算与算法</strong></h2> <p>在普遍使用高级语言开发的大环境下，位运算的实现更多的被封装起来，因此大多数开发者在项目开发中不见得会使用这一机制。在上面 基础计算 一节中笔者说过两个数相加只需要一个时钟周期（虽然 CPU 从寄存器读取存放数据也需要额外的时钟周期，但通常这部分的花销总是常量级，可以忽略不计）</p> <p>由于位运算的处理基本也在一个时钟周期完成，位运算这一操作备受算法封装者的喜爱。比如交换两个变量的值一般情况下代码是：</p> <pre> <code class="language-objectivec">int sum = a; a = b; b = sum;</code></pre> <p>又或者：</p> <pre> <code class="language-objectivec">a = a + b; b = a - b; a = a - b;</code></pre> <p>如果通过位运算的方式则不需要任何加减操作或者临时变量：</p> <pre> <code class="language-objectivec">a ^= b; b = a ^ b; a = a ^ b;</code></pre> <p>上面的代码和第二种方式的实现思路类似，都是将 a 和 b 合并成单个变量，再分别消除变量中的 a 和 b 的值（ ^ 运算会对相同二进制位的值置0，意味着 b^b 的结果等于0）</p> <p>进阶题：找出整型数组中唯一的单独数字，数组中的其他数字的个数为2个</p> <p>通过上面不用中间变量交换 a 和 b 的值可以得出下面的最简代码：</p> <pre> <code class="language-objectivec">- (int)singleDog(int * nums) { int singleDog = 0; for (int idx = 0; idx < sizeof(nums)/sizeof(int); idx++) { singleDog ^= nums[idx]; } return singleDog; }</code></pre> <p> </p> <p>来自：http://allluckly.cn/投稿/tougao69</p> <p> </p>