文档章节

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

 天使爱美
发布于 2016/11/08 16:39
字数 2874
阅读 17
收藏 0
点赞 0
评论 1

从现代计算机电路来说,只有 通电/没电 两种状态,即为 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的技术博客

© 著作权归作者所有

共有 人打赏支持
粉丝 0
博文 28
码字总数 53872
作品 0
朝阳
加载中

评论(1)

小码爱大牛
小码爱大牛
你好,我是深圳一家以家居安防为核心的智能家居公司的HR在招聘一位会ffmpeg的Android开发工程师和一位iOS开工程师。不知道您自己或者身边同事朋友有没有在看工作机会的呢?如果感兴趣可以发简历到3288771685@qq.com或者加起QQ。
【AR】开始使用Vuforia开发iOS(2)

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

lichong951 ⋅ 06/11 ⋅ 0

iOS最火那年转型管理,他收获了什么?

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

100offer ⋅ 04/13 ⋅ 0

iOS逆向工程- 学习整理(工具详解)

前言 一、逆向工程的要求 具备丰富的 iOS 开发经验 最好能非常熟悉 iOS 设备的硬件构成,iOS 系统的运行原理。 拿到任意一个 App 之后能够大致推断出它的项目规模和使用的技术,比如它的MVC模...

_小迷糊 ⋅ 05/11 ⋅ 0

如何重写自定义对象的hash方法

本文是我首发在iOS知识小集团队的,欢迎关注微博话题#ios知识小集#。我的微博:halohily hash 是 NSObject 协议中定义的一个属性,也就是说,任何一个 NSObject 的子类都会有 hash 方法(对应...

halohily ⋅ 05/22 ⋅ 0

一样的iOS开发程序员为什么有人4k有人40k?

前言 移动开发真正火起来其实就是最近这几年,iOS 开发技术因为发展也就才这么几年,所以值得做的事情还有很多,这就造成了每年苹果的 WWDC 都会推出一堆新的特性和 API。整体上来说,这对业...

原来是泽镜啊 ⋅ 05/16 ⋅ 0

面试官自述:面向高级开发人员的iOS面试问题

当您准备进行技术性iOS面试时,了解您可能会询问哪些主题以及经验丰富的iOS开发人员期望什么是非常重要的。 这是许多硅谷公司用来衡量iOS候选人资历水平的一系列问题。 这些问题涉及iOS开发的...

菇哒微课 ⋅ 04/26 ⋅ 0

你知道我为什么特别讨厌程序员吗?

你知道我为什么特别讨厌程序员吗? 2018-05-28 11:20编辑: 枣泥布丁分类:程序人生来源:程序师 程序员修电脑装系统 招聘信息: C++工程师 Cocos2d-x游戏客户端开发 iOS开发工程师 京东招聘...

枣泥布丁 ⋅ 05/28 ⋅ 0

bug的一生:如何体现测试专业度?

bug的一生:如何体现测试专业度? 2018-06-15 16:38编辑: garace分类:程序人生来源:代码湾 测试程序员bug 招聘信息: C++工程师 Cocos2d-x游戏客户端开发 iOS开发工程师 京东招聘iOS开发工...

garace ⋅ 06/15 ⋅ 0

如何判断你是合格的高级iOS开发工程师?

前言 随着移动互联网的高速发展泄洪而来,有意学习移动开发的人越来越多了,竞争也是越来越大,需要学习的东西很多。如何才能在激烈的移动开发者竞争中一枝独秀,成为一名真正合格的高级iOS...

_小迷糊 ⋅ 05/26 ⋅ 0

HDU ~ 6297 ~ CCPC直播 (模拟,输出格式控制)

思路:模拟就行了,注意Running和RTE的开头字母一样。 iomanip是I/O流控制头文件,就像printf的格式化输出一样。 以下是一些常用的: dec 置基数为10 相当于"%d" hex 置基数为16 相当于"%X" oc...

zscdst ⋅ 05/29 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

从零开始搭建Risc-v Rocket环境---(1)

为了搭建Rocke环境,我买了一个2T的移动硬盘,安装的ubuntu-16.04 LTS版。没有java8,gcc是5.4.0 joe@joe-Inspiron-7460:~$ java -version程序 'java' 已包含在下列软件包中: * default-...

whoisliang ⋅ 21分钟前 ⋅ 0

大数据学习路线(自己制定的,从零开始学习大数据)

大数据已经火了很久了,一直想了解它学习它结果没时间,过年后终于有时间了,了解了一些资料,结合我自己的情况,初步整理了一个学习路线,有问题的希望大神指点。 学习路线 Linux(shell,高并...

董黎明 ⋅ 27分钟前 ⋅ 0

systemd编写服务

一、开机启动 对于那些支持 Systemd 的软件,安装的时候,会自动在/usr/lib/systemd/system目录添加一个配置文件。 如果你想让该软件开机启动,就执行下面的命令(以httpd.service为例)。 ...

勇敢的飞石 ⋅ 29分钟前 ⋅ 0

mysql 基本sql

CREATE TABLE `BBB_build_info` ( `community_id` varchar(50) NOT NULL COMMENT '小区ID', `layer` int(11) NOT NULL COMMENT '地址层数', `id` int(11) NOT NULL COMMENT '地址id', `full_......

zaolonglei ⋅ 38分钟前 ⋅ 0

安装chrome的vue插件

参看文档:https://www.cnblogs.com/yulingjia/p/7904138.html

xiaoge2016 ⋅ 41分钟前 ⋅ 0

用SQL命令查看Mysql数据库大小

要想知道每个数据库的大小的话,步骤如下: 1、进入information_schema 数据库(存放了其他的数据库的信息) use information_schema; 2、查询所有数据的大小: select concat(round(sum(da...

源哥L ⋅ 今天 ⋅ 0

两个小实验简单介绍@Scope("prototype")

实验一 首先有如下代码(其中@RestController的作用相当于@Controller+@Responsebody,可忽略) @RestController//@Scope("prototype")public class TestController { @RequestMap...

kalnkaya ⋅ 今天 ⋅ 0

php-fpm的pool&php-fpm慢执行日志&open_basedir&php-fpm进程管理

12.21 php-fpm的pool pool是PHP-fpm的资源池,如果多个站点共用一个pool,则可能造成资源池中的资源耗尽,最终访问网站时出现502。 为了解决上述问题,我们可以配置多个pool,不同的站点使用...

影夜Linux ⋅ 今天 ⋅ 0

微服务 WildFly Swarm 管理

Expose Application Metrics and Information 要公开关于我们的微服务的有用信息,我们需要做的就是将监视器模块添加到我们的pom.xml中: 这将使在管理和监视功能得到实现。从监控角度来看,...

woshixin ⋅ 今天 ⋅ 0

java连接 mongo伪集群部署遇到的坑

部署mongo伪集群 #创建mongo数据存放文件地址mkdir -p /usr/local/config1/datamkdir -p /usr/local/config2/data mkdir -p /usr/local/config3/data mkdir -p /usr/local/config1/l......

努力爬坑人 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部