位运算03 不用加号的加法[C++]

 

图源:文心一言

上机题目练习整理,位运算,供小伙伴们参考~🥝🥝

网页版目录在页面的右上角↗~🥝🥝

  • 第1版:在力扣新手村刷题的记录~🧩🧩

编辑:梅头脑🌸

审核:文心一言

题目:面试题 17.01. 不用加号的加法 - 力扣(LeetCode)


🧵面试题 17.01. 不用加号的加法

🧩题目

设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。

示例:

输入: a = 1, b = 1
输出: 2

提示:

  • ab 均可能是负数或 0
  • 结果不会溢出 32 位整数

🌰解题一:循环+按位运算(一)

📇算法思路

  • 算法思想:
    • 初始化:函数接收两个整数ab作为输入。

    • 循环条件:当进位b不为0时,循环继续。

    • 计算进位:使用a & b来计算ab的哪些位都需要进位(仅当 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;
  • 进位 bb = carry = 000000000000000000000000000000110;
  • 本轮需要进位的在第2位,100 + 100 = 1000;

3:计算第2轮 本位和与进位

  • 进位 carry a & b = 00000000000000000000000000000100,无符号数算数左移1位结果为 00000000000000000000000000001000;
  • 本位和 a : a ^ b = 00000000000000000000001111101010;
  • 进位 bb = carry = 00000000000000000000000000001000;
  • 本轮需要进位的在第3位,1000 + 1000 = 10000;

4:计算第3轮 本位和与进位

  • 进位 carry a & b = 00000000000000000000000000001000,无符号数算数左移1位结果为 00000000000000000000000000010000;
  • 本位和 a : a ^ b = 00000000000000000000001111100010;
  • 进位 bb = carry = 00000000000000000000000000010000;
  • 本轮 a 与 b 没有同时为 1 的位,最后进行异或,进位b更新为0,本位和a即为答案;

5:计算第4轮 本位和与进位

  • 进位 carry a & b = 00000000000000000000000000000000,无符号数算数左移1位结果为 00000000000000000000000000000000;
  • 本位和 a : a ^ b = 00000000000000000000001111110010;
  • 进位 bb = carry = 00000000000000000000000000000000;
  • 返回:a = 1010 (十进制) = 00000000000000000000001111110010(二进制);

这道题目的难点应该是从后向前一轮一轮地处理 进位,(本位和异或就可以搞定了),感觉官方的解法真的很简洁美观,但是以我的功底,要能自己写出这种水平的代码,感觉至少还要1年,囧...

🌰解题二:循环+按位运算(二)(简单全加器原理)

📇算法思路

  • 算法思想:
    • 初始化:函数接收两个整数ab作为输入。

    • 循环条件:int 通常为 32位,未读取完32位时,循环继续遍历读取每1位。

    • 全加器逻辑

      • 每次从ab中提取一位(从最低位开始)记入 bita、bitb进行运算,调用函数fulladder计算本位和 sum 与 进位 carryout,计算结果存入容器 adderresult。

      • 计算进位:使用a & b来计算ab的哪些位都需要进位(仅当 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(下轮进位): 1

Iteration(位数) 1:
  bita: 1
  bitb: 1
  carry(本轮进位): 1
  adderresult (sum, carry): (1, 1)
  result: 2 = 00000000000000000000000000000010
  carry(下轮进位): 1

Iteration(位数) 2:
  bita: 1
  bitb: 0
  carry(本轮进位): 1
  adderresult (sum, carry): (0, 1)
  result: 2 = 00000000000000000000000000000010
  carry(下轮进位): 1

Iteration(位数) 3:
  bita: 1
  bitb: 0
  carry(本轮进位): 1
  adderresult (sum, carry): (0, 1)
  result: 2 = 00000000000000000000000000000010
  carry(下轮进位): 1

Iteration(位数) 4:
  bita: 0
  bitb: 0
  carry(本轮进位): 1
  adderresult (sum, carry): (1, 0)
  result: 18 = 00000000000000000000000000010010
  carry(下轮进位): 0

Iteration(位数) 5:
  bita: 1
  bitb: 0
  carry(本轮进位): 0
  adderresult (sum, carry): (1, 0)
  result: 50 = 00000000000000000000000000110010
  carry(下轮进位): 0

Iteration(位数) 6:
  bita: 1
  bitb: 0
  carry(本轮进位): 0
  adderresult (sum, carry): (1, 0)
  result: 114 = 00000000000000000000000001110010
  carry(下轮进位): 0

Iteration(位数) 7:
  bita: 0
  bitb: 1
  carry(本轮进位): 0
  adderresult (sum, carry): (1, 0)
  result: 242 = 00000000000000000000000011110010
  carry(下轮进位): 0

Iteration(位数) 8:
  bita: 0
  bitb: 1
  carry(本轮进位): 0
  adderresult (sum, carry): (1, 0)
  result: 498 = 00000000000000000000000111110010
  carry(下轮进位): 0

Iteration(位数) 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(下轮进位): 0

expected: 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博客

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/406598.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

go 1.18 不同目录package引用问题

go 1.18开始使用module了 不同的package在vs code中引用的话 需要先开启 是Go1.11版本之后 推出的版本管理工具 有点类似java的 maven工具 可以引入依赖使用 go env -w GO111MODULEon 先把这个打开 然后在创建的vs code工作目录下 执行 module gomdoule module 模块名 会生…

(六)激光线扫描-三维重建

本篇文章是《激光线扫描-三维重建》系列的最后一篇。 1. 基础理论 1.1 光平面 在之前光平面标定的文章中,已经提到过了,是指 激光发射器投射出一条线,形成的一个扇形区域平面就是光平面。 三维空间中平面的公式是: A X + B Y + C Z + D = 0 A X+B Y+C Z+D=0

解决RabbitMQ管理页面异常/不正确的问题

正确的页面&#xff1a;有Channels、Exchanges等 异常/不正确的页面&#xff1a; 问题原因 我的RabbitMQ是用docker安装的&#xff0c;应该不会是安装的环境有问题。 而且MQ的服务确实是启动了&#xff0c;后端能正常使用&#xff0c;并且管理界面的登录页面也是能正常登录的&…

流程图:理解、创建与优化的视觉工具

流程图&#xff1a;理解、创建与优化的视觉工具 引言 在日常生活和工作中&#xff0c;我们经常遇到需要描述一系列步骤或过程的情况。这些步骤可能是制作一杯咖啡、完成一个项目&#xff0c;或者是解决一个复杂的数学问题。流程图&#xff0c;作为一种强大的视觉工具&#xf…

数据同步MySQL -> Elasticsearch

大家好我是苏麟,今天聊聊数据同步 . 数据同步 一般情况下&#xff0c;如果做查询搜索功能&#xff0c;使用 ES 来模糊搜索&#xff0c;但是数据是存放在数据库 MySQL 里的&#xff0c;所以说我们需要把 MySQL 中的数据和 ES 进行同步&#xff0c;保证数据一致(以 MySQL 为主)…

在 Jupyter Notebook 中查看所使用的 Python 版本和 Python 解释器路径

&#x1f349; CSDN 叶庭云&#xff1a;https://yetingyun.blog.csdn.net/ 我们在做 Python 开发时&#xff0c;有时在我们的服务器上可能安装了多个 Python 版本。 使用 conda info --envs 可以列出所有的 conda 环境。当在 Linux 服务器上使用 which python 命令时&#xff0…

ES通用查询页面使用说明

前言:ES语法比较复杂,需要专门的学习,而且查询工具不太友好, 对公司运维人员使用有点困难,所以花了个时间做了一个页面,方便运维人员使用,如下。 也不难,有兴趣的朋友可以私聊发源码。 开发帮助-ES数据查询 搜索 输入要查看的文档索引,文档类型后点【查询】即可 搜…

Python之Matplotlib

Matplotlib 是一个综合库&#xff0c;用于创建静态、动画、 和交互式可视化 安装 pip install matplotlib 功能 示例 import matplotlib.pyplot as plt plt.figure() plt.plot([1,2,3],[10,20,30]) plt.show() 官方文档&#xff1a; Matplotlib — Visualization with Pyt…

Covalent Network(CQT)发展新里程碑:SOC 2 数据安全认证通过,进一步加强了其人工智能支持

Covalent Network&#xff08;CQT&#xff09;现已完成并通过了严格的 Service Organization Control&#xff08;SOC) 2 Type II 的合规性审计&#xff0c;通过由备受行业认可的机构执行&#xff0c;进一步证明了 Covalent Network&#xff08;CQT&#xff09;团队坚定不移地致…

【区块链】智能交易模式下的数据安全流通模型

【区块链】智能交易模式下的数据安全流通模型 写在最前面**区块链智能交易模式概述****数据安全流通的挑战****数据安全流通模型的核心要素****实现数据安全流通的区块链技术****区块链智能交易模式下数据安全流通模型的设计原则****数据安全流通模型的应用案例分析****面临的挑…

OpenAI划时代大模型——文本生成视频模型Sora作品欣赏(五)

Sora介绍 Sora是一个能以文本描述生成视频的人工智能模型&#xff0c;由美国人工智能研究机构OpenAI开发。 Sora这一名称源于日文“空”&#xff08;そら sora&#xff09;&#xff0c;即天空之意&#xff0c;以示其无限的创造潜力。其背后的技术是在OpenAI的文本到图像生成模…

全面解析企业财务报表系列之四:财务报表的真实性和可靠性

全面解析企业财务报表系列之四&#xff1a;财务报表的真实性和可靠性 一、什么是会计方法二、选择会计方法三、会计方法的重要性四、会计报表常用的造假手段五、财务报表经常被遗漏的重要事件六、财务报告造假的资信敏感性七、财务报告审计的重要性八、审计报告 一、什么是会计…

HL祭记汇

一.写在前面 如果说廿四10天集训&#xff0c;对于我&#xff0c;是完成了从入门&#xff08;虽然可能我比别人入门更早&#xff1f;&#xff09;到准OIer的蜕变&#xff0c;那么&#xff0c;HL7天&#xff0c;可以说是真正成为了OIer&#xff0c;虽然是被小学生、初中生&#…

【时事篇-05-04】20240224 27笔货币基金中有3笔250元的具体数目测算( itertools)

结果展示 背景需求&#xff1a; 前文测算了27只货币基金&#xff0c;如果存145、146、147、148、149、150元分别需要存几笔。结果是4、4、4、5、5、5 【时事篇-05-03】20240222 金额145-150元填充27笔货币基金的具体数目测算&#xff08; itertools&#xff09;-CSDN博客文章…

1.30主成分分析,因子分析

主成分分析 主成分分析&#xff08;Principal Component Analysis&#xff0c;简称PCA&#xff09;是一种常用的多变量数据分析方法。它用于降低数据维度&#xff0c;以便更好地理解和解释数据集中的变化。PCA通过将原始数据投影到新的坐标轴上&#xff0c;使得新的坐标轴上的…

Raspbian命令行RTSP/RTP服务

Raspbian命令行RTSP/RTP服务 1. 源由2. Raspbian摄像头2.1 命令行启动RTP摄像头2.2 命令行启动RTSP摄像头 3. 示例3.1 测试RTP摄像头3.2 测试RTSP摄像头3.3 QGroundControl测试3.3.1 RTSP配置3.3.2 RTP配置 4. 总结5. 参考资料 1. 源由 鉴于实际测试发现RTP协议下&#xff0c;…

【MATLAB】CEEMD_ MFE_SVM_LSTM 神经网络时序预测算法

有意向获取代码&#xff0c;请转文末观看代码获取方式~也可转原文链接获取~ 1 基本定义 CEEMD_MFE_SVM_LSTM神经网络时序预测算法是一种结合了多种先进技术的复杂预测方法&#xff0c;旨在提高时序预测的准确性和稳定性。下面是对该算法的详细介绍&#xff1a; CEEMD&#xff…

常用的函数式接口(Supplier、Consumer、Predicate、Function)

目录 一.函数式接口作为方法的参数 二.函数式接口作为方法的返回值 三.常用的函数式接口 3.1生产型Supplier接口 3.2消费型Consumer接口 抽象方法&#xff1a;accept 默认方法&#xff1a;andThen 3.3判断型Predicate接口 抽象方法&#xff1a;test 默认方法&#xf…

【vue】provide/inject

provide/ inject这对选项需要一起使用&#xff0c;以允许一个祖先组件向其所有子孙后代注入一个依赖&#xff0c;不论组件层次有多深&#xff0c;并在起上下游关系成立的时间里始终生效。 通途点来讲可以用来实现隔代传值&#xff0c;传统的props只能父传子&#xff0c;而 prov…

电影《热辣滚烫》观后感

过完年&#xff0c;回来的时候&#xff0c;上周看了这部电影《热辣滚烫》&#xff0c;是贾玲自导自演的一部电影&#xff0c;个人感觉还是非常好的&#xff0c;偏向小人物&#xff0c;写实风格。 &#xff08;1&#xff09;电影相关评价 但是你说这部电影有多立志&#xff0c…