图源:文心一言
上机题目练习整理,位运算,供小伙伴们参考~🥝🥝
网页版目录在页面的右上角↗~🥝🥝
- 第1版:在力扣新手村刷题的记录~🧩🧩
编辑:梅头脑🌸
审核:文心一言
题目:面试题 17.01. 不用加号的加法 - 力扣(LeetCode)
🧵面试题 17.01. 不用加号的加法
🧩题目
设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。
示例:
输入: a = 1, b = 1 输出: 2提示:
a
,b
均可能是负数或 0- 结果不会溢出 32 位整数
🌰解题一:循环+按位运算(一)
📇算法思路
- 算法思想:
初始化:函数接收两个整数
a
和b
作为输入。循环条件:当进位
b
不为0时,循环继续。计算进位:使用
a & b
来计算a
和b
的哪些位都需要进位(仅当 a 为 1,且 b 为 1时,需要进位)。然后,通过左移一位(<< 1
)来将这些进位应用到正确的位置上。这里使用unsigned int
是为了确保左移操作不会引入任何符号位。计算本位和:使用
a ^ b(
异或操作)
来计算不考虑进位时的和。异或操作会返回在两个输入中只有一个为1的那些位上设置1的结果,例如:
a = 1, b = 1 ,算数运算:a + b = 10,位运算:本位和为 1 ^ 1 = 0,进位为 1 & 1 = 1;
a = 1, b = 0 ,算数运算:a + b = 01,位运算:本位和为 1 ^ 0 = 1,进位为 1 & 0 = 0;
a = 0, b = 1 ,算数运算:a + b = 01,位运算:本位和为 0 ^ 1 = 1,进位为 0 & 1 = 0;
a = 0, b = 0 ,算数运算:a + b = 00,位运算:本位和为 0 ^ 0 = 0,进位为 0 & 0 = 0;
更新操作数:
a
被更新为不考虑进位的本位和(a ^ b
的结果)。b
被更新为进位((unsigned int)(a & b) << 1
的结果)。这样,在下一次循环中,b
将包含所有需要被加到a
上的进位。返回结果:当
b
变为0(即没有更多的进位需要处理)时,循环结束,函数返回a
作为最终的和。- 时间复杂度:O(1)或O(log(max(a, b)));我们可以认为时间复杂度是O(1),其中1表示一个固定的上限,即整数的大小,或整数的二进制表示的长度。
- 空间复杂度:O(1);
⌨️算法代码
#include <iostream>
#include <bitset>
using namespace std;
class Solution {
public:
int add(int a, int b) {
while (b != 0) {
unsigned int carry = (unsigned int)(a & b) << 1;
a = a ^ b;
b = carry;
}
return a;
}
};
//class Solution {
//public:
// int add(int a, int b) {
// cout << "a = " << a << " = " << bitset<32>(a) << ", b = " << b << " = " << bitset<32>(b) << endl;
//
// while (b != 0) {
// unsigned int carry = (unsigned int)(a & b) << 1;
// cout << "carry = " << bitset<32>(carry);
// a = a ^ b;
// cout << ", a = " << bitset<32>(a);
// b = carry;
// cout << ", b = " << bitset<32>(b) << endl;
// }
// return a;
// }
//};
//
//int main()
//{
// int a = 111; int b = 899;
// Solution solution;
// int result = solution.add(a, b);
// cout << "result = " << result << " = " << bitset<32>(result) << endl;
//
// return 0;
//}
作者:力扣官方题解
链接:https://leetcode.cn/problems/add-without-plus-lcci/solutions/1718025/bu-yong-jia-hao-de-jia-fa-by-leetcode-so-pp8a/
📇执行结果
输入 a = 111, b = 899后,执行结果如下:
📇代码解释
1:输入 a 与 b
- a = 111(十进制) = 00000000000000000000000001101111(二进制)
- b = 899(十进制) = 00000000000000000000001110000011(二进制)
- 本轮需要进位的在第0位、第1位,11 + 11 = 110;
2:计算第1轮 本位和与进位
- 进位 carry :a & b = 00000000000000000000000000000011,无符号数算数左移1位结果为 000000000000000000000000000000110;
- 本位和 a : a ^ b = 00000000000000000000001111101100;
- 进位 b:b = carry = 000000000000000000000000000000110;
- 本轮需要进位的在第2位,100 + 100 = 1000;
3:计算第2轮 本位和与进位
- 进位 carry :a & b = 00000000000000000000000000000100,无符号数算数左移1位结果为 00000000000000000000000000001000;
- 本位和 a : a ^ b = 00000000000000000000001111101010;
- 进位 b:b = carry = 00000000000000000000000000001000;
- 本轮需要进位的在第3位,1000 + 1000 = 10000;
4:计算第3轮 本位和与进位
- 进位 carry :a & b = 00000000000000000000000000001000,无符号数算数左移1位结果为 00000000000000000000000000010000;
- 本位和 a : a ^ b = 00000000000000000000001111100010;
- 进位 b:b = carry = 00000000000000000000000000010000;
- 本轮 a 与 b 没有同时为 1 的位,最后进行异或,进位b更新为0,本位和a即为答案;
5:计算第4轮 本位和与进位
- 进位 carry :a & b = 00000000000000000000000000000000,无符号数算数左移1位结果为 00000000000000000000000000000000;
- 本位和 a : a ^ b = 00000000000000000000001111110010;
- 进位 b:b = carry = 00000000000000000000000000000000;
- 返回:a = 1010 (十进制) = 00000000000000000000001111110010(二进制);
这道题目的难点应该是从后向前一轮一轮地处理 进位,(本位和异或就可以搞定了),感觉官方的解法真的很简洁美观,但是以我的功底,要能自己写出这种水平的代码,感觉至少还要1年,囧...
🌰解题二:循环+按位运算(二)(简单全加器原理)
📇算法思路
- 算法思想:
初始化:函数接收两个整数
a
和b
作为输入。循环条件:int 通常为 32位,未读取完32位时,循环继续遍历读取每1位。
全加器逻辑:
每次从
a
和b
中提取一位(从最低位开始)记入 bita、bitb进行运算,调用函数fulladder计算本位和 sum 与 进位 carryout,计算结果存入容器 adderresult。计算进位:使用
a & b
来计算a
和b
的哪些位都需要进位(仅当 a 为 1,且 b 为 1时,需要进位)。然后,通过左移一位(<< 1
)来将这些进位应用到正确的位置上。这里使用unsigned int
是为了确保左移操作不会引入任何符号位。计算本位和:使用 sum = a ^ b
(
异或操作)
来计算不考虑进位时的和。异或操作会返回在两个输入中只有一个为1的那些位上设置1的结果;更新操作数:在result 中输出本位和与进位;
返回结果:当int遍历结束时时,循环结束,函数返回
result
作为最终的和。- 时间复杂度:O(1):总是处理32位整数;
- 空间复杂度:O(1):使用了固定数量的变量来存储中间结果和进位;
⌨️算法代码
#include <iostream>
#include <utility> // 为了使用 std::pair
// 全加器函数,返回一个包含和与进位的pair
std::pair<int, int> fulladder(int a, int b, int carryin) {
int sum = a ^ b ^ carryin; // 不考虑进位的和
int carryout = (a & b) | ((a ^ b) & carryin); // 进位,注意这里修正了逻辑错误
return std::make_pair(sum, carryout); // 返回和与进位的pair
}
// 两个32位整数相加
int add(int a, int b) {
int carry = 0; // 初始化进位为0
int result = 0; // 初始化结果为0
for (int i = 0; i < 32; ++i) { // 逐位相加
int bita = (a >> i) & 1; // a的第i位
int bitb = (b >> i) & 1; // b的第i位
// 调用全加器并更新结果和进位
std::pair<int, int> adderresult = fulladder(bita, bitb, carry);
result |= adderresult.first << i; // 将当前位的和加入结果中
carry = adderresult.second; // 更新进位为全加器的进位输出
}
// 注意:此实现不处理溢出情况。在实际应用中,应考虑溢出。
return result;
}
int main() {
int a = 111; // 101 in binary, 但实际上在32位整数中是 0000 ... 0101
int b = 899; // 011 in binary, 但实际上在32位整数中是 0000 ... 0011
int expected = 1010; // 1000 in binary, 但实际上在32位整数中是 0000 ... 1000
int actual = add(a, b); // 应该返回1010(没有溢出的情况下)
std::cout << "expected: " << expected << std::endl; // 输出期望结果
std::cout << "actual: " << actual << std::endl; // 输出实际结果,应该是8
return 0; // 程序成功执行完毕,返回0表示成功状态码
}
作者:文心一言
📇执行结果
测试代码
int add(int a, int b) {
int carry = 0;
int result = 0;
for (int i = 0; i < 32; ++i) {
int bita = (a >> i) & 1;
int bitb = (b >> i) & 1;
std::pair<int, int> adderresult = fulladder(bita, bitb, carry);
// 添加打印语句来查看中间变量的值
std::cout << "Iteration(位数) " << i << ":" << std::endl;
std::cout << " bita: " << bita << std::endl;
std::cout << " bitb: " << bitb << std::endl;
std::cout << " carry(本轮进位): " << carry << std::endl;
std::cout << " adderresult (sum, carry): ("
<< adderresult.first << ", " << adderresult.second << ")" << std::endl;
result |= adderresult.first << i;
carry = adderresult.second;
// 打印当前的结果和进位
std::cout << " result: " << result << " = " << std::bitset<32>(result) <<std::endl;
std::cout << " carry(下轮进位): " << carry << std::endl;
std::cout << std::endl; // 打印空行以便于阅读
}
return result;
}
运行结果
1:输入 a 与 b
- a = 111(十进制) = 00000000000000000000000001101111
- b = 899(十进制) = 00000000000000000000001110000011
2:代码运行
Iteration(位数) 0:
bita: 1
bitb: 1
carry(本轮进位): 0
adderresult (sum, carry): (0, 1)
result: 0 = 00000000000000000000000000000000
carry(下轮进位): 1Iteration(位数) 1:
bita: 1
bitb: 1
carry(本轮进位): 1
adderresult (sum, carry): (1, 1)
result: 2 = 00000000000000000000000000000010
carry(下轮进位): 1Iteration(位数) 2:
bita: 1
bitb: 0
carry(本轮进位): 1
adderresult (sum, carry): (0, 1)
result: 2 = 00000000000000000000000000000010
carry(下轮进位): 1Iteration(位数) 3:
bita: 1
bitb: 0
carry(本轮进位): 1
adderresult (sum, carry): (0, 1)
result: 2 = 00000000000000000000000000000010
carry(下轮进位): 1Iteration(位数) 4:
bita: 0
bitb: 0
carry(本轮进位): 1
adderresult (sum, carry): (1, 0)
result: 18 = 00000000000000000000000000010010
carry(下轮进位): 0Iteration(位数) 5:
bita: 1
bitb: 0
carry(本轮进位): 0
adderresult (sum, carry): (1, 0)
result: 50 = 00000000000000000000000000110010
carry(下轮进位): 0Iteration(位数) 6:
bita: 1
bitb: 0
carry(本轮进位): 0
adderresult (sum, carry): (1, 0)
result: 114 = 00000000000000000000000001110010
carry(下轮进位): 0Iteration(位数) 7:
bita: 0
bitb: 1
carry(本轮进位): 0
adderresult (sum, carry): (1, 0)
result: 242 = 00000000000000000000000011110010
carry(下轮进位): 0Iteration(位数) 8:
bita: 0
bitb: 1
carry(本轮进位): 0
adderresult (sum, carry): (1, 0)
result: 498 = 00000000000000000000000111110010
carry(下轮进位): 0Iteration(位数) 9:
bita: 0
bitb: 1
carry(本轮进位): 0
adderresult (sum, carry): (1, 0)
result: 1010 = 00000000000000000000001111110010
carry(下轮进位): 0……
Iteration(位数) 31:
bita: 0
bitb: 0
carry(本轮进位): 0
adderresult (sum, carry): (0, 0)
result: 1010 = 00000000000000000000001111110010
carry(下轮进位): 0expected: 1010
actual: 1010
🌰自留错误版本
📇算法思路
- 基本思想同算法一,通过计算本位和与进位计算结果~
⌨️算法代码(错误,自留代码)
#include <iostream>
#include <bitset>
using namespace std;
class Solution {
public:
//代码逻辑有问题, sum += 那一行,违背了位运算原则。
int add(int a, int b) {
int sum = 0;
int carry = 0;
int i = 0;
for (i = 0; i < 32; i++) {
cout << "本轮 i = " << i << endl;
int bitA = (a >> i) & 1;
cout << "本轮 bitA = " << bitA << endl;
int bitB = (b >> i) & 1;
cout << "本轮 bitB = " << bitB << endl;
int bitSum = bitA ^ bitB;
cout << "本轮 bitSum = " << bitSum << endl;
carry = (bitA & bitB) | (bitSum & carry);
cout << "本轮 carry = " << carry << endl;
sum = sum + (carry << i + 1) + (bitSum << i);
cout << "本轮 sum = " << sum << endl;
carry <<= 1;
cout << "carry 左移一位" << endl;
cout << endl;
}
return sum;
}
//int add(int a, int b) {
// int result = 0;
// int carry = 0;
// int i = 0;
// for (i = 0; i < 32; i++) {
// cout << "本轮 i = " << i << endl;
// int bitA = (a >> i) & 1;
// cout << "本轮 bitA = " << bitA << endl;
// int bitB = (b >> i) & 1;
// cout << "本轮 bitB = " << bitB << endl;
// int bitSum = bitA ^ bitB;
// cout << "本轮 bitSum = " << bitSum << endl;
// carry = (bitA & bitB) | (bitSum & carry);
// cout << "本轮 carry = " << carry << endl;
// // sum = sum + (carry << i + 1) + (bitSum << i);
// result = result | bitSum << i;
// if (carry & 1) { result |= (1 << (i + 1));}
// cout << "本轮 result = " << result << endl;
// carry >>= 1;
// cout << "carry 右移一位" << endl;
// cout << endl;
// }
// return result;
//}
};
int main()
{
//int a = 1; int b = 1;
int a = 111; int b = 899;
Solution solution;
int result = solution.add(a, b);
cout << result;
return 0;
}
作者:梅头脑
这个解法呃,倒是可以运行,将 本位和 与 进位和分开了,接近解法二的思路。但是因为没能很好得处理进位的问题,就使用了加法企图蒙混过关 sum = sum + (carry << i + 1) + (bitSum << i); (此处如果使用 “ | ” 会吞掉进位与本位的相同位),违背了题目不能使用加法的本意 。又想到使用result,也出现了类似的问题,后来摆脱文心一言用全加器的原理修改掉,也就是解法二~~
🔚结语
博文到此结束,写得模糊或者有误之处,欢迎小伙伴留言讨论与批评,督促博主优化内容{例如有错误、难理解、不简洁、缺功能}等,博主会顶锅前来修改~~😶🌫️😶🌫️
我是梅头脑,本片博文若有帮助,欢迎小伙伴动动可爱的小手默默给个赞支持一下,感谢点赞小伙伴对于博主的支持~~🌟🌟
同系列的博文:🌸位运算_梅头脑_的博客-CSDN博客
同博主的博文:🌸随笔03 笔记整理-CSDN博客