位运算
一. 操作符
| 符号 | 描述 | 运算规则 |
|---|---|---|
| & | 与 | 两个位都为1时，结果才为1 |
| | | 或 | 两个位都为0时，结果才为0 |
| ^ | 异或 | 两个位相同都为0，相异为1 |
| ~ | 取反 | 0变1，1变0 |
| << | 左移 | 各位全部左移若干位，高位丢弃，低位补0 |
| >> | 右移 | 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移） |
二. 进制转换
1. 二、八、十六进制转十进制(按位计数法)
e.g.
0B11010101转十进制
2. 十进制转二、八、十六进制(除r取余，逆序排列)
e.g.
761转二进制
最后得到二进制数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;
}
网友评论