在进入编码前,我们先补充位运算的知识:
& :与门,两个位都为1时,结果才为1;
| : 或门,两个位都为0时,结果才为0;
^: 异或门,两个位相同为0,相异为1;
~: 取反符号,二进制数0变1,1变0;
<< : 左移符号,各二进位全部左移若干位,高位丢弃,低位补0;
>> (>>>): 带(不带)符号位右移符号,各二进位全部右移若干位,对无符号数,高位补0,有符号数,各编译器处理方法不一样,有的补符号位(算术右移),有的补0(逻辑右移);
加法代码:public static int add(int a, int b){
int sum = a; while ( b != 0){ sum = a ^ b;//没有进位相加的结果 b = (a & b)<< 1;//进位 a = sum; } return sum; } 解释:在二进制中我们可以使用异或门(^)得到两个数相加得到的情况,但是此时两个数没有加上进位数;两个数的进位数可以通过与门(&)得到,所以每一次相加的结果都要加上进位数,一直加到没有进位数为止。 减法代码:
/相反数 public static int negNum(int a){ return add(~a,1); } public static int sub(int a,int b){ return add(a,negNum(b)); } 解释:通过加法我们可以知道,a - b = a + (- b),所以需要先得到b的相反数,但是因为我们没有-号,所以需要让b取反加一实现相反数。 乘法代码:
public static int multi(int a,int b){ int ans = 0; while (b != 0){ if ((b & 1) == 1){ ans = add(ans,a); } a <<= 1; b >>>= 1; } return ans; } 解释:a * b 可以解释为 (a*2^1*1)+(a*2^2*0)+(a*2^3*1)...........【即:将b以二进制的形式表示】,则每次只需要判断b的最后一位是否存在就可以判断这个a需要乘的2进制位,然后将结果加上a; 每处理一次循环体,需要让a左移一位保证a多乘一个2,让b不带符号位又移动一位,判断当前位置是否需要乘,带符号位是为了避免b永远不能等于0的问题。 除法代码:
//判断是否为负数 public static boolean isNeg(int a){ return 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 result = 0; for (int i = 30; i >= 0 ;i = sub(i,1)) { if ((x >> i) >= y){ result = add(result,(1 << i)); } } return isNeg(a) ^ isNeg(b) ? negNum(result) : (result); } //实现任何数字相除的情况 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)){ return Integer.MAX_VALUE; }else { int c= div(add(a, 1),b);//最小值加一取反后除的值 //对上面的值还原,找出原数与上面的数之间的差值除以b,将除以b的值加上原数add的值得到最后值 return add(add, div(sub(a, multi(c, b)), b)); } }else{ return div(a,b); } } 解释:关于除法,我们可以让被除数左移到最接近除数的位置,记录下当前移动的数字,然后将让除数减去被除数移动后的值并赋值给除数,让1左移同样的位置加到结果里,循环得到最后的结果。 但这样可能会出现越界到符号位的问题,所以我们使用右移策略,从第三十位开始往右移动,若出现了比被除数大的数则记录下左移位数,结果加上数字1向左移动记录下来的左移位数。 处理极限值的情况: 因为Integer类型最小值没有相反数,所以需要单独拿出来处理。先让它加上1然后进入除法算法,得到的值是模糊的除法值不准确,所以需要再将结果c乘以被除数还原,用除数(a)减去c乘以b的结果得到两者差值,再用差值除以被除数加上c得到准确结果并返回。 以上就是我个人对位运算实现计算器原理的理解,谢谢大家的观看,欢迎留言。