文档章节

iOS程序猿必知的位运算相关知识

 天使爱美
发布于 2016/11/08 16:39
字数 2874
阅读 20
收藏 0

从现代计算机电路来说,只有 通电/没电 两种状态,即为 0/1 状态,计算机中所有的数据按照具体的编码格式以二进制的形式存储在设备中。

  直接操作这些二进制数据的位数据就是位运算,在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 179: 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/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

 

色彩存储

  使用位运算包括下面几个原因: 1、代码更简洁 2、更高的效率 3、更少的内存

  简单来说,我们如何单纯的保存一张 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.mstatic 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* urls = @[......];NSArray* 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;

}

 

文章来源:Bison的技术博客

© 著作权归作者所有

共有 人打赏支持
粉丝 1
博文 36
码字总数 59694
作品 0
朝阳
私信 提问
加载中

评论(1)

小码爱大牛
小码爱大牛
你好,我是深圳一家以家居安防为核心的智能家居公司的HR在招聘一位会ffmpeg的Android开发工程师和一位iOS开工程师。不知道您自己或者身边同事朋友有没有在看工作机会的呢?如果感兴趣可以发简历到3288771685@qq.com或者加起QQ。
唐巧专访:用 HTML5 写移动应用终究不会成为主流

小编语 本文为 DevLink 专访系列,本期采访嘉宾是 iDev 苹果开发者大会特约出品人、小猿搜题产品技术负责人——唐巧。在参加 iDev 苹果开发者大会前夕,这位资深 iOS 开发者接受了 DevLink ...

DevLink
2016/10/13
270
0
唐巧专访:用 HTML5 写移动应用终究不会成为主流

小编语 本文为 DevLink 专访系列,本期采访嘉宾是 iDev 苹果开发者大会特约出品人、小猿搜题产品技术负责人——唐巧。在参加 iDev 苹果开发者大会前夕,这位资深 iOS 开发者接受了 DevLink ...

DevLink
2016/10/18
252
2
【AR】开始使用Vuforia开发iOS(2)

原 设置iOS开发环境 安装Vuforia iOS SDK 如何安装Vuforia iOS示例 编译并运行Vuforia iOS示例 支持iOS金属 iOS 64位迁移 设置iOS开发环境 适用于iOS的Vuforia引擎目前支持运行iOS 9及更高版...

lichong951
06/11
0
0
iOS 开发之一些著名开发者博客

国内 王巍 王巍目前在日本横滨任职于 LINE。工作内容主要进行 Unity3D 开发,8小时之外经常进行 iOS/Mac 开发。他的陈列柜中已有多款应用,其中番茄工作法工具非常棒。 博客 池建强 池建强,...

maskmale
02/25
0
0
iOS最火那年转型管理,他收获了什么?

过去一年,移动端开发者就业环境爆冷。一些迷茫的程序员,通过转岗甚至转行的方式,暂时告别自己的移动开发路。 提到转型,作为国内最早的一批 iOS 开发者,唐巧相当有发言权。工作八年,他恰...

100offer
04/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Flink-数据流编程模型

1、抽象等级 Flink提供了不同级别的抽象来开发流/批处理应用程序。 1) 低层级的抽象 最低层次的抽象仅仅提供有状态流。它通过Process函数嵌入到DataStream API中。它允许用户自由地处理来自一...

liwei2000
25分钟前
1
0
Java开发Swing实战JFrame和JTabbedPane容器的用法详细解析

概述: 项目是一个桌面程序,涉及标签和按钮组件、布局管理器组件、面板组件、列表框和下拉框组件等组件,以及Swing事件处理机制。 下面先从最基础的界面开始。 /** * @author: lishuai * @...

金铭鼎IT教育
30分钟前
9
0
flask 之旅

环境 为了正确地跑起来,你的应用需要依赖许多不同的软件。 就算是再怎么否认这一点的人,也无法否认至少需要依赖Flask本身。 你的应用的运行环境,在当你想要让它跑起来时,是至关重要的。 ...

hblt-j
30分钟前
6
0
easyui的上传文件

记录一下自己亲手操刀easyui的心得:不用不知道,一用就问题多,网上查资料,有用的真的太少了 ——————————————————正文 FileBox,还是不错的讲真,至少我去自己写就gaga了...

anlve
31分钟前
4
0
如何做好SQLite 使用质量检测,让事故消灭在摇篮里

本文由云+社区发表 SQLite 在移动端开发中广泛使用,其使用质量直接影响到产品的体验。 常见的 SQLite 质量监控一般都是依赖上线后反馈的机制,比如耗时监控或者用户反馈。这种方式问题是: ...

腾讯云加社区
34分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部