目录
- 前言
- 问题介绍
- 解决方案
- 代码编写
- java语言版本
- c语言版本
- c++语言版本
- 思考感悟
- 写在最后
前言
当前所有算法都使用测试用例运行过,但是不保证100%的测试用例,如果存在问题务必联系批评指正~
在此感谢左大神让我对算法有了新的感悟认识!
问题介绍
原问题
使用位运算完成整数的加减乘除
解决方案
原问题:
加法:
1、二进制数如果不考虑进位,异或运算就是加法结果
2、二进制计算进位的方法,使用&操作可以判断当前位是否进位,因为只有1和1会有进位,也只有1和1&操作是1
3、结合1、2两点,当前两个数a和b的异或结果为无进位相加,两个数的与操作为各位的进位,进位左移一位后加上异或的结果即为最终结果,剩下的操作循环即可,直到没有进位为止
减法:
a-b <=> a + (-b),而负数为正数的补码,剩下的过程和加法相同
乘法:
ab
按照正常的乘法法则计算即可
b中的1的位数代表a左移的位数,剩下的相加即可
除法:
a/b
除法为乘法的反推过程,从最大值开始枚举,首先商的31位为1时,乘b的结果小于a,则当前位商1,如果大于a则继续计算30位…
每商1时,a减去对应b商
代码编写
java语言版本
原问题:
/*** 返回a的补码:除了符号位以外,剩下的位取反+1,* 其实等价于该数的正数连通符号为直接取反+1* @param a* @return*/public static int negNum(int a){return addCp1(~a, 1);}/*** a+b* @param a* @param b* @return*/public static int addCp1(int a, int b) {int sum = a;while (b != 0) {// 无进位结果int x = sum ^ b;// 进位b = (sum & b) << 1;sum = x;}return sum;}/*** a-b* @param a* @param b* @return*/public static int subCp1(int a, int b) {// a+ b的补码即可,取反+1,符号位一起计算return addCp1(a, negNum(b));}/*** 获取当前值的补码* @param a* @return*/public static int negNumCp1(int a) {return addCp1(~a, 1);}/*** a * b* @param a* @param b* @return*/public static int multiCp1(int a, int b) {int res = 0;while (b != 0) {if ((b & 1) != 0) {res = addCp1(res, a);}b >>>= 1;a <<= 1;}return res;}/*** 除法最通常的情况* 但是有个缺陷就是 补码的负数比正数多一个最小值,最小值无法转正数所以当最小值计算时需要另外判断* @param a* @param b* @return*/public static int divCp1(int a, int b) {// 这里去一下符号int x = a < 0 ? negNumCp1(a) : a;int y = b < 0 ? negNumCp1(b) : b;// 商int res = 0;// 因为不能存在算数计算,所以这里--i也用的sub函数减法for (int i = 31; i >= 0; i = subCp1(i, 1)) {// 先尝试除数b左移位i位是否小于等于被除数aif ((x >> i) >= b) {// 说明商1res |= 1 << i;// 减x = subCp1(x, y << i);}}return res;}/*** 考虑了全部情况的除法* @return*/public static int divideCp1(int a, int b) {if (b == 0) {throw new RuntimeException("除数为0");}if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {return 1;}else if (a != Integer.MIN_VALUE && b == Integer.MIN_VALUE) {return 0;}else if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {// 首先计算a+1/bint res1 = divCp1(a+1, b);// 再乘回去求和原来值的差int sub = a - multiCp1(res1, b);// 返回结果,如果偏差值刚好满一个b,那么说明res1 + 1return res1 + sub/b;}else {// 最正常的情况return divCp1(a, b);}}public static void main(String[] args) {System.out.println(add(4, 2));}
c语言版本
正在学习中
c++语言版本
正在学习中
思考感悟
位运算的加减乘除是计算机专业中计算机组成课程中必修部分,现在使用代码实现起来仍然能够感受到二进制的博大精深。
写在最后
方案和代码仅提供学习和思考使用,切勿随意滥用!如有错误和不合理的地方,务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津!