位运算

0 views

前言

现代计算机电路通过高电平/低电平两种状态，即为1/0状态，将数据按照特定的编码格式存储起来。

直接操作这些二进制数据的位数据就是位运算，在iOS中基本所有的位运算都通过枚举声明传值的方式将位运算的实现细节隐藏了起来：

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);

位运算是一种极为高效乃至可以说最为高效的计算方式，虽然现代程序开发中编译器已经为我们做了大量的优化，但是合理的使用位运算可以提高代码的可读性以及执行效率。

基础计算

在了解怎么使用位运算之前，笔者简单说一下CPU处理计算的过程。如果你对CPU的计算方式有所了解，可以跳过这一节。

当代码int sum = 11 + 79被执行的时候，计算机直接将两个数的二进制位进行相加和进位操作：

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

通常来说CPU执行两个数相加操作所花费的时间被我们称作一个时钟周期，而2.0GHz频率的CPU表示可以在一秒执行运算2.0*1024*1024*1024个时钟周期。相较于加法运算，下面看一下11*2、11*4的二进制结果：

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

简单来说，不难发现当某个数乘以2的N次幂的时候，结果等同于将这个数的二进制位置向左移动N位，在代码中我们使用num << N表示将num的二进制数据左移N个位置，其效果等同于下面这段代码：

for (int idx = 0; idx < N; idx++) {
    num *= 2;
}

假如相乘的两个数都不是2的N次幂，这时候编译器会将其中某个值分解成多个2的N次幂相加的结果进行运算。比如37 * 69，这时候CPU会将37分解成32+4+1，然后换算成(69<<5) + (69<<2) + (69<<0)的方式计算出结果。因此，计算两个数相乘通常需要十个左右的时钟周期。 同理，代码num >> N的作用等效于：

for (int idx = 0; idx < N; idx++) {
    num /= 2;
}

但是两个数相除花费的时钟周期要比乘法还要多得多，其大部分消耗在将数值分解成多个2的N次幂上。除此之外，浮点数涉及到的计算更为复杂，这里也简单聊聊浮点数的准确度问题。拿float类型来说，总共使用了32bit的存储空间，其中第一位表示正负，2~13位表示整数部分的值，14~32位之中分别存储了小数位以及科学计数的标识值（这里可能并不那么准确，主要是为了给读者一个大概的介绍）。由于小数位的二进制数据依旧保持2的N次幂特性，假如下面的二进制属于小数位：

1 0 1 1 1 0 0 1

那么这部分小数位的值等于：1/2 + 1/4 + 1/8 + 1/16 + 1/128 = 0.9453125。因此，当你把一个没有任何规律的小数例如3.1415926535898存入计算机的时候，小数点后面会被拆解成很多的2的N次幂进行保存。由于小数位总是有限的，因此当分解的N超出这些位数时导致存储不下，就会出现精度偏差。另一方面，这样的分解计算势必要消耗大量的时钟周期，这也是大量的浮点数运算(cell动态计算)容易引发卡顿的原因。所以，当小数位过多时，改用字符串存储是一个更优的选择。

位运算符

使用的运算符包括下面：

含义 运算符
左移 «
右移 »
按位或 ︳
按位并 &
按位取反 ~
按位异或 ^

  • & 操作

      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
  • 操作 
      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

  • ~ 操作

      0 0 1 0 1 1 1 0    46
  ———————————————
  1 1 0 1 0 0 0 1    225

  • ^ 操作

      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

色彩存储

使用位运算包括下面几个原因：

  • 代码更简洁
  • 更高的效率
  • 更少的内存

简单来说，我们如何单纯的保存一张RGB色彩空间下的图片？由于图片由一系列的像素组成，每个像素有着自己表达的颜色，因此需要这么一个类用来表示图片的单个像素：

@interface Pixel

@property (nonatomic, assign) CGFloat red;
@property (nonatomic, assign) CGFloat green;
@property (nonatomic, assign) CGFloat blue;
@property (nonatomic, assign) CGFloat alpha;

@end

那么在4.7寸的屏幕上，启动图需要750*1334个这样的类，不计算其他数据，单单是变量的存储需要750*1334*4*8 = 32016000个字节的占用内存。但实际上我们使用到的图片总是将RGBA这四个属性保存在一个int类型或者其它相似的少字节变量中。

由于色彩取值范围为0~255，即2^1 ~ 2^8-1不超过一个字节的整数占用内存。因此可以通过左移运算保证每一个字节只存储了一个决定色彩的值：

- (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;
}

同理，通过右移操作保证数值的最后一个字节存储着需要的数据，并用0xff将值取出来：

- (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);
}

对比使用类和位运算存储，效率跟内存占用上可以说是完败。

位运算应用

苹果在类对象的结构中使用了位运算这一设计：每个对象都有一个整型类型的标识符flags，其中多个不同的位表示了是否存在弱引用、是否被初始化等信息，对于这些存储的数据通过&、|等运算符获取出来。这些在runtime源码中都能看到，下面是一段伪代码（参数请勿对号入座）

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;
	}
}

......

借鉴苹果的运算操作，可以声明一个应用常用权限的枚举，来获取我们的应用权限：

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,  ///<    通讯录授权
};

通过声明一个全局的权限变量来保存不同的授权信息。当应用拥有对应的授权时，通过|操作符保证对应的二进制位的值被修改成1。否则对对应授权枚举进行~取反后再&操作消除二进制位的授权表达。为了完成这些工作，建立一个工具类来获取以及更新授权的状态：

/*!
 *  @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

在我们需要使用某些授权的时候，例如打开相册时，直接使用&运算符判断权限即可：

- (void)openCamera {
    LXDAuthorizationType type = [LXDAuthObtainTool obtainAuthorization];
    if (type & LXDAuthorizationTypeCamera) {
        ///  open camera
    } else {
        /// alert
    }
}

在数据存储的方面位运算拥有着占用内存少，高效率的优点，当然位运算能做的不仅仅是这些，比如笔者项目有这样的一个需求：用户登录成功之后在首页界面请求服务器下载所有金额相关的数据。这个需求最大的问题是：

AFN2.3+版本的请求库不支持同步请求，当需要多个请求任务一次性执行时，判断请求任务完成是很麻烦的一件事情。

由于NSInteger拥有8个字节64位的二进制位，因此笔者将每一个二进制位用来表示单个任务请求的完成状态。已知登陆后需要同步数据的接口为N(<64)个，因此可以声明一个全部请求任务完成后的状态变量：

NSInteger complete = 0;
for (int idx = 0; idx < N; idx++) {
    complete |= (1 << idx);
}

然后使用一个标志变量flags用来记录当前任务请求的完成情况，每一个数据同步的任务完成之后对应的二进制位就置为1：

__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];
        }
    }];
}

位运算与算法

在普遍使用高级语言开发的大环境下，位运算的实现更多的被封装起来，因此大多数开发者在项目开发中不见得会使用这一机制。在上面基础计算一节中笔者说过两个数相加只需要一个时钟周期（虽然CPU从寄存器读取存放数据也需要额外的时钟周期，但通常这部分的花销总是常量级，可以忽略不计）

由于位运算的处理基本也在一个时钟周期完成，位运算这一操作备受算法封装者的喜爱。比如交换两个变量的值一般情况下代码是：

int sum = a;
a = b;
b = sum;

又或者：

a = a + b;
b = a - b;
a = a - b;

如果通过位运算的方式则不需要任何加减操作或者临时变量：

a ^= b;
b = a ^ b;
a = a ^ b;

上面的代码和第二种方式的实现思路类似，都是将a和b合并成单个变量，再分别消除变量中的a和b的值（^运算会对相同二进制位的值置0，意味着b^b的结果等于0）

进阶题：找出整型数组中唯一的单独数字，数组中的其他数字的个数为2个

通过上面不用中间变量交换a和b的值可以得出下面的最简代码：

- (int)singleDog(int * nums) {
    int singleDog = 0;
    for (int idx = 0; idx < sizeof(nums)/sizeof(int); idx++) {
        singleDog ^= nums[idx];
    }
    return singleDog;
}

位运算与密码

说了这么多，上面对于位运算的使用都是在编程的环境下，能不能让位运算有更多的使用意义呢？答案是肯定的。俗话说道高一尺，魔高一丈。近日来互联网公司的数据被攻破已经不算什么大新闻了，对于喜欢共用同一个账号名的用户（例如笔者）来说，被撞库的风险非常的大，使用位运算可以帮助我们生成不同的但是又不难记的密码。简单来说，我们可以基于规律的运算，传入随机性的变量生成非唯一的密码。例如：

const NSInteger kRemoveBit = 8;
extern NSString * const kEncryptKey;
static inline NSString * kPasswordGenerate(NSString * randomString) {
	NSInteger hash = randomString.hash;
	NSString * encryptString = [NSString stringWithFormat: @"%lu", hash ^ kEncryptKey.hash];
	return [NSString stringWithFormat: @"%@%lu%@", randomString, ((hash << kRemoveBit) | (hash >> kRemoveBit)), encryptString];
}

传入的string就是生成密码的随机变量，通过获取hash进行少量的位运算之后，由于hash过程的不可逆属性以及在保证string足够长的情况下，基本可以保证密码的复杂性以及安全性。另外，传入的randomString可以根据不同网址生成，例如简书主页为jianshu.com，可以用以下的方式生成：

static inline NSString * kRandomString(NSString * string) {
	unichar ch = [string characterAtIndex: 0];
	return [NSString stringWithFormat: @"%@%lu", string, (ch | string.hash)];
}
NSString * random = kRandomString(@"jianshu.com");
NSString * password = kPasswordGenerate(random);

复杂的密码可以有效的保护账户安全，但是同样复杂的密码更难以记住，更别说我们需要不同账户对应不同的复杂密码。位运算+hash的结合运用可以帮助我们来管理这些复杂的密码，唯一的缺点大概就是手机要装着这么一个app

PREVIOUS定时器动画
NEXT均衡代码职责