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

ops/2024/11/26 5:58:51/

前言

        从我们开始上学起就了解到，若要进行加减乘除就要使用对应的运算符号…… 甚至在如今的计算机中也是如此。我们通常只知道如何使用这些运算符号，却很少去关注其底层是如何实现的。假如某天在面试中遇到一道题，要求不使用 “+，-，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/ops/136759.html

相关文章

Scala中身份证的使用

Scala中身份证的使用

package hfd import scala.util.Random //字符串 //知识点 //1.toInt把字符串转成整数 //2.toUpperCase变大写 //3.toLomerCase变小写 //4.substring(起点&#xff0c;终点&#xff0c;不包括)字符串截取 //5.chartAt(下标)得到对应位置的字符&#xff08;不是字符串&#xff…
阅读更多...
数据库的联合查询

数据库的联合查询

数据库的联合查询 简介为什么要使⽤联合查询多表联合查询时MYSQL内部是如何进⾏计算的构造练习案例数据案例&#xff1a;⼀个完整的联合查询的过程 内连接语法⽰例 外连接语法 ⽰例⾃连接应⽤场景示例表连接练习 ⼦查询语法单⾏⼦查询多⾏⼦查询多列⼦查询在from⼦句中使⽤⼦查…
阅读更多...
极简开源Windows桌面定时提醒休息python程序

极简开源Windows桌面定时提醒休息python程序

当我们长期在电脑面前坐太久后&#xff0c;会产生一系列健康风险&#xff0c;包括干眼症&#xff0c;颈椎&#xff0c;腰椎&#xff0c;肌肉僵硬等等。解决方案是在一定的时间间隔内我们需要have a break, 远眺可以缓解干眼症等眼部症状&#xff0c;站起来走动两步&#xff0c;…
阅读更多...
一键部署zabbix-agent2的脚本

一键部署zabbix-agent2的脚本

1、首先下载agent2的安装包 我是X86的centos 7系统&#xff0c;zabbix-agent2-5.0.42-1.el7.x86_64.rpm下载地址&#xff0c;另外很多国产系统统信、中科方德也适用这个版本。 这个网站里面有其他版本的&#xff0c;自行选择下载 https://repo.zabbix.com/zabbix/5.0/rhel/7/…
阅读更多...
jmeter5.6.3安装教程

jmeter5.6.3安装教程

一、官网下载 需要提前配置好jdk的环境变量 jmeter官网&#xff1a;https://jmeter.apache.org/download_jmeter.cgi 选择点击二进制的zip文件 下载成功后&#xff0c;默认解压下一步&#xff0c;更改安装路径就行(我安装在D盘) 实用jmeter的bin目录作为系统变量 然后把这…
阅读更多...
大数据新视界 -- Hive 数据分区：提升查询效率的关键步骤（下）（8/ 30）

大数据新视界 -- Hive 数据分区：提升查询效率的关键步骤（下）（8/ 30）

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…
阅读更多...
线性代数空间理解

线性代数空间理解

学习线性代数已经很久&#xff0c;但是在使用过程中仍然还是不明所以&#xff0c;比如不知道特征向量和特征值的含义、矩阵的相乘是什么意思、如何理解矩阵的秩……。随着遇到的次数越来越多&#xff0c;因此我决定需要对线性代数的本质做一次深刻的探讨了。 本次主要是参考了3…
阅读更多...
10大排序总结

10大排序总结

1. 冒泡排序 (Bubble Sort) def bubble_sort(arr):n len(arr)# 遍历数组中的每个元素for i in range(n):# 内层循环&#xff0c;从数组的第一个元素到倒数第 i 1 个元素for j in range(0, n - i - 1):# 如果当前元素比下一个元素大&#xff0c;则交换if arr[j] > arr[j …
阅读更多...
最新文章

Copyright @ 2022~2023