新乡商城网站建设价格,杭州做网站优化,wordpress图集功能,wordpress树形导航注册1.位实现加法和乘法
在计算机中#xff0c;位运算的效率要比加减乘除的效率更高#xff0c;因此在高性能软件中源码中大量使用#xff0c;计算机里各种运算基本上都是位运算。
学习下面内容之前建议先学习位运算规则#xff1a;算法通关村十一关 | 位运算的规则_我爱学算…1.位实现加法和乘法
在计算机中位运算的效率要比加减乘除的效率更高因此在高性能软件中源码中大量使用计算机里各种运算基本上都是位运算。
学习下面内容之前建议先学习位运算规则算法通关村十一关 | 位运算的规则_我爱学算法的博客-CSDN博客
1.1 位运算实现加法 题目LeetCode371 给你两个整数a和b不使用运算符 和 -计算并返回两整数之和。 示例1 输入 a 1b 2 输出3 我们先看两个二进制位相加的情况 0 0 0 0 1 1 1 0 1 1 1 0发生进位应该是10 相加的时候我们需要考虑两个问题进位部分是什么不进位部分是什么从上面的情况可以看到对于a和b两个数不进位部分的情况是相同为0不同为1就是a⊕b。
对于进位部分只有a和b都是1的时候才会进位而且进位只能是1这不就是ab1吗然后位数由一位变成两位只需将1手动移位一下就好也就是a b 1。 结论 不进位部分用a⊕b计算 是否进位以及进位的值使用a b 1计算只有结果为1的时候才会出现进位 异或不用考虑是否进位 我们可以将整数a和b的和拆分成a和b的无进位加法结果与进位结果的和 //位运算加法public int getNum(int a, int b){while (b ! 0){int sign (a b) 1;a a ^ b;b sign;}return a;}
注意需要思考的是a异或于移位之后的a b的情况 第一次并没有考虑进位第二次才进行进位
2.2 递归乘法 题目LeetCode里面面试08.05 递归乘法写一个递归函数不使用* 运算符实现两个整数相乘。可以使用加号、减号、位移但要吝啬一些 示例1 输入A 1B 10 输出10 如果使用累加来计算效率太低还是要用移位运算。
首先求得A和B的最大值和最小值对其中的最小值当作乘数为什么选最小值当乘数因为可以计算的更少将其拆分成2的幂的和比如12用二进制表示1100即1000 0100。0 * 2^0 0 * 2^1 0 * 2^2 1 * 2^3,和0 * 2^0 0 * 2^1 1 * 2^2 0 * 2^3的和。 13 * 12 13 * ( 8 4) 13 * 8 13 * 4 (13 3) (13 2); 代码实现 //位运算乘法public int multiply2(int a ,int b){int min Math.min(a,b);int max Math.max(a,b);int ans 0;for (int i 0; min ! 0 ; i) {//位为1的时候累加if ((min 1) 1){ans max i;}min 1;}return ans;}
