iOS开发-位运算基础

前言

现代计算机只有0/1状态，计算机中所有的数据按照具体的编码格式以二进制的形式存储在设备中。

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

原码

原码规定数值最高位为符号位，正数符号位为0，负数符号位为1（0有两种表示：+0和-0），其余位表示数值的大小。

例如，11的原码为00001011，-11的原码就是10001011。

原码不能直接参加运算，可能会出错。例如数学上，1+(-1)=0，而在二进制中00000001+10000001=10000010，换算成十进制为-2，显然出错了。因此原码的符号位不能直接参与运算，必须和其他位分开，这就增加了开销和复杂性。

反码

反码通常是用来由原码求补码或者由补码求原码的过渡码。

正数的反码和原码相同。

负数的反码就是原码符号位除外，其他位按位取反。

补码

在计算机系统中，数值一律用补码来表示和存储。因为使用补码可以将符号位和数值域统一处理；同时，加法和减法也可以统一处理。

补码是通过“模”将减法变加法：假设当前时针指向8点，而准确时间是6点，调整时间可有以下两种拨法：一种是倒拨2小时，即8-2=6；另一种是顺拨10小时，(8+10)%12=6，即(8-2)%12=(8+10)%12。在12为模的系统里，+10和-2效果是一样的，因此凡是-2运算，都可以用+10来代替，对“模”而言，-2和+10互为补数。而计算机是模为2^n的系统，因此只需要找到被减数的补数，即可将减法变为加法，而二进制数的补数称为补码。

怎么求补数呢？x mod y = z，其中y为模，而z和x互为补数。

因此正数的补数即为自己：7 mod 12 = 7。

而负数的补数则是一个正数，就可以化减法为加法：(-2) mod 12 = 10、(-5) mod 12 = 7。

所以得出结论是：

正数的补码与原码相同。

负数的补码，将其原码除符号位外的所有位取反（0变1，1变0，符号位为1不变）后加1，即为负数的反码加1。

已知一个数的补码求原码，其实就是对该补码再求补码，因为原码和补码互为补数。

基础运算

加法运算

 

两个二进制整数相加时，是位对位处理的，从最低的一对位（右边）开始，依序将每一对位进行加法运算。两个二进制数字相加，有四种结果，如下所示：
 

0 + 0 = 0	0 + 1 = 1
1 + 0 = 1	1 + 1 = 10

1与1相加的结果是二进制的10（十进制的 2）。多出来的数字会向更高位产生一个进位。

  0 0 0 0 0 1 0 0  4
+ 0 0 0 0 0 1 1 1  7
---------------------
  0 0 0 0 1 0 1 1  11

当负数相加时，需要先把负数转为补码，再相加。例如1+(-1)=0。

       原码        反码        补码
+1   00000001    00000001    00000001
-1   10000001    11111110    11111111

  0 0 0 0 0 0 0 1
+ 1 1 1 1 1 1 1 1
------------------
1 0 0 0 0 0 0 0 0   -->最高位溢出，结果为0.

当最高位相加有进位时就会导致溢出，正数与正数相加可能导致溢出，负数与负数相加也可能导致溢出，而正数加负数是绝对不会产生溢出。

减法运算

减法可以将被减数看作加它的负数，即可把减法转为加法。例如，如果减法表达式为 C=A-B，则处理器就可以很方便地将其转换为加法表达式：C=A+(-B)。

而无符号数相减如果得到负数，得到的仍是正数。例如，10-42得到有符号数-32(1110 0000)，得到无符号数224(1110 0000)。

乘法运算

当其中一个乘数是2^n时，等于将另一个乘数的所有二进制位向左移动n位。

11： 0 0 0 0 1 0 1 1 * 4(2^2)
-----------------------------
44： 0 0 1 0 1 1 0 0

而当两个乘数都不是2^n时，这时候编译器会将其中一个乘数分解成多个2^n相加的结果，然后进行分别运算。

例如：37 * 69，首先将37 分为 32(2^5) + 4(2^2)  + 1(2^0)，然后变为 (69 << 5) + (69 << 2) + ( 69 << 0)算出结果。

除法运算

当除数是2^n时，等于将被除数的所有二进制位向右移动n位。

当除数不是2^n时，这个原理比较难并且精度问题。之后再专门补充。

浮点数简要介绍

由于浮点数的小数位的二进制数据依旧保持2^n的特性，假如10111001属于小数位，那么这部分小数位的值等于：1/2 + 1/4 + 1/8 + 1/16 + 1/128 = 0.9453125。

因此，把一个小数位很多的浮点数（3.14159269453125）存入计算机的时候，所有小数位会被拆解成很多的2^n进行保存。由于位数总是有限的，因此当分解到第n位数溢出时，就会出现精度偏差。另一方面，过多的分解计算势必要消耗大量的时钟周期，这也是大量的浮点数运算容易引发卡顿的原因，比如cell滑动时动态算高。

位运算符 

1、&（按位与）：对应两个二进制位均为1时，结果才为1，否则为0。

  0 0 0 1 0 1 0 1
& 1 0 1 1 0 0 1 1
------------------
  0 0 0 1 0 0 0 1

2、|（按位或）：对应两个二进制位只要有一个为1时，结果才为1，否则为0。

  0 0 0 1 0 1 0 1
| 1 0 1 1 0 0 1 1
------------------
  1 0 1 1 0 1 1 1

3、^（按位异或）：对应两个二进制位都不相同时，结果才为1，否则为0。

  0 0 0 1 0 1 0 1
^ 1 0 1 1 0 0 1 1
------------------
  1 0 1 0 0 1 1 0

4、~（取反）：所有二进制位都变为相反的（0变1,1变0），符号位也变。

~ 0 0 0 1 0 1 0 1 
------------------
  1 1 1 0 1 0 1 0

5、>>（右移）：右移n位本质是a=a/2^n。把整数a的所有二进制位全部右移n位，符号位不变。（正数）符号位为0时，数值最高位补0。（负数）符号位为1时，数值最高位补0或1，则取决与编译系统，一般最高位补符号位。

 0 0 0 1 0 1 0 1 >> 4
------------------
 0 0 0 0 0 0 0 1

6、<<（左移）：左移n位本质是a=a*2^n。把整数a的所有二进制位全部左移n位，溢出的最高位丢弃，包括符号位，低位补0。因此左移会改变正负性。

 0 0 0 1 0 1 0 1 << 3
------------------
 1 0 1 0 1 0 0 0

色彩存储

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

简单来说，我们如何单纯的保存一张RGBA色彩空间下的图片？

由于图片由一系列的像素组成，每个像素有着自己表达的颜色，如果我们使用类来表示图片的单个像素：

@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寸的小屏幕上，启动图就需要755*1334个这样的类，不计算类其他数据，单单是RGBA的存储就需要750*1334*4*8 = 32016000个字节的占用内存。但是色彩取值范围仅为0~255，只占一个字节的内存，一个像数点的RGBA值仅需要4个字节即可存储，因此一个像数点只需要存储在unsigned int里，然后通过左移就可每个字节只存一个色彩值：

- (int)rgbNumberWithRed:(int)red green:(int)green blue:(int)blue alpha:(CGFloat)alpha {
    int bitPerByte = 8;
    int maxNumber  = 255;
    int alphaInt   = alpha * maxNumber;
    unsigned int rgba = (red << (bitPerByte*3)) + (green << (bitPerByte*2)) + (blue << bitPerByte) + alphaInt;
}

然后通过按字节右移并&0xff将RGBA值挨个取出来：

- (void)obtainRGBA: (int)rgba {
    int mask = 0xff;
    int bitPerByte = 8;

    double alpha = (rgba & mask) / 255.0;
    int blue  = ((rgba >> bitPerByte)     & mask);
    int green = ((rgba >> (bitPerByte*2)) & mask);
    int red   = ((rgba >> (bitPerByte*3)) & mask);
}

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

位运算应用

苹果官方在类对象的结构中也使用了位运算这一设计：每个对象都有一个整型类型的标识符flags，其中每一位都包含了信息，例如是否存在弱引用、是否被初始化、对象是否为常量等，这些数据通过&、|等运算符从flags里获取出来。

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

typedef NS_ENUM(NSInteger, SSAuthorizationType)
{
    SSAuthorizationTypeNone     = 0,
    SSAuthorizationTypePush     = 1 << 0,  ///< 推送授权
    SSAuthorizationTypeLocation = 1 << 1,  ///< 定位授权
    SSAuthorizationTypeCamera   = 1 << 2,  ///< 相机授权
    SSAuthorizationTypePhoto    = 1 << 3,  ///< 相册授权
    SSAuthorizationTypeAudio    = 1 << 4,  ///< 麦克风授权
    SSAuthorizationTypeContacts = 1 << 5,  ///< 通讯录授权
};

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

@interface SSAuthObtainTool : NSObject

/// 获取当前应用权限
+ (SSAuthorizationType)obtainAuthorization;
/// 更新应用权限
+ (void)updateAuthorization;

@end

#pragma mark -  SSAuthObtainTool .m
static SSAuthorizationType kAuthorization;

@implementation SSAuthObtainTool

+ (void)initialize
{
    kAuthorization = SSAuthorizationTypeNone;
    [self updateAuthorization];
}

/// 获取当前应用权限
+ (SSAuthorizationType)obtainAuthorization
{
    return kAuthorization;
}

/// 更新应用权限
+ (void)updateAuthorization
{
    /// 推送
    if ([UIApplication sharedApplication].currentUserNotificationSettings.types == UIUserNotificationTypeNone) {
        kAuthorization &= (~SSAuthorizationTypePush);
    } else {
        kAuthorization |= SSAuthorizationTypePush;
    }
    /// 定位
    if ([CLLocationManager authorizationStatus] == kCLAuthorizationStatusAuthorizedAlways || [CLLocationManager authorizationStatus] == kCLAuthorizationStatusAuthorizedWhenInUse) {
        kAuthorization |= SSAuthorizationTypeLocation;
    } else {
        kAuthorization &= (~SSAuthorizationTypeLocation);
    }
    /// 相机
    if ([AVCaptureDevice authorizationStatusForMediaType: AVMediaTypeVideo] == AVAuthorizationStatusAuthorized) {
        kAuthorization |= SSAuthorizationTypeCamera;
    } else {
        kAuthorization &= (~SSAuthorizationTypeCamera);
    }
    /// 相册
    if ([PHPhotoLibrary authorizationStatus] == PHAuthorizationStatusAuthorized) {
        kAuthorization |= SSAuthorizationTypePhoto;
    } else {
        kAuthorization &= (~SSAuthorizationTypePhoto);
    }
    /// 麦克风
    [[AVAudioSession sharedInstance] requestRecordPermission: ^(BOOL granted) {
        if (granted) {
            kAuthorization |= SSAuthorizationTypeAudio;
        } else {
            kAuthorization &= (~SSAuthorizationTypeAudio);
        }
    }];
    /// 通讯录
    if ([UIDevice currentDevice].systemVersion.doubleValue >= 9) {
        if ([CNContactStore authorizationStatusForEntityType: CNEntityTypeContacts] == CNAuthorizationStatusAuthorized) {
            kAuthorization |= SSAuthorizationTypeContacts;
        } else {
            kAuthorization &= (~SSAuthorizationTypeContacts);
        }
    } else {
        if (ABAddressBookGetAuthorizationStatus() == kABAuthorizationStatusAuthorized) {
            kAuthorization |= SSAuthorizationTypeContacts;
        } else {
            kAuthorization &= (~SSAuthorizationTypeContacts);
        }
    }
}

@end

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

- (void)openCamera {
    SSAuthorizationType type = [SSAuthObtainTool obtainAuthorization];
    if (type & SSAuthorizationTypeCamera) {
        ///  open camera
    } else {
        /// alert
    }
}

位运算与算法

在普遍使用高级语言开发的大环境下，位运算的实现更多的被封装起来，因此大多数开发者在项目开发中不见得会使用这一机制。

由于位运算的效率极高，因此位运算备受算法封装者的喜爱。

比如交换两个变量的值一般情况下代码是：

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的值，但效率更高。

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

- (NSUInteger)singleNumberInArray:(NSArray *)array {
    NSUInteger singleNumber = 0;
    for (int idx=0; idx<array.count; idx++) {
        singleNumber ^= array[idx];
    }
    return singleNumber;
}

字节对齐算法

unsigned int byte_align(unsigned int n, unsigned int align){
    return (n + (align - 1)) & (~(align - 1));
}

 

本文地址：https://blog.csdn.net/qq_36557133/article/details/107501583

如对本文有疑问， 点击进行留言回复！！