位运算

作者: 柚丸 | 来源:发表于2018-11-19 19:37 被阅读22次

位运算

一. 操作符

符号	描述	运算规则
&	与	两个位都为1时，结果才为1
\|	或	两个位都为0时，结果才为0
^	异或	两个位相同都为0，相异为1
~	取反	0变1，1变0
<<	左移	各位全部左移若干位，高位丢弃，低位补0
>>	右移	各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

二. 进制转换

1. 二、八、十六进制转十进制(按位计数法)

e.g.

0B11010101转十进制
$\begin{split} 0B\qquad \qquad 1\qquad \qquad 1\qquad \qquad 0\qquad \qquad 1\qquad \qquad 0\qquad \qquad 1\qquad \qquad 0\qquad \qquad 1 \qquad \\ = (1 \times 2^7) + (1 \times 2^6) + (0 \times2^5) + (1 \times 2^4) + (0 \times 2^3) + (1 \times 2^2) + (0 \times 2^1) + (1 \times 2^0) \\ = 213 \end{split}$

2. 十进制转二、八、十六进制(除r取余，逆序排列)

e.g.
761转二进制
$\begin{split} 761 \div 2 = 380...1 \\ 380 \div 2 = 190...0 \\ 190 \div 2 = 95 ...0 \\ 95 \div 2 = 47...1 \\ 47 \div 2 = 23...1 \\ 23 \div 2 = 11...1 \\ 11 \div 2 = 5...1 \\ 5 \div 2 = 2...1 \\ 2 \div 2 = 1...0 \\ 1 \div 2 = 0...1 \end{split}$
最后得到二进制数1011111001。

3. 二进制转八、十六进制(取三、四合一法)

e.g.
11 010 转八进制
第一步：高位补0
011 010
第二步：每三位对应成八进制数
32

4. 八、十六进制转二进制(取一分三、四法)

e.g.
3b转二进制
第一步：3 = 0011，b = 1011
第二步：拼接
0011 1011

三. 常用位运算小技巧

1. 判断奇偶

根据二进制数的末尾，0为偶数，1为奇数。

所以 n & 1 == 0 ，或者 n | 0 == 0 时，为偶数。

2. 在不引入第三方变量的情况下交换两数

a ^= b;
// a = a ^ b            ①式
b ^= a;
// b = b ^ a
//   = b ^ (a ^ b)      ②式
//   = b ^ b ^ a
//   = 0 ^ a
//   = a
a ^= b;
// 解法1：
// a = a ^ b
//   = (a ^ b) ^ a  // 带入①式，并且第二步中b已经转换为a
//   = b
// 解法2：
// a = a ^ b
//   = (a ^ b) ^ (b ^ a ^ b)  // 带入①式和②式
//   = (a ^ a) ^ (b ^ b) ^ b
//   = 0 ^ 0 ^ b
//   = b

3. 交换符号

取反+1

理解：

负数转正数：负数的补码转源码，除符号位取反加一，变成负数的源码。所以负数取反加一就是符号位一起取反，变成正数的源码，也就是正数的补码。

正数转负数：正数的符号位取反变成负数的源码，负数除符号位取反加一，变成负数的补码；

SignedByte a = 0b00001011;
SignedByte b = 0b11110101;
NSLog(@"a = %d, b = %d", a, b);

3. 求绝对值

正数返回本身，负数返回取反+1

/** 求绝对值 */
- (int)abs:(int)num {
    int absNum;
    // 获取符号位，比如int为4字节，32位，右移31位获取符号位
    int bits = sizeof(int) * 8 - 1;
    // 符号位为0代表是整数，反之是负数，取反加一得到正数
    absNum = ((num >> bits) & 1) == 0 ? num : ~num + 1;
    return absNum;
}

四. 四则运算

1. 加法

加法可以分解成求'和'、'进位'两个部分，'和'要留在当前位，'进位'要加到下一位。

二进制的加法有两个特点：

位的异或运算和求'和'的结果一致

异或 1 ^ 1 = 0 1 ^ 0 = 1   0 ^ 0 = 0
求和 1 + 1 = 0 1 + 0 = 1   0 + 0 = 0

位的与运算跟求'进位'的结果一致

位与 1 & 1 = 1 1 & 0 = 0   0 & 0 = 0
进位 1 + 1 = 1 1 + 0 = 0   0 + 0 = 0

1.1 二进制个位数加法

/** 二进制个位数加法 */
- (int)addA:(int)a andB:(int)b {
    // 记录求和
    int sum = a ^ b;
    // 记录进位
    int carry = (a & b) << 1;
    // 位运算，实现各位求和
    return sum ^ carry;
}

1.2 二进制多位数加法

非递归：

/** 二进制多位数加法，非递归 */
- (int)addA:(int)a andB:(int)b {
    int sum, carry;
    // 保证加数为0，相加不存在进位，此时的异或就是真正的求和
    while (b != 0) {
        // 记录下各位的求和
        sum = a ^ b;
        // 记录下各位的进位
        carry = (a & b) << 1;
        // 求和赋值为被加数
        a = sum;
        // 进位赋值为加数
        b = carry;
    }
    return a;
}

递归：

/** 二进制多位数加法，递归 */
- (int)addA:(int)a andB:(int)b {
    // 判断递归终止条件
    if (b == 0) {
        // 当进位为0时，求和就是两数的和
        return a;
    }
    // 记录下各位的求和
    int sum = a ^ b;
    // 记录下各位的进位
    int carry = (a & b) << 1;
    // 调用当前函数
    return [self addA:sum andB:carry];
}

2. 减法

减去一个数等于加上这个数的负数。

/** 二进制多位数减法 */
- (int)a:(int)a minusB:(int)b {
    return [self addA:a andB:~b + 1];
}

3. 乘法

axb相乘等于b个a相加

/** 两数相乘 */
- (int)multiplyA:(int)a andB:(int)b {
    // 乘积
    int product = 0;
    // 两数相乘的结果是否为负数
    BOOL isNegativeNum = NO;
    
    // 判断两数相乘的结果是否为负数
    if ([self isNegativeNumber:a]) {
        isNegativeNum = !isNegativeNum;
    }
    if ([self isNegativeNumber:b]) {
        isNegativeNum = !isNegativeNum;
    }
    
    // 求和，b个a相加
    for (int i = 0; i < [self abs:b]; i++) {
        product = [self addA:product andB:[self abs:a]];
    }
    
    // 如果乘积结果是负数，乘积取反
    if (isNegativeNum) {
        product = [self addA:~product andB:1];
    }
    
    return product;
}

/** 获取该数的绝对值 */
- (int)abs:(int)num {
    int absNum;
    // 负数取反，正数返回本身
    absNum = [self isNegativeNumber:num] ? [self addA:~num andB:1] : num;
    return absNum;
}

/** 判断该数字是否为负数 */
- (BOOL)isNegativeNumber:(int)num {
    // 获取右移位数，比如int为4字节，32位，右移31位获取符号位
    int bits = 31;
    // 获取符号位，符号位为1代表负数，反之为正数
    BOOL isNegativeNumber = ((num >> bits) & 1) == 1 ? YES : NO;
    return isNegativeNumber;
}

4. 除法

被除数除以除数，相当于被除数一直减去除数，直到不够减为止，做减法的次数就是商。

/** 除法 */
- (int)divideA:(int)a byB:(int)b {
    
    // 被除数和除数的赋值
    int dividend = a;
    int divisor = b;
    // 商，即做减法的次数
    int times = 0;
    // 两数相除的结果是否为负数
    BOOL isNegativeNum = NO;
    
    // 判断两数相除的结果是否为负数
    if ([self isNegativeNumber:dividend]) {
        isNegativeNum = !isNegativeNum;
    }
    if ([self isNegativeNumber:divisor]) {
        isNegativeNum = !isNegativeNum;
    }
    
    // 当被除数小于除数时，代表不够除了
    while (dividend > 0 && [self abs:dividend] >= [self abs:divisor]) {
        int negativeNum = divisor < 0 ? divisor : [self addA:~divisor andB:1];
        dividend = [self addA:[self abs:dividend] andB:negativeNum];
        times++;
    }
    
    // 商为负数的话取反
    if (isNegativeNum) {
        times = [self addA:~times andB:1];
    }
    
    return times;
}

位运算

位运算