位運(yùn)算
一. 操作符
| 符號 | 描述 | 運(yùn)算規(guī)則 |
|---|---|---|
| & | 與 | 兩個(gè)位都為1時(shí)，結(jié)果才為1 |
| | | 或 | 兩個(gè)位都為0時(shí)，結(jié)果才為0 |
| ^ | 異或 | 兩個(gè)位相同都為0，相異為1 |
| ~ | 取反 | 0變1，1變0 |
| << | 左移 | 各位全部左移若干位，高位丟棄，低位補(bǔ)0 |
| >> | 右移 | 各二進(jìn)位全部右移若干位，對無符號數(shù)，高位補(bǔ)0，有符號數(shù)，各編譯器處理方法不一樣，有的補(bǔ)符號位（算術(shù)右移），有的補(bǔ)0（邏輯右移） |
二. 進(jìn)制轉(zhuǎn)換
1. 二、八、十六進(jìn)制轉(zhuǎn)十進(jìn)制(按位計(jì)數(shù)法)
e.g.
0B11010101轉(zhuǎn)十進(jìn)制
2. 十進(jìn)制轉(zhuǎn)二、八、十六進(jìn)制(除r取余，逆序排列)
e.g.
761轉(zhuǎn)二進(jìn)制
最后得到二進(jìn)制數(shù)1011111001。
3. 二進(jìn)制轉(zhuǎn)八、十六進(jìn)制(取三、四合一法)
e.g.
11 010 轉(zhuǎn)八進(jìn)制
第一步：高位補(bǔ)0
011 010
第二步：每三位對應(yīng)成八進(jìn)制數(shù)
32
4. 八、十六進(jìn)制轉(zhuǎn)二進(jìn)制(取一分三、四法)
e.g.
3b轉(zhuǎn)二進(jìn)制
第一步：3 = 0011，b = 1011
第二步：拼接
0011 1011
三. 常用位運(yùn)算小技巧
1. 判斷奇偶
根據(jù)二進(jìn)制數(shù)的末尾，0為偶數(shù)，1為奇數(shù)。
所以 n & 1 == 0 ， 或者 n | 0 == 0 時(shí)，為偶數(shù)。
2. 在不引入第三方變量的情況下交換兩數(shù)
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已經(jīng)轉(zhuǎn)換為a
// = b
// 解法2：
// a = a ^ b
// = (a ^ b) ^ (b ^ a ^ b) // 帶入①式和②式
// = (a ^ a) ^ (b ^ b) ^ b
// = 0 ^ 0 ^ b
// = b
3. 交換符號
取反+1
理解：
負(fù)數(shù)轉(zhuǎn)正數(shù)：負(fù)數(shù)的補(bǔ)碼轉(zhuǎn)源碼，除符號位取反加一，變成負(fù)數(shù)的源碼。所以負(fù)數(shù)取反加一就是符號位一起取反，變成正數(shù)的源碼，也就是正數(shù)的補(bǔ)碼。
正數(shù)轉(zhuǎn)負(fù)數(shù)：正數(shù)的符號位取反變成負(fù)數(shù)的源碼，負(fù)數(shù)除符號位取反加一，變成負(fù)數(shù)的補(bǔ)碼；
SignedByte a = 0b00001011;
SignedByte b = 0b11110101;
NSLog(@"a = %d, b = %d", a, b);
3. 求絕對值
正數(shù)返回本身，負(fù)數(shù)返回取反+1
/** 求絕對值 */
- (int)abs:(int)num {
int absNum;
// 獲取符號位，比如int為4字節(jié)，32位，右移31位獲取符號位
int bits = sizeof(int) * 8 - 1;
// 符號位為0代表是整數(shù)，反之是負(fù)數(shù)，取反加一得到正數(shù)
absNum = ((num >> bits) & 1) == 0 ? num : ~num + 1;
return absNum;
}
四. 四則運(yùn)算
1. 加法
加法可以分解成求'和'、'進(jìn)位'兩個(gè)部分，'和'要留在當(dāng)前位，'進(jìn)位'要加到下一位。
二進(jìn)制的加法有兩個(gè)特點(diǎn)：
-
位的異或運(yùn)算和求'和'的結(jié)果一致
異或 1 ^ 1 = 0 1 ^ 0 = 1 0 ^ 0 = 0 求和 1 + 1 = 0 1 + 0 = 1 0 + 0 = 0 -
位的與運(yùn)算跟求'進(jìn)位'的結(jié)果一致
位與 1 & 1 = 1 1 & 0 = 0 0 & 0 = 0 進(jìn)位 1 + 1 = 1 1 + 0 = 0 0 + 0 = 0
1.1 二進(jìn)制個(gè)位數(shù)加法
/** 二進(jìn)制個(gè)位數(shù)加法 */
- (int)addA:(int)a andB:(int)b {
// 記錄求和
int sum = a ^ b;
// 記錄進(jìn)位
int carry = (a & b) << 1;
// 位運(yùn)算，實(shí)現(xiàn)各位求和
return sum ^ carry;
}
1.2 二進(jìn)制多位數(shù)加法
非遞歸：
/** 二進(jìn)制多位數(shù)加法，非遞歸 */
- (int)addA:(int)a andB:(int)b {
int sum, carry;
// 保證加數(shù)為0，相加不存在進(jìn)位，此時(shí)的異或就是真正的求和
while (b != 0) {
// 記錄下各位的求和
sum = a ^ b;
// 記錄下各位的進(jìn)位
carry = (a & b) << 1;
// 求和賦值為被加數(shù)
a = sum;
// 進(jìn)位賦值為加數(shù)
b = carry;
}
return a;
}
遞歸：
/** 二進(jìn)制多位數(shù)加法，遞歸 */
- (int)addA:(int)a andB:(int)b {
// 判斷遞歸終止條件
if (b == 0) {
// 當(dāng)進(jìn)位為0時(shí)，求和就是兩數(shù)的和
return a;
}
// 記錄下各位的求和
int sum = a ^ b;
// 記錄下各位的進(jìn)位
int carry = (a & b) << 1;
// 調(diào)用當(dāng)前函數(shù)
return [self addA:sum andB:carry];
}
2. 減法
減去一個(gè)數(shù)等于加上這個(gè)數(shù)的負(fù)數(shù)。
/** 二進(jìn)制多位數(shù)減法 */
- (int)a:(int)a minusB:(int)b {
return [self addA:a andB:~b + 1];
}
3. 乘法
axb相乘等于b個(gè)a相加
/** 兩數(shù)相乘 */
- (int)multiplyA:(int)a andB:(int)b {
// 乘積
int product = 0;
// 兩數(shù)相乘的結(jié)果是否為負(fù)數(shù)
BOOL isNegativeNum = NO;
// 判斷兩數(shù)相乘的結(jié)果是否為負(fù)數(shù)
if ([self isNegativeNumber:a]) {
isNegativeNum = !isNegativeNum;
}
if ([self isNegativeNumber:b]) {
isNegativeNum = !isNegativeNum;
}
// 求和，b個(gè)a相加
for (int i = 0; i < [self abs:b]; i++) {
product = [self addA:product andB:[self abs:a]];
}
// 如果乘積結(jié)果是負(fù)數(shù)，乘積取反
if (isNegativeNum) {
product = [self addA:~product andB:1];
}
return product;
}
/** 獲取該數(shù)的絕對值 */
- (int)abs:(int)num {
int absNum;
// 負(fù)數(shù)取反，正數(shù)返回本身
absNum = [self isNegativeNumber:num] ? [self addA:~num andB:1] : num;
return absNum;
}
/** 判斷該數(shù)字是否為負(fù)數(shù) */
- (BOOL)isNegativeNumber:(int)num {
// 獲取右移位數(shù)，比如int為4字節(jié)，32位，右移31位獲取符號位
int bits = 31;
// 獲取符號位，符號位為1代表負(fù)數(shù)，反之為正數(shù)
BOOL isNegativeNumber = ((num >> bits) & 1) == 1 ? YES : NO;
return isNegativeNumber;
}
4. 除法
被除數(shù)除以除數(shù)，相當(dāng)于被除數(shù)一直減去除數(shù)，直到不夠減為止，做減法的次數(shù)就是商。
/** 除法 */
- (int)divideA:(int)a byB:(int)b {
// 被除數(shù)和除數(shù)的賦值
int dividend = a;
int divisor = b;
// 商，即做減法的次數(shù)
int times = 0;
// 兩數(shù)相除的結(jié)果是否為負(fù)數(shù)
BOOL isNegativeNum = NO;
// 判斷兩數(shù)相除的結(jié)果是否為負(fù)數(shù)
if ([self isNegativeNumber:dividend]) {
isNegativeNum = !isNegativeNum;
}
if ([self isNegativeNumber:divisor]) {
isNegativeNum = !isNegativeNum;
}
// 當(dāng)被除數(shù)小于除數(shù)時(shí)，代表不夠除了
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++;
}
// 商為負(fù)數(shù)的話取反
if (isNegativeNum) {
times = [self addA:~times andB:1];
}
return times;
}
