复习 ---- 位运算,乘除与移位
位运算
且 & 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次溢出抵消符号变化。
使用左移和+做乘法时,每次相加后检查符号位改变是可以的。