每天一道LeetCode----位运算实现加减乘除四则运算

Divide Two Integers

原题链接Divide Two Integers

意思是重新实现除法运算，这里不要复习一下用位运算实现加减乘除四则运算
C++学习笔记—–用位运算实现加减乘除以前也有记录过，这里主要是复习，另外，除法需要优化，在这里实现

加法

通过异或运算和与运算实现
两个二进制数相加，异或运算的结果是不考虑进位时的结果
两个二进制数相加，与运算的结果是对应为是否有进位

0101 + 0001 = 01100101 ^ 0001 = 0100
0101 & 0001 = 0001
异或结果表明，如果不考虑进位，那么结果为0100
与运算结果表明，最低位需要向次低位进1算式改为0100 + 00010（与结果左移一位，将进位加到高位上）
计算结果0101

代码实现

int add(int a, int b)
{return b == 0 ? a : add(a ^ b, (a & b) << 1);
}

减法

同加法，减去一个数等于加一个数的相反数

int negative(int n)
{return add(~n, 1);
}int sub(int a, int b)
{return add(a, negative(b));
}

乘法

笔算二进制乘法

        0101    a×   0110    b----------------
        000001010101+ 0000-------------
     00011110

b的每一位乘a，左移一定位数后加到结果上，代码把逻辑实现出来就可以了。可以在代码中每加一次结果就将a左移一位，就不需要每次算完都左移。最好考虑符号问题，乘之前都转为正数

int get_sign(int n)
{if(n >> 31)return 1;elsereturn 0;
}int positive(int n)
{if(n >> 31)return negative(n);elsereturn n;
}int multi(int a, int b)
{bool be_negative = false;if(get_sign(a) ^ get_sign(b))be_negative = true;unsigned int x = positive(a);unsigned int y = positive(b);int n = 0;while(y | 0){if(y & 1)n = add(n, x);x = x << 1;y = y >> 1;}return be_negative ? negative(n) : n;
}

除法

第一种方法，每次循环都是a-b，看能减多少次，如果a很大b很小，效率比较低
第二种方法，从最大倍数n开始，看看a / n 是否大于b，如果大，将n加到结果上，然后缩小倍数继续循环

int div(int a, int b)
{bool be_negative = false;if(get_sign(a) ^ get_sign(b))be_negative = true;unsigned int x = positive(a);unsigned int y = positive(b);int res = 0;int i = 31;while(i >= 0){if((x >> i) >= y){res = add(res, 1 << i);x = sub(x, y << i);}/* 也可以在else里，因为这里是int型，最大也就1 << 31倍 */i = sub(i, 1);}/* 题中要求溢出时为INT_MAX，实现时可以让它溢出 *///if(res < 0 && !be_negative)//    return INT_MAX;return be_negative ? negative(res) : res;}

完整测试程序如下

#include 
#include 
#include using namespace std;class Solution {
public:int add(int a, int b){return b == 0 ? a : add(a ^ b, (a & b) << 1);}int sub(int a, int b){return add(a, negative(b));}int get_sign(int n){if(n >> 31)return 1;elsereturn 0;}int negative(int n){return add(~n, 1);}int positive(int n){if(n >> 31)return negative(n);elsereturn n;}int multi(int a, int b){bool be_negative = false;if(get_sign(a) ^ get_sign(b))be_negative = true;unsigned int x = positive(a);unsigned int y = positive(b);int n = 0;while(y | 0){if(y & 1)n = add(n, x);x = x << 1;y = y >> 1;}return be_negative ? negative(n) : n;}int div(int a, int b){bool be_negative = false;if(get_sign(a) ^ get_sign(b))be_negative = true;unsigned int x = positive(a);unsigned int y = positive(b);int res = 0;int i = 31;while(i >= 0){if((x >> i) >= y){res = add(res, 1 << i);x = sub(x, y << i);}i = sub(i, 1);}//if(res < 0 && !be_negative)//    return INT_MAX;return be_negative ? negative(res) : res;}
};int main()
{Solution s;srand(unsigned(time(NULL)));int maxIteration = 10000;while(maxIteration--){int a = rand() - INT_MAX / 2;int b = rand() - INT_MAX / 2;if(s.add(a, b) != a + b)cout << "error : " << a << " + " << b << endl;if(s.sub(a, b) != a - b)cout << "error : " << a << " - " << b << endl;if(s.multi(a, b) != a * b)cout << "error : " << a << " * " << b << " " << s.multi(a, b) << " " << a * b << endl;if(b != 0 && s.div(a, b) != a / b)cout << "error : " << a << " / " << b << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！