位运算/实现加减乘除(leetcode)

学习笔记

leetcode试题地址：https://leetcode.com/problems/divide-two-integ

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
public class Leetcode01_divide_two_integers {

    // 不能出现加号
    public static int add(int a, int b) {
        int sum = a;
        // 直到进位信息变为0 ，返回无进位相加信息就是答案
        while (b != 0) {
            // 无进位相加的信息
            sum = a ^ b;
            // 进位信息 b-> b`
            b = (a & b) << 1;
            // a-> a`
            a = sum;
        }
        return sum;
    }

    // 相反数
    public static int negNum(int n) {
        return add(~n, 1);
    }

    // a-b ， a加上b的相反数
    public static int minus(int a, int b) {
        return add(a, negNum(b));
    }

    //乘法  小学乘法运算
    // a = 0110
    // b = 0111
    // ans = 0110 + 01100(补0) + 011000（补0）
    public static int multi(int a, int b) {
        int res = 0;
        while (b != 0) {
            // 末尾有1 ，a算到结果里去
            if ((b & 1) != 0) {
                res = add(res, a);
            }
            // a左移一位
            a <<= 1;
            // b不带符号右移一位
            // b>> 1 表示符号位补 ， b>>>1 表示用0来补
            b >>>= 1;
        }
        return res;
    }

    //是不是负数
    public static boolean isNeg(int n) {
        return n < 0;
    }


    // a / b = c
    // 假设 b = 01110 ，c = 00110
    // a = b * 2^1 + b* 2^2
    // a = b << 1 + b << 2
    // c 在第3位是1 ，第1位是1，其余位0
    // a - 2^ 2 = a`
    // a` - 2^1 = a``  直到 - - - > a```` = 0

    public static int div(int a, int b) {
        int x = isNeg(a) ? negNum(a) : a;
        int y = isNeg(b) ? negNum(b) : b;
        int res = 0;
        for (int i = 30; i >= 0; i = minus(i, 1)) {
            if ((x >> i) >= y) {
                res |= (1 << i);
                x = minus(x, y << i);
            }
        }
        return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
    }


    // 最小值无法取绝对值
    public static int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
            return 1;
        } else if (b == Integer.MIN_VALUE) {
            return 0;
        } else if (a == Integer.MIN_VALUE) {
            if (b == negNum(1)) {
                // leetcode约定， 理论上得到max +1
                return Integer.MAX_VALUE;
            } else {
                // a 加一个1 得到 一个结果
                int c = div(add(a, 1), b);
                // c * b = d , 比较a和d差多少，用a-d div  b 得到另一个结果， 两者结果相加，相当于补偿了一次。
                return add(c, div(minus(a, multi(c, b)), b));
            }
        } else {
            return div(a, b);
        }
    }

}