【6.10】位运算-实现四则运算

embedded/2024/11/26 13:51:49/

前言

        从我们开始上学起就了解到，若要进行加减乘除就要使用对应的运算符号…… 甚至在如今的计算机中也是如此。我们通常只知道如何使用这些运算符号，却很少去关注其底层是如何实现的。假如某天在面试中遇到一道题，要求不使用 “+，-，x，÷ ” 来实现两个数的四则运算，你该如何应对呢？今天我们就来看一下应该怎样实现。

一、位运算实现两数相加

        实现两个数相加而不使用“+”运算符，在计算机中，数字以二进制形式表示，即由0和1组成。如果我们需要实现0和1之间的加法，可以考虑以下四种组合方式：
1. 0 + 0 = 00
2. 0 + 1 = 01
3. 1 + 0 = 01
4. 1 + 1 = 10

        通过观察可以发现，只有当1与1相加时才会产生进位，其他组合都不会产生进位。因此，判断是否产生进位只需检查a与b的按位与运算结果是否为1。而a与b的和（不考虑进位）可以通过a与b的按位或运算来计算。理解了这一点，编写代码就变得简单明了。

#include <iostream>int add1(int a, int b) {int c = (a & b) << 1; // 进位的值int d = a ^ b;        // 不考虑进位，相加的值return c | d;         // 或者 return c ^ d;
}int main() {int a = 5;int b = 3;std::cout << "Sum: " << add1(a, b) << std::endl;return 0;
}

        在处理二进制加法时，我们通常会遇到多个位的情况，而不仅仅是单个位的加法。例如，给定两个二进制数 `a = 13 (1101)` 和 `b = 9 (1001)`，我们需要计算它们的和。首先，如果不考虑进位问题，我们可以直接对每一位进行按位异或运算，得到的结果如下：

a = 1101
b = 1001
---------
   = 0100

        这个结果表示在不考虑进位的情况下，`a` 和 `b` 的和为 `0100`。接下来，我们需要处理进位问题，以得到最终的和。

        在处理二进制加法时，我们通常需要考虑进位问题。例如，给定两个二进制数 a = 13 (1101) 和 b = 9 (1001)，我们需要计算它们的和。首先，如果不考虑进位，我们可以直接对每一位进行按位异或运算，得到的结果如下：

a = 1101 
b = 1001 
--------- 
=   0100

        这个结果表示在不考虑进位的情况下，a 和 b 的和为 0100。接下来，我们需要处理进位问题，以得到最终的和。

  1. 进位问题：

    • 只有当两个位都是1时才会产生进位。因此，我们可以使用按位与运算来检测进位。

    • 计算 a & b 的结果是 1001，这意味着在第1位和第4位上会产生进位。

    • 进位的值实际上是 10010（即 (a & b) << 1）。

  2. 合并结果：

    • 将进位值 10010 与不考虑进位的结果 0100 相加，得到最终结果 10110。

    • 10110 实际上是十进制的 22，也就是 13 + 9 的结果。

  3. 避免使用加号：

    • 由于题目要求不能使用加减乘除符号，我们需要通过递归来实现加法。

    • 通过上面的分析，我们发现 a + b 可以通过按位异或和按位与运算后再次执行相加操作。

    • 因此，我们可以使用递归来实现这个过程。

#include <iostream>int add2(int a, int b) {if (a == 0 || b == 0)return a ^ b;// 其他逻辑
}int main() {int a = 5;int b = 3;std::cout << "Sum: " << add2(a, b) << std::endl;return 0;
}
        第3行表示的是如果a==0就返回b，如果b==0就返回a，这种写法少了一个if语句的判断会更简洁。

        经过验证，我们的代码能够正确地实现两个数的相加，而无需使用“+”运算符。实际上，我们可以将递归方法改为非递归方式来实现相同的功能。

#include <iostream>int add3(int a, int b) {while (b != 0) {int temp = a ^ b;  // 不考虑进位的和b = (a & b) << 1;  // 进位a = temp;          // 更新 a 为不考虑进位的和}return a;
}int main() {int a = 5;int b = 3;std::cout << "Sum: " << add3(a, b) << std::endl;return 0;
}

        这种方法的原理非常简单：每次计算时，我们都会对 `a` 和 `b` 进行重新赋值，然后不断循环，直到 `b` 等于0时停止。在这里，`b` 表示的是进位的值，当 `b` 等于0时，意味着不再有进位，此时可以退出循环。这就是通过位运算来实现加法的基本思路。

        为了更好地理解这个过程，我们可以假设 `a = 13` 和 `b = 9`，并通过图示来展示每一步的计算过程。

 

 

二、位运算实现两数相减

        在不使用“-”运算符的情况下实现两个数的相减，既然我们已经实现了加法，那么减法就相对简单了。我们可以将 a - b 转换为 a + (-b)。然而，题目要求我们不能使用“-”符号，因此我们需要找到另一种方法来表示 -b。

        在计算机中，一个数的相反数可以通过另一种方式表示，即 a 的相反数是 ~a + 1。这里的 ~ 是按位取反运算符，它会将 a 的每一位取反（0 变为 1，1 变为 0），然后再加上 1。

        上面“+”我们已经实现了，“~”不属于四则运算符，所以代码也很容易写出 
#include <iostream>int add3(int a, int b) {while (b != 0) {int temp = a ^ b;  // 不考虑进位的和b = (a & b) << 1;  // 进位a = temp;          // 更新 a 为不考虑进位的和}return a;
}int subtraction(int a, int b) {return add3(a, add3(~b, 1));  // a + (-b)
}int main() {int a = 13;int b = 9;std::cout << "Difference: " << subtraction(a, b) << std::endl;return 0;
}

        在不使用“-”运算符的情况下实现两个数的相减，通过上述方法，我们可以更简洁地实现两个数的相减，只需一行代码即可完成。代码中的 `add3(~b, 1)` 表示 `-b`。然而，如果不使用加法运算符，我们是否也能实现两个数的相减呢？答案是肯定的。我们可以通过以下步骤来实现：

1. **处理 `b` 为0的情况**：
   - 如果 `b` 等于0，我们直接返回 `a`。
   - 如果 `b` 不等于0，我们可以先移除 `a` 和 `b` 中同为1的位。具体方法是通过计算 `c = a & b`，然后通过异或运算 `a ^= c` 和 `b ^= c` 来移除这些位。

2. **处理不同位的情况**：
   - 经过第一步处理后，`a` 和 `b` 在相同位置上要么都是0，要么一个0一个1，不可能全是1。
   - 在不考虑借位的情况下，对应位置上的结果可以通过 `a | b` 来计算（因为在第一步中已经移除了同为1的位）。
   - 实际计算时需要考虑借位问题，因此实际结果是 `(a | b) - (b << 1)`。然而，这里又出现了“-”符号，不符合要求。我们可以通过递归来解决这个问题。

### 递归实现

#include <iostream>int subtraction2(int a, int b) {if (b == 0)return a;int c = a & b;// 下面两行是把a和b中相同位置为1的都消去a ^= c;b ^= c;return subtraction2(a | b, b << 1);
}int main() {int a = 13;int b = 9;std::cout << "Difference: " << subtraction2(a, b) << std::endl;return 0;
}

### 非递归实现
 

#include <iostream>int subtraction3(int a, int b) {while (b != 0) {int c = a & b;a ^= c;b ^= c;a |= b;b <<= 1;}return a;
}int main() {int a = 13;int b = 9;std::cout << "Difference: " << subtraction3(a, b) << std::endl;return 0;
}


        通过递归和非递归方法，我们可以在不使用“-”运算符的情况下实现两个整数的相减。递归方法通过不断移除 `a` 和 `b` 中同为1的位，并递归调用自身，直到 `b` 为0。非递归方法通过循环移除 `a` 和 `b` 中同为1的位，并合并结果，直到 `b` 为0。

        我们以a=13，b=10来画个图加深一下理解

 

三、位运算实现两数相乘

        在不使用“×”运算符的情况下实现两个数的相乘，我们来看一个例子，比如 `13 * 9`，计算方式如下：

        从上面的公式可以看出，只有当 `b` 的某一位是1时，与 `a` 相乘才有意义。如果 `b` 的某一位是0，那么与 `a` 相乘则永远都是0。因此，我们在计算时逐步遍历 `b` 的每一位，只有当它为1时才进行运算。
### 示例代码

#include <iostream>int add3(int a, int b) {while (b != 0) {int temp = a ^ b;  // 不考虑进位的和b = (a & b) << 1;  // 进位a = temp;          // 更新 a 为不考虑进位的和}return a;
}int negative(int a) {return add3(~a, 1);  // 求一个数的相反数
}int mult(int a, int b) {int x = a < 0 ? negative(a) : a;  // 如果是负数，先转为正数再参与计算int y = b < 0 ? negative(b) : b;int res = 0;while (y != 0) {if ((y & 1) == 1)res = add3(res, x);x <<= 1;  // x 左移一位y >>= 1;  // y 右移一位}return (a ^ b) >= 0 ? res : negative(res);  // 判断结果的符号
}int main() {int a = 13;int b = 9;std::cout << "Product: " << mult(a, b) << std::endl;return 0;
}

 

        通过逐步遍历 `b` 的每一位，并在 `b` 的某一位为1时进行相应的计算，我们可以在不使用“×”运算符的情况下实现两个整数的相乘。`mult` 函数通过判断 `b` 的每一位，并将 `a` 左移相应的位数，最终得到两个整数的乘积。

四、位运算实现两数相除

        在不使用“÷”运算符的情况下实现两个数的相除， `a ÷ b` 的含义是 `a` 中包含多少个 `b`。例如，`6 ÷ 3 = 2`，`7 ÷ 3 = 2`。这里我们实现的除法与计算机中两个 `int` 类型相除的结果一致，只记录商的值，余数会被舍去。因此，我们可以通过不断从 `a` 中减去 `b`，并记录减去的次数来实现除法。

### 递归实现
 

#include <iostream>int add3(int a, int b) {while (b != 0) {int temp = a ^ b;  // 不考虑进位的和b = (a & b) << 1;  // 进位a = temp;          // 更新 a 为不考虑进位的和}return a;
}int subtraction(int a, int b) {return add3(a, add3(~b, 1));  // a + (-b)
}int negative(int a) {return add3(~a, 1);  // 求一个数的相反数
}int div1(int a, int b) {int x = a < 0 ? negative(a) : a;int y = b < 0 ? negative(b) : b;if (x < y)return 0;return (a ^ b) >= 0 ? div1(subtraction(a, b), b) + 1 : div1(add3(a, b), b) - 1;
}int main() {int a = 7;int b = 3;std::cout << "Quotient: " << div1(a, b) << std::endl;return 0;
}

        在递归实现中，如果 a 非常大而 b 又比较小，确实可能会出现堆栈溢出异常。递归调用会在堆栈中不断累积函数调用帧，直到达到堆栈的限制。为了避免这种情况，我们可以将递归实现改为非递归实现，从而提高效率并避免堆栈溢出。 

### 非递归实现
 

#include <iostream>int add3(int a, int b) {while (b != 0) {int temp = a ^ b;  // 不考虑进位的和b = (a & b) << 1;  // 进位a = temp;          // 更新 a 为不考虑进位的和}return a;
}int subtraction3(int a, int b) {while (b != 0) {int c = a & b;a ^= c;b ^= c;a |= b;b <<= 1;}return a;
}int negative(int a) {return add3(~a, 1);  // 求一个数的相反数
}int div2(int a, int b) {int x = a < 0 ? negative(a) : a;int y = b < 0 ? negative(b) : b;int count = 0;while (x >= y) {x = subtraction3(x, y);count++;}return (a ^ b) >= 0 ? count : -count;
}int main() {int a = 7;int b = 3;std::cout << "Quotient: " << div2(a, b) << std::endl;return 0;
}
        这种虽然不会出现堆栈溢出异常了，但如果b是1，a是一个非常非常大的数，这样一直减下去也是非常慢的，我们还可以换种思路，每次减去的不是b，而是b的倍数，我们来看下代码

### 优化实现

#include <iostream>int add3(int a, int b) {while (b != 0) {int temp = a ^ b;  // 不考虑进位的和b = (a & b) << 1;  // 进位a = temp;          // 更新 a 为不考虑进位的和}return a;
}int subtraction3(int a, int b) {while (b != 0) {int c = a & b;a ^= c;b ^= c;a |= b;b <<= 1;}return a;
}int negative(int a) {return add3(~a, 1);  // 求一个数的相反数
}int div3(int a, int b) {if (a == 0 || b == 0)return 0;  // b 不能为0，如果 b 是0我们应该抛异常的，这里简单处理就没抛int x = a < 0 ? negative(a) : a;int y = b < 0 ? negative(b) : b;int result = 0;for (int i = 31; i >= 0; i--) {if ((x >> i) >= y) {result = add3(result, 1 << i);x = subtraction3(x, y << i);}}return (a ^ b) >= 0 ? result : -result;
}int main() {int a = 7;int b = 3;std::cout << "Quotient: " << div3(a, b) << std::endl;return 0;
}


        通过递归和非递归方法，我们可以在不使用“÷”运算符的情况下实现两个整数的相除。递归方法通过不断从 `a` 中减去 `b`，并递归调用自身，直到 `a` 小于 `b`。非递归方法通过循环从 `a` 中减去 `b`，并记录减去的次数。优化方法通过每次减去 `b` 的倍数，提高计算效率。


http://www.ppmy.cn/embedded/140637.html

相关文章

昇腾CANN环境下Whisper.cpp安装指南

昇腾CANN环境下Whisper.cpp安装指南

前置检查 确认昇腾AI处理器已经安装妥当 lspci | grep Processing accelerators ❕务必确认操作系统架构及版本、Python版本满足要求 软件 版本 操作系统 openEuler20.03/22.03, Ubuntu 20.04/22.04 Python 3.8, 3.9, 3.10 uname -m && cat /etc/*release py…
阅读更多...
非标自动化项目管理如何做

非标自动化项目管理如何做

非标自动化项目管理的关键在于&#xff1a;深入理解客户需求、制定详细的项目计划、有效的资源调配、严格的质量控制、持续的风险管理、高效的沟通协调、灵活应对变更、项目总结与持续改进。深入理解客户需求是项目成功的基础。通过与客户的深入沟通&#xff0c;全面了解其生产…
阅读更多...
[面试]-golang基础面试题总结

[面试]-golang基础面试题总结

文章目录 panic 和 recover**注意事项**使用 pprof、trace 和 race 进行性能调试。**Go Module**&#xff1a;Go中new和make的区别 Channel什么是 Channel 的方向性&#xff1f;如何对 Channel 进行方向限制&#xff1f;Channel 的缓冲区大小对于 Channel 和 Goroutine 的通信有…
阅读更多...
网络安全设备系列--安全隔离网闸

网络安全设备系列--安全隔离网闸

0x00 定义: 网闸&#xff08;GAP&#xff09;全称安全隔离网闸。安全隔离网闸是一种由带有多种控制功能专用硬件在电路上切断网络之间的链路层连接&#xff0c;并能够在网络间进行安全适度的应用数据交换的网络安全设备。 网闸在两个不同安全域之间&#xff0c;通过协议转换的…
阅读更多...
Websocket++ 框架

Websocket++ 框架

概述 基于 C 标准的 WebSocket 协议实现&#xff0c;适合使用 C11 或更高版本开发的项目&#xff0c;支持构建 WebSocket 客户端和服务器&#xff0c;功能灵活&#xff0c;设计模块化&#xff0c;非常适合高性能的网络通信场景 主要特点 支持 WebSocket 客户端和服务器默认支持…
阅读更多...
lanqiaoOJ 3745：餐厅排队 ← 数组模拟队列

lanqiaoOJ 3745：餐厅排队 ← 数组模拟队列

【题目来源】https://www.lanqiao.cn/problems/3745/learning/【题目描述】 在蓝桥学院的新餐厅&#xff0c;学生们在取餐窗囗形成了一条长队。小蓝&#xff0c;餐厅的经理&#xff0c;希望能够实时了解队伍最前面和最后面的学生编号。你需要执行以下三种操作&#xff1a; 1.学…
阅读更多...
Debian/Ubuntu 、Fedora 、Arch Linux， 在Linux上，对文本文件进行多线程压缩 xz、pxz、zstd、7z、lrzip

Debian/Ubuntu 、Fedora 、Arch Linux， 在Linux上，对文本文件进行多线程压缩 xz、pxz、zstd、7z、lrzip

Debian/Ubuntu 、Fedora 、Arch Linux&#xff0c; 在Linux上&#xff0c;对文本文件进行多线程压缩 xz、pxz、zstd、7z、lrzip 前言对比多线程压缩1. 使用 pxz安装 pxz使用 pxz 2. 使用 xz 的 -T 选项使用 xz -T 3. 其他压缩命令1. 使用 gzip2. 使用 bzip23. 使用 xz4. 使用 7…
阅读更多...
sql server 主从job对比差异

sql server 主从job对比差异

---查看job的基本信息 select a.job_id,a.name, a.date_created ,a.date_modified ,case when a.enabled1 then N是when a.enabled0 then N否 end as enabled ,a.description, b.step_id,b.step_name,b.subsystem,b.command,b.database_name,b.last_run_datefrom msdb.dbo.sy…
阅读更多...
最新文章

Copyright @ 2022~2023