前置知识：二进制和位运算
特别提醒：Python 的同学实现位运算的题目需要特别注意，需要自己去手动处理溢出和符号扩展等问题，比如：
(n << shift_amount) & 0xFFFFFFFF（Python 溢出会自动升位：）
位运算实现加减乘除，过程中不能出现任何算术运算符
加法
a+b = a和b无进位相加 + a+b的进位信息
直到进位消失// 加法
func add(a, b int) int {
ans := a
for b != 0 { // 没有进位了，说明加完了
ans = a ^ b // ans: 无进位相加
b = (a & b) << 1 // b: 进位信息
a = ans
}
return ans
}减法
a-b = a + (-b)
= a + (^b+1)// 减法
func minus(a, b int) int {
return add(a, neg(b)) // a-b == a+(-b)
}
// 取相反数
func neg(n int) int {
return add(^n, 1) // -n == ^n+1
}乘法
回想小学时候怎么学的乘法，除此之外没别的了
十进制：
57
x 21
------
57
114
------
1197
二进制：
1011
x 1010
----------
1010
1010
0000
1010
----------
1101110const (
INT_BIT_COUNT = int(unsafe.Sizeof(int(0))) * 8 // int 占的位数
)
// 乘法
func multiply(a, b int) int {
ans := 0
for b != 0 { // 还有乘数
if b&1 != 0 { // 考察 b 当前最右的状态
ans = add(ans, a)
}
a <<= 1
b = unsignedRightShift(b, 1) // b >>>= 1
}
return ans
}
// 无符号右移
// n >>> bit
func unsignedRightShift(n int, bit int) int {
// 1<<(32-i) - 1: 低位一共 32-i 位都是 1，高位一共 i 位都是 0
return (n >> bit) & minus(1<<minus(INT_BIT_COUNT, bit), 1)
}无符号右移
Go 中没有无符号右移，两种方法解决：
法一：int 转 uint 后进行右移
// 无符号右移
// n >>> bit
func unsignedRightShift(n int, bit int) int {
return int(uint(n) >> bit)
}法二：，其中
const (
INT_BIT_COUNT = int(unsafe.Sizeof(int(0))) * 8 // int 占的位数
)
// 无符号右移
// n >>> bit
func unsignedRightShift(n int, bit int) int {
// 1<<(32-i) - 1: 低位一共 32-i 位都是 1，高位一共 i 位都是 0
return (n >> bit) & (1<<(INT_BIT_COUNT-bit) - 1)
}除法
除法是乘法的逆运算
280 / 25 相当于：
280 = 25*2^3 + 25*2^1 + 25*2^0
所以：先从 25*2^30（为什么不是 25*2^31？因为第 32 位是符号位）开始试是否 <= 剩余值，一直试到 25*2^0
注意：
1. 上面方法的前提是除数和被除数都是非负数，所以如果是负数要先转换为非负数
2. 为了防止溢出，让被除数右移，而不是除数左移// 除法（不要用，有瑕疵）
// 必须保证 a 和 b 都不是整数最小值
func div(a, b int) int {
// a、b 是否异号
// Java 中更方便：a < 0 ^ b < 0
haveOppositeSigns := (a < 0) != (b < 0)
if a < 0 {
a = neg(a)
}
if b < 0 {
b = neg(b)
}
ans := 0
for i := minus(INT_BIT_COUNT, 2); i >= 0; i = minus(i, 1) {
if a>>i >= b { // 不是 a >= b << i，因为 b << i 可能溢出（改变符号位）
ans |= 1 << i
a = minus(a, b<<i)
}
}
if haveOppositeSigns {
return neg(ans)
}
return ans
}因为要先将负数转换为非负数，所以上面的算法中必须保证 a 和 b 都不是整数最小值，因为整数最小值转不成非负数（整数最小值的相反数还是他自己）
需要分类讨论：
a和b都是整数最小：相除为 1a和b都不是整数最小：正常相除a不是整数最小，b是整数最小：相除为 0a是整数最小，b是 -1：相除为整数最小的相反数，溢出导致还是整数最小a是整数最小，b不是 -1 也不是整数最小：- b 为负数：令 ，使其变得不那么小后再除以 b，得到的结果 +1
- b 为非负数：令 ，使其变得不那么小后再除以 b，得到的结果 -1
const (
MIN_INT = math.MinInt // int 最小值
)
// 除法
func divide(a, b int) int {
if a == MIN_INT && b == MIN_INT {
// 情况1：a 和 b 都是整数最小
return 1
}
if a != MIN_INT && b != MIN_INT {
// 情况2：a 和 b 都不是整数最小，那么正常去除
return div(a, b)
}
if b == MIN_INT {
// 情况3：a 不是整数最小，b 是整数最小
return 0
}
if b == neg(1) {
// 情况4：a 是整数最小，b 是 -1，相除为整数最小的相反数，溢出导致还是整数最小
return MIN_INT
}
// 情况5：a 是整数最小，b 不是 -1 也不是整数最小
absB := b
offset := neg(1)
if b < 0 {
absB = neg(b)
offset = 1
}
a = add(a, absB)
return add(div(a, b), offset)
}测试
测试链接：29.两数相除
题目要求：假设我们的环境只能存储 32 位有符号整数，其数值范围是 。本题中，如果商严格大于 ，则返回 ；如果商严格小于 ，则返回
const (
INT_BIT_COUNT = 32
MAX_INT = math.MaxInt32 // 2^31 - 1
MIN_INT = math.MinInt32 // -2^31
)
// 加法
func add(a, b int) int {
ans := a
for b != 0 {
ans = a ^ b
b = (a & b) << 1
a = ans
}
return ans
}
// 减法
func minus(a, b int) int {
return add(a, neg(b))
}
// 取相反数
func neg(n int) int {
return add(^n, 1)
}
// 乘法
func multiply(a, b int) int {
ans := 0
for b != 0 {
if b&1 != 0 {
ans = add(ans, a)
}
a <<= 1
b = unsignedRightShift(b, 1)
}
return ans
}
// 无符号右移
// n >>> bit
func unsignedRightShift(n int, bit int) int {
return (n >> bit) & minus(1<<minus(INT_BIT_COUNT, bit), 1)
}
// 除法（不要用，有瑕疵）
// 必须保证 a 和 b 都不是整数最小值
func div(a, b int) int {
haveOppositeSigns := (a < 0) != (b < 0)
if a < 0 {
a = neg(a)
}
if b < 0 {
b = neg(b)
}
ans := 0
for i := minus(INT_BIT_COUNT, 2); i >= 0; i = minus(i, 1) {
if a>>i >= b {
ans |= 1 << i
a = minus(a, b<<i)
}
}
if haveOppositeSigns {
return neg(ans)
}
return ans
}
// 除法
func divide(a int, b int) int {
if a == MIN_INT && b == MIN_INT {
return 1
}
if a != MIN_INT && b != MIN_INT {
return div(a, b)
}
if b == MIN_INT {
return 0
}
if b == neg(1) { // 题目要求：商严格大于2^31 - 1，则返回2^31 - 1
return MAX_INT
}
absB := b
offset := neg(1)
if b < 0 {
absB = neg(b)
offset = 1
}
a = add(a, absB)
return add(div(a, b), offset)
}备注
上面的实现传入负数也都是正确的，其原因是 二进制优秀的设计