前言
位运算是基于整数的二进制表示进行的运算。大部分情况下，位运算的运算效率都是很快的。
与、或、异或
与（ & ）或（ | ）和异或（ ^ ）这三者都是两数间的运算.
它们都是将两个数作为二进制数，对二进制表示中的每一位逐一运算。
两次异或同一个数最后结果不变，即 a^b^b = a
取反
取反（ ~ ）是对一个数进行的计算，即单目运算。
参与运算的数以补码方式出现。
取反会把数字的补码中的 0 和 1 全部取反（0 变为 1，1 变为 0）
左移和右移
位运算的应用
很多大厂的算法题目，都会考到位运算的应用，大家刷过 leetcode ，应该也有印象。
以下示例代码使用 swift
位运算实现加减乘除
1
2
3
| func add(a: Int, b: Int) -> Int {
return (b != 0) ? add(a: a ^ b, b: (a & b ) << 1) : a
}
|
1
2
3
| func subtraction(a: Int, b: Int) -> Int {
return add(a: a, b: add(a: ~b, b: 1))
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| func multiply(a: Int, b: Int) -> Int {
var multiplicand = a < 0 ? add(a: ~a, b: 1) : a
var multiplier = b < 0 ? add(a: ~b, b: 1) : b
var product = 0
while multiplier > 0 {
if (multiplier & 0x1) > 0 {
product = add(a: product, b: multiplicand)
}
multiplicand = multiplicand << 1
multiplier = multiplier >> 1
}
if (a ^ b) < 0 {
product = add(a: ~product, b: 1)
}
return product
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| func divide(a: Int, b: Int) -> Int {
var dividend = a < 0 ? add(a: ~a, b: 1) : a
let divisor = b < 0 ? add(a: ~b, b: 1) : b
var invert = 2
while (dividend != 0) {
invert |= dividend & 0x1
invert = invert << 1
dividend = dividend >> 1
}
var quotient = 0
var remainder = 0
while invert > 1 {
remainder = remainder << 1
remainder |= invert & 0x1
invert = invert >> 1
quotient = quotient << 1
if remainder >= divisor {
quotient |= 0x1
remainder = subtraction(a: remainder, b: divisor)
}
}
if (a ^ b) < 0 {
quotient = add(a: ~quotient, b: 1)
}
return quotient
}
|
参考：
用基本位运算实现加减乘除
位运算实现加减乘除四则运算
位运算交换两数
位运算交换两数可以不需要第三个临时变量，虽然普通操作也可以做到，但是没有其效率高
1
2
3
4
5
6
7
8
9
| func swap(a: inout Int, b: inout Int) {
a ^= b
b ^= a
a ^= b
}
var a = 1, b = 2
swap(&a, &b)
print(a)
print(b)
|
位运算判断奇偶数
只要根据数的最后一位是 0 还是 1 来决定即可，为 0 就是偶数，为 1 就是奇数
1
2
3
4
| let a = 2
if 0 == (a & 1) {
print("偶数")
}
|
还有很多，可以去这儿继续学习，位运算有什么奇技淫巧？
