按位实现加减乘除 四则运算
分类:剑指offer
二进制位运算
不使用+-*/四则运算符,实现两个数的四则运算。
1. 加
用二进制位实现两个数之间的加法。不考虑2个数相加的和溢出问题。 如 9+15=24 1001 + 1111,由于二进制 0+0=0,1+0=1, 0+1=1, 1+1=0, 可以发现是异或运算,而产生进位,则只有1 ,1相加,,即与运算。
int add(int nums1, int nums2) {if (nums1 == 0 || nums2 == 0)return (nums1 == 0) ? nums2 : nums1;int sum = 0, carry = 0;do {sum = nums1 ^ nums2;carry = (nums1 & nums2) << 1; // 进位左移一位nums1 = sum;nums2 = carry;} while (nums2);return sum;}2. 减
a-b = a + (-b),只需要实现负数操作,即求补码:按位取反 + 1
int negtive(int num) {return add(~num, 1);}add(nums1, negtive(nums2));}3. 乘
如十进制中的乘法,逐位乘。 求 2 个正整数的乘积
int multi(int nums1, int nums2) {if (nums1 == 0 || nums2 == 0)return 0;int result = 0;while (nums2) {if (nums2 & 0x01) { // 乘数的最后1位result = add(result, nums1);}nums1 <<= 1; // 被乘数左移1位nums2 >>= 1; // 取乘数的下一位}return result;}4. 除
求两个正整数相除的商。 乘的逆运算。 除法就是由乘法的过程逆推,x/y的过程: x依次减掉(如果x够减的)y^(2^31),y^(2^30),…y^8,y^4,y^2,y^1。减掉相应数量的y就在结果加上相应的数量。
int division(int nums1, int nums2) {if (nums1 == 0 || nums2 == 0)return 0;const int BITS = sizeof(nums1)*8;int result = 0;for (int i = BITS-1; i >= 0; i–) {// 之所以不使用 nums2 << i 与 nums1 比较,是为了防止溢出if ((nums1 >> i) > nums2) {result = add(result, 1 << i);nums1 = sub(nums1, nums2 << i);}}return result;}
参考:
版权声明:本文为博主原创文章,未经博主允许不得转载。
上一篇45 – 圆圈中最后剩下的数字下一篇不使用 乘除、循环和判断 语句实现 1+…+n
顶0踩0
“过去酒逢知已千杯少,现在酒逢千杯知已少”。