《程序员面试金典（第6版）面试题 16.09. 运算

题目描述

请实现整数数字的乘法、减法和除法运算，运算结果均为整数数字，程序中只允许使用加法运算符和逻辑运算符，允许程序中出现正负常数，不允许使用位运算。

你的实现应该支持如下操作：

• Operations() 构造函数
• minus(a, b) 减法，返回a - b
• multiply(a, b) 乘法，返回a * b
• divide(a, b) 除法，返回a / b

示例：

Operations operations = new Operations();
operations.minus(1, 2); //返回-1
operations.multiply(3, 4); //返回12
operations.divide(5, -2); //返回-2

提示：

• 你可以假设函数输入一定是有效的，例如不会出现除法分母为0的情况
• 单个用例的函数调用次数不会超过1000次

解题思路与代码

• 这道题属实是一道中等难度的题。需要你有一定的思考量，才可以做出来。

• 题目的要求是，不允许我们使用位运算符，除了 + 法以外的算术运算符，去实现两个数之间的减法，乘法，除法函数。

• 也就是说，我们可以使用 + 法运算符，关系运算符（==， <= , >=, < , >）还有逻辑运算符 （ ! , && , ||）去实现这些函数。

• 这道题建议大家不要抖机灵，使用各种没有意义的库函数来简便运算。还有这道题也不要去使用vector这种数据结构。因为，vector的模板类在实现时涉及到位运算符和减法运算符的。

接下来，其实我们就要思考一个问题。乘法，除法的本质是什么？

• 那其实是不是就是加法（乘法的本质是加法）与减法（除法的本质是减法）呢？
• 那也就是说，要实现除法函数，首先得实现减法函数。

那我们，在来思考一个问题，减法的本质是什么？

• 那是不是加上一个相反数呢？
• 所以要实现减法函数，首先我们还需要去实现一个取反函数。

其实这道题还有一个隐藏的条件，那就是提示：单个用例的函数调用次数不会超过1000次。

• 也就是说，这道题，出题人不想你太容易去解决这个问题。问你如何优化流程，也就是缩短时间复杂度。
• 假如说我们要用累加去实现取反过程，你想想时间复杂度是不是O(n),那有没有一种办法可以优化累加的时间复杂度呢？
• 当然有。我们可以通过事先创建两个数组，分别去存储正负2的多少次方的值是多少。到时候，我们可以用循环的方式，去累加预定值，这样是不是就将时间复杂度O(n)缩短到O(logn)了呢？

OK，这道题讲到这里，大家应该心里很有谱了才对。做这道题，首先，我们要创建两个内置数组，去存储可能出现的2的次方值。然后先实现取反函数。再实现减法函数，再实现乘法函数，最后实现除法函数。

实现的过程中，需要大家注意溢出问题。因为虽然题目给的值的范围不会超过int的最大最小范围。但是两个数相减，相乘，相除的过程中，如果处理不好，是会发生溢出问题的。

具体的实现请看代码：

class Operations {int posN[31]; // 放正数2的n次方int negN[31]; // 放负数2的n次方//取相反数函数int oppN(int num){if(!num) return 0;int res = 0;if(num > 0){ // 从2^30次方开始检查for(int i = 30; i >= 0; i += (-1)){if(num + negN[i] < 0) continue;num += negN[i];res += negN[i];}}else{ // 从 - 2^30次方开始检查for(int i = 30; i >= 0; i += (-1)){if(num + posN[i] > 0) continue;num += posN[i];res += posN[i];}}return res;}
public:Operations() {int p = 1;int n = -1;posN[0] = p;negN[0] = n;// 初始化次方数组for(int i = 1; i < 31; ++i){p += p;posN[i] = p;n += n;negN[i] = n;}}int minus(int a, int b) {return a + oppN(b);}int multiply(int a, int b) {if(!a || !b) return 0;if(a == 1) return b;if(b == 1) return a;if(b < 0) return oppN(multiply(a,oppN(b))); // 统一b的正负int res = a;int count = 1;while(count < posN[30] && count + count <= b ){res += res;count += count;}res += multiply(a,minus(b,count));return res;}int divide(int a, int b) {if(!a) return 0;int res = 1;if(a > 0){if(b == INT_MIN) return 0;if(b < 0) return oppN(divide(a,oppN(b))); // 统一a，b的正负if(a < b) return 0;int count = b;while(count < posN[30] && a >= count + count){res += res;count += count;}res += divide(minus(a,count),b);}else{if(b == 1) return a;if(b > 0) return oppN(divide(a,oppN(b)));if(a > b) return 0;int count = b;while(count >= negN[30] && a <= count + count){res += res;count += count;}res += divide(minus(a,count),b);}return res;}    
};

复杂度分析

下面是这个代码中各个函数的时间复杂度和空间复杂度分析：

• oppN(int num)：时间复杂度为 O(log(num))，因为它在最坏情况下需要遍历数组 posN 或 negN 中的所有元素（共 31 个），这与输入数字的二进制表示长度成正比。空间复杂度为 O(1)，因为它使用了固定数量的额外存储空间。

• Operations() 构造函数：时间复杂度为 O(1)，因为它只需要遍历 31 个元素并执行一定数量的操作。空间复杂度为 O(1)，因为它只使用了固定大小的 posN 和 negN 数组。

• minus(int a, int b)：时间复杂度为 O(log(b))，因为它调用了 oppN 函数。空间复杂度为 O(1)，因为它没有使用额外的存储空间。

• multiply(int a, int b)：时间复杂度为 O(log(a) * log(b))，因为它使用递归实现，每次递归调用都会减小 b 的值，递归深度为 O(log(b))，而每次递归调用都会调用 minus 函数，时间复杂度为 O(log(a))。空间复杂度为 O(log(b))，因为递归深度与空间复杂度成正比。

• divide(int a, int b)：时间复杂度为 O(log(a) * log(b))，因为它也是使用递归实现，每次递归调用都会减小 a 的值，递归深度为 O(log(a))，而每次递归调用都会调用 minus 函数，时间复杂度为 O(log(b))。空间复杂度为 O(log(a))，因为递归深度与空间复杂度成正比。

总的来说，这个实现的时间复杂度主要取决于输入数字的二进制表示长度，而空间复杂度主要取决于递归深度。

总结

• 这道题的意义在于考察编程能力、逻辑思维和对基本运算的理解。

• 它要求我们在限制条件下（仅使用加法运算符和逻辑运算符）实现整数数字的减法、乘法和除法运算。这种问题有助于锻炼思考能力，强化对计算机基本原理的理解，以及提高解决问题的灵活性。

• 同时，这种问题也有助于理解计算机是如何处理基本的算术运算的，以及为什么某些优化方法（例如位运算）是有效的。通过解决这种问题，你可以加深对计算机科学和编程原理的理解。

• 最后的最后，如果你觉得我的这篇文章写的不错的话，请给我一个赞与收藏，关注我，我会继续给大家带来更多更优质的干货内容。