wordpress火车头发布模板,谷歌seo博客,关键字排名优化公司,wordpress gzip插件设计一个函数把两个数字相加。不得使用 或者其他算术运算符。
示例:
输入: a 1, b 1
输出: 2 提示#xff1a;
a, b 均可能是负数或 0结果不会溢出 32 位整数
我的答案#xff1a;
一、信息
1.设计一个函数把两个数相加
2.不得使用或者其他运算符
3.a,b均为负数或…
设计一个函数把两个数字相加。不得使用 或者其他算术运算符。
示例:
输入: a 1, b 1
输出: 2 提示
a, b 均可能是负数或 0结果不会溢出 32 位整数
我的答案
一、信息
1.设计一个函数把两个数相加
2.不得使用或者其他运算符
3.a,b均为负数或0
4.结果不会溢出32位整数
二、分析
问题出现
1.如何实现不用加法就实现两数相加呢
我的思路:
思路1通过将a,b转化成二进制这样我们就能用二进制加法求解了。
新的问题出现
该如何实现二进制加法呢
首先我们可以观察二进制加法的规律 1101
1010 10111
规律就是
1 0 得1
1 1 得0
0 0 得0
我的答案其实很简单我们只需要通过与异或运算即可实现
问题2该如何避免结果不会溢出32位整数呢
我的实现
为了不使用或其他算术运算符来实现数字的加法我们可以使用位操作。以下是基于此思路的解决方案
### 1. C语言
#include stdio.hint add(int a, int b) {while (b ! 0) {unsigned int carry (unsigned int)(a b) 1; // 计算进位a a ^ b; // 不计算进位的加法b carry; // 把进位放在b上继续进行加法}return a;
}int main() {int a 1, b 1;printf(Sum: %d\n, add(a, b));return 0;
}
2. C
#include iostreamint add(int a, int b) {while (b ! 0) {unsigned int carry (unsigned int)(a b) 1;a a ^ b;b carry;}return a;
}int main() {int a 1, b 1;std::cout Sum: add(a, b) std::endl;return 0;
}
JAVA
public class AddWithoutPlus {public static int add(int a, int b) {while (b ! 0) {int carry a b; // 计算进位a a ^ b; // 不计算进位的加法b carry 1; // 把进位放在b上继续进行加法}return a;}public static void main(String[] args) {int a 1, b 1;System.out.println(Sum: add(a, b));}
}这些解决方案都是基于二进制表示的加法原理利用位操作来实现的。当我们加两个二进制数时可以分为两步1) 不计算进位的加法和 2) 计算进位。
英雄师傅的分析
将a和b都转化成二进制以后执行相加举个简单的例子例如a是21(二进制是10101)b是12二进制是1100它们两个相加的值应该是33 对于两个数的对应相加如果不产生进位就是异或的结果。在我看来就是用异或来模拟这个过程
比如说
唯一没有提到的就是1和1相加的情况这种情况会产生进位所以异或结果并不等于相加的结果但是异或的结果等于相加后低位的值。换言之1110异或结果等于00和0相等很合理。
基于上述观点如果两个数二进制在相加的过程中都没有出现1和1的情况那么加法就等于两个数的异或。如果有进位那么就要把进位的那部分单独拎出来。
什么时候有进位呢当两个都为1的时候也就是两个位与为1的时候所以我们可以把ab拆成两个部分
a^b和ab
英雄师傅的实现过程
int add(int a, int b){if(b0){return a;}return add(a^b,((unsigned int)(ab))1);
}Leetcode 题解
Leetcode地址Leetcode题解
方法一位运算 预备知识
有符号整数通常用补码来表示和存储补码具有如下特征
正整数的补码与原码相同负整数的补码为其原码除符号位外的所有位取反后加 111。
可以将减法运算转化为补码的加法运算来实现。
符号位与数值位可以一起参与运算。
思路和算法
虽然题目只要求了不能使用算术运算符但是原则上来说也不宜使用类似的运算符 \texttt{} 和 -\texttt{-}- 以及 sum\texttt{sum}sum 等方法。于是我们使用位运算来处理这个问题。
首先考虑两个二进制位相加的四种情况如下
0 0 0 0 1 1 1 0 1 1 1 0 (进位) 可以发现对于整数 aaa 和 bbb
在不考虑进位的情况下其无进位加法结果为 a⊕b\texttt{a} \oplus \texttt{b}a⊕b。
而所有需要进位的位为 a b\texttt{a \ b}a b进位后的进位结果为 (a b) 1\texttt{(a \ b) 1}(a b) 1。
于是我们可以将整数 aaa 和 bbb 的和拆分为 aaa 和 bbb 的无进位加法结果与进位结果的和。因为每一次拆分都可以让需要进位的最低位至少左移一位又因为 aaa 和 bbb 可以取到负数所以我们最多需要 log(max_int)\log (max\_int)log(max_int) 次拆分即可完成运算。
因为有符号整数用补码来表示所以以上算法也可以推广到 000 和负数。
实现
在 C\texttt{C}C 的实现中当我们赋给带符号类型一个超出它表示范围的值时结果是 undefined\text{undefined}undefined而当我们赋给无符号类型一个超出它表示范围的值时结果是初始值对无符号类型表示数值总数取模的余数。因此我们可以使用无符号类型来防止溢出。
在 Python\texttt{Python}Python 的实现中因为 Python\texttt{Python}Python 的整数类型为是无限长的所以无论怎样左移位都不会溢出。因此我们需要对 Python\texttt{Python}Python 中的整数进行额外处理以模拟用补码表示的 323232 位有符号整数类型。具体地我们将整数对 2322^{32}2 32 取模从而使第 333333 位及更高位均为 000因为此时最终结果为用补码表示的包含符号位的 323232 位整数所以我们还需要再次将其换算为 Python\texttt{Python}Python 的整数。
C:
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;}
};
JAVA:
class Solution {public int add(int a, int b) {while (b ! 0) {int carry (a b) 1;a a ^ b;b carry;}return a;}
} 总结
个人
从这个问题中我们可以学到多方面的知识和技能
1. **基础计算机科学知识**这道题目介绍了如何使用位操作来模拟基本的算术运算这反映了计算机在底层如何处理加法。
2. **递归和迭代思维**即使在这样的问题中递归和迭代的应用也是一个重要的思维模式。我们反复应用相同的逻辑直到达到预期的结果。
3. **处理边界情况**考虑到整数溢出和32位限制这提醒我们在解决问题时总是要注意潜在的边界情况和限制。
4. **位操作技能**位操作是许多算法和数据结构问题中的一个关键技能。这道题目为我们提供了一次实际应用的机会加深了我们对AND、XOR、左移等操作的理解。
5. **创新思维**当面对某些明显的方法例如使用加法运算符不可用时寻找其他解决方案需要创新思维。这种思维方式对于不断发展的计算机科学领域是至关重要的。
6. **优化和效率**尽管我们可以使用递归来解决此问题但递归可能会导致效率问题特别是对于大的整数。这提醒我们即使某个方法是可行的我们仍然需要考虑其效率。
7. **实际应用与理论知识**在真实的计算机系统中加法和其他算术操作确实是通过硬件逻辑例如加法器和位操作来实现的。通过这种方法我们不仅学习了一种算法技巧而且还深入了解了计算机的工作原理。
总的来说这道题目为我们提供了一次深入学习计算机科学基础、算法设计和优化的机会并激发了我们的创新思维。
感受
其实这道题目和计算机组成原理中定点加法和减法这一章很像象在哪里呢其实就是像在对二进制加法的推导和探索其中二者都处理了很多进位问题。其实我觉得出题人是想让我们体验一把当初计算机科学家们是如何一步一步设计出加法器的就是绕开编译器原本就带着的法函数而是自己写一个这个函数的底层。
传送门计算机组成原理 2.2 定点加法
