力扣1. A + B 问题（位运算：加减乘除）

63 阅读 0 评论 42 点赞

我是靠谱客的博主儒雅嚓茶，最近开发中收集的这篇文章主要介绍力扣1. A + B 问题（位运算：加减乘除），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

https://www.lintcode.com/problem/a-b-problem/description

给出两个整数 aa 和 bb , 求他们的和。

挑战

显然你可以直接 return a + b，但是你是否可以挑战一下不这样做？（不使用++等算数运算符）

#include "stdafx.h"
class Solution {
public:
/**
* @param a: An integer
* @param b: An integer
* @return: The sum of a and b
*/
int aplusb(int a, int b)
{
// write your code here
int sum = a^b;//不考虑进位
int carry = (a&b) << 1;//考虑进位，左移一
while (carry!=0)
{
a = sum;
b = carry;
sum = a^b;
carry = (a&b) << 1;
}
return sum;
}
};
int main()
{
Solution s;
auto result = s.aplusb(3,7);
return 0;
}

补充知识：

位运算（按位与、按位或、异或）
按位与运算符（&）
参加运算的两个数，按二进制位进行“与”运算。

运算规则：只有两个数的二进制同时为1，结果才为1，否则为0。（负数按补码形式参加按位与运算）

即 0 & 0= 0 ，0 & 1= 0，1 & 0= 0， 1 & 1= 1。

例：3 &5 即 00000011 & 00000101 = 00000001 ，所以 3 & 5的值为1。

按位或运算符（|）
参加运算的两个数，按二进制位进行“或”运算。

运算规则：参加运算的两个数只要两个数中的一个为1，结果就为1。

即 0 | 0= 0 , 1 | 0= 1 ， 0 | 1= 1 , 1 | 1= 1 。

例：2 | 4 即 00000010 | 00000100 = 00000110 ，所以2 | 4的值为 6 。

异或运算符（^）
参加运算的两个数，按二进制位进行“异或”运算。

运算规则：参加运算的两个数，如果两个相应位为“异”（值不同），则该位结果为1，否则为0。

即 0 ^ 0=0 ， 0 ^ 1= 1 ， 1 ^ 0= 1 ， 1 ^ 1= 0 。

例： 2 ^ 4 即 00000010 ^ 00000100 =00000110 ，所以 2 ^ 4 的值为6 。

位运算实现加、减、乘、除运算
1. 加法运算
思路：第一步先不考虑进位，异或相加，对应位相加；第二步只考虑进位，与运算左移一实现进位；第三步判断是否有进位，即判断左移后的值是否为零则结束，不为零则循环。
运算过程：13 + 9 = 22
1、不考虑进位，分别对各位数进行相加，结果为sum：
个位数3加上9为2；十位数1加上0为1；最终结果为12；
位运算异或实现
2、只考虑进位，结果为carry：
3 + 9 有进位，进位的值为10；
位运算与实现，左移一实现进位
3、如果步骤2所得进位结果carry不为0，对步骤1所得sum，步骤2所得carry重复步骤1、 2、3；如果carry为0则结束，最终结果为步骤1所得sum：
这里即是对sum = 12 和carry = 10重复以上三个步骤，(a) 不考虑进位，分别对各位数进行相加:sum = 22; (b) 只考虑进位: 上一步没有进位，所以carry = 0； (c) 步骤2carry = 0，结束，结果为sum = 22
// 递归写法
int add(int num1, int num2){
if(num2 == 0)
return num1;
int sum = num1 ^ num2;
int carry = (num1 & num2) << 1;
return add(sum, carry);
}

// 迭代写法
int add(int num1, int num2){
int sum = num1 ^ num2;
int carry = (num1 & num2) << 1;
while(carry != 0){
int a = sum;
int b = carry;
sum = a ^ b;
carry = (a & b) << 1;
}
return sum;
}

2. 减法运算
思路：第一步，将被减数变成补码形式，取反加一；第二步，减数和被减数取反加一后相加
减法即一个正数加上一个负数
在计算机中，通过补码储存负数。补码就是反码加一

/*
* num1: 减数
* num2: 被减数
*/
int substract(int num1, int num2){
int subtractor = add(~num2, 1);// 先求减数的补码（取反加一）
int result = add(num1, subtractor); // add()即上述加法运算　　
return result ;
}

3. 乘法运算

思路：先处理乘数和被乘数的绝对值的乘积，然后根据它们的符号确定最终结果的符号即可。

求绝对值：a<0?(~a+1):a;

被乘数在前，乘数在后 4 X 2，被乘数是4，乘数是2

其中：乘数和被乘数的绝对值的乘积也可以通过位运算求解

(1) 判断乘数是否为0，为0跳转至步骤(4)
(2) 将乘数与1作与运算，确定末尾位为1还是为0，如果为1，则相加数为当前被乘数；如果为0，则相加数为0；将相加数加到最终结果中；
(3) 被乘数左移一位，乘数右移一位；回到步骤(1)
(4) 确定符号位，输出结果；

int multiply(int a, int b) {　　
//将乘数和被乘数都取绝对值　
int multiplicand = a < 0 ? add(~a, 1) : a; 　　
int multiplier = b < 0 ? add(~b , 1) : b;　　
　
//计算绝对值的乘积　　
int product = 0;　　
while(multiplier > 0) {　　　　
if((multiplier & 0x1) > 0) {// 每次考察乘数的最后一位　　　　
product = add(product, multiplicand);　　　　
} 　　　　
multiplicand = multiplicand << 1;// 每运算一次，被乘数要左移一位　　　　
multiplier = multiplier >> 1;// 每运算一次，乘数要右移一位（可对照上图理解）　　
} 　　
//计算乘积的符号　　
if((a ^ b) < 0) {　　　　
product = add(~product, 1);　　
} 　　
return product;
}

#include "stdafx.h"
class Solution {
public:
/*
* @param n: A long integer
* @return: An integer, denote the number of trailing zeros in n!
*/
long long multiply(long long a, long long b)
{
// write your code here, try to do it without arithmetic operators.
long long nq = a;
long long nh = b;
long long sum = 0;
while (nh != 0)
{
if ((nh&(0x1)) == 1)//乘数末位有一的话，加上被乘数
{
sum = sum + nq;
}
nq = nq << 1;//被乘数左移
nh = nh >> 1;//乘数右移
}
return sum;
}
};
int main()
{
Solution s;
auto result = s.multiply(10, 2);
return 0;
}

4. 除法运算

除法运算很容易想到可以转换成减法运算，即不停的用除数去减被除数，直到被除数小于除数时，此时所减的次数就是我们需要的商，而此时的被除数就是余数。这里需要注意的是符号的确定，商的符号和乘法运算中乘积的符号确定一样，即取决于除数和被除数，同号为证，异号为负；余数的符号和被除数一样。

除数的231,230,...,22,21,2^0倍尝试去减被除数，如果减得动，则把相应的倍数加到商中；如果减不动，则依次尝试更小的倍数。这样就可以快速逼近最终的结果。

2的i次方其实就相当于左移i位，为什么从31位开始呢？因为int型数据最大值就是2^31啊。

int divide_v2(int a,int b) {
// 先取被除数和除数的绝对值
int dividend = a > 0 ? a : add(~a, 1);
int divisor = b > 0 ? a : add(~b, 1);
int quotient = 0;// 商
int remainder = 0;// 余数
for(int i = 31; i >= 0; i--) {
//比较dividend是否大于divisor的(1<<i)次方，不要将dividend与(divisor<<i)比较，而是用(dividend>>i)与divisor比较，
//效果一样，但是可以避免因(divisor<<i)操作可能导致的溢出，如果溢出则会可能dividend本身小于divisor，但是溢出导致dividend大于divisor
if((dividend >> i) >= divisor) {
quotient = add(quotient, 1 << i);
dividend = substract(dividend, divisor << i);
}
}
// 确定商的符号
if((a ^ b) < 0){
// 如果除数和被除数异号，则商为负数
quotient = add(~quotient, 1);
}
// 确定余数符号
remainder = b > 0 ? dividend : add(~dividend, 1);
return quotient;// 返回商
}

#include "stdafx.h"
class Solution
{
public:
int divide_v2(int a, int b)
{
int q = a;
int h = b;
int beishu = 0;
for (int i=31;i>=0;i--)
{
if ((q>>i)>=h)
{
beishu = (1<<i) + beishu;
q = q - (h<<i);
}
}
return beishu;
}
};
int main()
{
Solution s;
auto result = s.divide_v2(16, 5);
return 0;
}