比较两个数中较大的数

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
public class GetMax {

    /*
    保证参数n 不是n就是1 1->0 0->1
     */
    public int flip(int n) {
        return n ^ 1;
    }

    /*
    n是非负数返回1， n是负数返回0
     */
    public int sign(int n) {
        return flip((n >> 31) & 1);
    }

    // 不考虑溢出
    public int getMax1(int a, int b){
        int c = a - b; //可能会溢出
        int scA = sign(c); // a-b为非负 scA为1，否则是0
        int scB = sign(scA);
        // scA为0 scb必为1；scA为0，scb为0
        return a * scA + b * scB;
    }

    // 考虑溢出
    public int getMax2(int a, int b){
        int c = a - b; //可能会溢出
        int sa = sign(a);
        int sb = sign(b);
        int sc = sign(c);
        int diffSab = sa ^ sb; //a和b符号不一样为1，一样为0
        int sameSab = flip(diffSab);  //a和b符号一样为1，不 一样为0
        /*
            返回a
                a和b符号相同 a-b >=0
                a和b符号不相同 a > 0
         */
        int returnA = diffSab * sa + sameSab * sc;
        int returnB = flip(returnA);
        return a * returnA + b * returnB;
    }
}

判断一个32位正数是不是2的幂、四的幂

对2的幂来说，2进制上只有1位是1

1
2
3
2的0次方	0... 01
2的1次方	0... 10
2的2次方	0... 100

X只有一个1， X-1 会把唯一的1打撒

1
2
3
2的0次方-1	 	0... 00
2的1次方-1	 	0... 01
2的2次方-1		0... 011

判断一个数是不是2的幂通过 X&(X-1)==0

对4的幂来说，它的1在奇数位上

1
2
3
4的0次方	0... 01
4的1次方	0... 100
4的2次方	0... 10000

判断一个数是不是4的幂，先判断它是不是2的幂，然后 X & 010101…01 不等于0

代码如下

1
2
3
4
5
6
7
8
9
// X只有一个1， X-1 会把唯一的1打撒 X&(X-1)==0
public boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

// X只有一个1， X-1 会把唯一的1打撒 X&(X-1)==0
public boolean isPowerOfFour(int n) {
    return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
}

给定两个有符号32位整数a和b,不能使用算术运算符，分别实现a和b的加、减、乘、除运算

如果给定a、b执行加减乘除的运算结果就会导致数据的溢出，那么你实现的函数不必对此负责,除此之外请保证计算过程不发生溢出

加法

先进行异或运算，异或是无进位相加，再进行与运算，与运算是进位信息，将它左移一位，得到2个数，将这2个数相加，也是是重复以上操作，直到得到进位信息的全是0，无进位相加就是最后结果。

相减

a-b = a+(-b) , -b这么求？相反数 就是取反加1

相乘

二进制乘法与十进制乘法相同

1
2
3
4
5
6
7
8
   100
   101
  ----
   100  // 1与上面与
  000
 100	// 1与上面与	
-------
 10100

相除

a/b，就是讲b向左移动刚好被a最大相减的位置上

1
2
3
4
5
6
7
8
9
10100 / 100
把100 左移2位 记为100
  10100
- 10000
-------
  00100
-   100	不左移 记为1

最终结果为 100 + 1 = 101
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
// a+b保证不溢出
// leetcode 371 两数相加无+-
public int add(int a, int b) {
    int sum = a;
    while (b != 0) {
        sum = a ^ b;    // 无进位加
        b = (a & b) << 1;  // 进位信息
        a = sum;
    }
    return sum;
}

// 相减 a-b = a + (-b)
public int minus(int a, int b) {
    return add(a, negNum(b));
}

// 相反数 就是取反加1
private int negNum(int n) {
    return add(~n, 1);
}

// 相乘
public int multi(int a, int b) {
    int res = 0;
    while (b != 0) {
        if ((b & 1) != 0) { // 从最后一位开始计算
            res = add(res, a);
        }
        a <<= 1;
        b >>>= 1;
    }
    return res;
}

// 相除
public 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 = 31; i > -1; i = minus(i, 1)) {
        // 已经到最大相除的位置 y相左移可能会溢出
        if ((x >> i) >= y) {
            res |= (1 << i);
            x = minus(x, y << i);
        }
    }
    return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
}

public int divide(int a, int b) {

    
    
    if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
        return 1;
    } else if (b == Integer.MIN_VALUE) { // a和b不都是最小值
        return 0;
    } else if (a == Integer.MIN_VALUE && b < 0){
        return Integer.MAX_VALUE;
    } else if (a == Integer.MIN_VALUE) {
        int res = div(add(a, 1), b);
        return add(res, div(minus(a, multi(res, b)), b));
    } else {
        return div(a, b);
    }

}

private boolean isNeg(int n) {
    return n < 0;
}