复习 ---- 位运算,乘除与移位

位运算

且 &  Bitwise AND

按位且。向右对其,对其后两位都在且两位都为1的时候才为1。

例:1110 & 0001 = 0000,1111 & 1101 = 1101, 1010 & 1001 = 1000

常见用途:掩码,取某个数第n位(& 除了第n位是1,其他都是0的数,然后除以n个2), 判断一个数的奇偶(&1==1是奇数)

或 |  Bitwise OR

按位或。向右对其,对其后有一位为1就为1

例:0000|1111 = 1111, 0101 & 1010 = 1111,0010 & 1010 = 1010

非 ~  Bitwise Complement/NOT

按位取反

例: ~0000 = 1111,  ~1010 = 0101, ~1110 = 0001

注意:在大多语言的大多数据类型里,数都不只4位,高位的0取非后都会变成1

如,java中:

1: 00000000000000000000000000000001

~1(-2): 11111111111111111111111111111110

1000: 00000000000000000000001111101000

~1000(-1001): 11111111111111111111110000010111

public static void printAllBits(int t){
	System.out.println(t);
	int[] res = new int[32];
	for(int i = 0; i<32; i++){
		res[i] = t&1; // 取末位
		t>>=1; // 右移
	}
	for(int i=31; i>=0; i--){ //从高位开始打印
		System.out.print(res[i]);
	}
	System.out.println();
}

异或 ^ Bitwise XOR

按位异或。向右对其,对其的两位不同时取1,相同时取0

例:1111^0000 = 1111,  1010^0001 = 1011,  0001^0101 = 0100

常见用途:抵消相同的数,判断两数符号是否相同(异或后看符号位)

乘除和位移

十进制和二进制

二进制:11101 即 1*24 + 1*23 + 1*22 + 0*21 + 1*20

十进制: 24 + 23 + 22 + 0 + 20 = 16+8+4+0+1 = 29

乘法和左移

例:29 (11101) * 4 (10)

= (1*24 + 1*23 + 1*22 + 0*21 + 1*20)* 22

= (1*26 + 1*25 + 1*24 + 0*23 + 1*22) + (0*21 + 0*20)  

(即二进制 1110100,11101左移两位)

所以,a * 2i == a<<i

例: 29 (11101) * 7(111)

= (1*24 + 1*23 + 1*22 + 0*21 + 1*20) * (1* 22 + 1* 21 + 1* 20)

= (29<<2) + (29<<1) + 29

public Class MultiplyByShift {
    public static int multiply(int a, int b){
    	// 假设没有溢出
        
        int res = 0;
        boolean negative = (a^b)<0; // 异或后只看最高位(符号位)
        // 若a,b中只有一个负数,则最高位0^1 = 1,结果为负
        
        int m = a<0? -a: a;
        int n = b<0? -b: b;
        
        int i = 0;
        
        while(n>0){
            int t = n & 1; // n的最后一位
            n >>= 1;
            if(t==1) res += (m<<i);
            i++;
        }
        
        return negative? -res: res;
    }
}

除法和右移

例:101(1100101)/4(10)

= (1*26 + 1*25 + 0*24 + 0*23 + 1*22 + 0*21 + 1*20) / 22

= 1* 24 + 1*23 + 0*22 + 0*21 + 1*20 + 0*2-1 + 0*2-2

在整数范围为 1* 24 + 1*23 + 0*22 + 0*21 + 1*20 即11001

所以a/2b = a>>b

通过位移来做除法时,如果除数不是2的幂,我们可以依次试探每一位

例:101(1100101)/13(1101)

13(1101)右移1位,26(11010)<=101;

右移2位, 52(110100)<=101;

右移3位,104>101;

所以结果第3位是0,第2位是1

把101拆成 (1*13*22) + 49,继续试探49

49 = (1*13*21)+ 23,  23 = (1*13*20 +22)

所以101/13 = 二进制的111,即7

public class DivideByShift {
    public static void main(String[] args) {
        System.out.println(divide(1234567,123)+","+1234567/123);
    }
    
    public static int divide(int a, int b){
    	// 假设没有溢出
        boolean negative = (a^b)<0;
        int m = a<0? -a:a;
        int n = b<0? -b:b;
        
        int res = 0;
        
        while(m>=n){
            int i=0;
            while((n<<i) <=m) i++;
            i--;
            res += (1<<i);
            m -= (n <<i);
        }
        
        return negative? -res: res;
    }
}

谈谈溢出(Java的情况)

Java的Integer的取值范围是-2147483648到2147483647。

向下溢出

Integer.MIN_VALUE,即-2147483638,是个比较烦的数,因为取负它会溢出。Integer.MIN_VALUE = -Integer.MIN_VALUE = -2147483638.... 所以想要存它的绝对值,就只好用Long了。

正确的得到Integer.MIN_VALUE的办法:

Long abs = -(Long)Integer.MIN_VALUE; // 一定要先转换成Long再取负

Java里,负数移位不会变成正数,但是可能变成0

向上溢出

使用*做乘法时,先乘再判断是否符号变化是不靠谱的,因为乘一次可能产生2次溢出抵消符号变化。

使用左移和+做乘法时,每次相加后检查符号位改变是可以的。