整数除法的位运算实现与边界处理
问题背景
实现两个整数的除法运算，返回整数结果。要求不得使用乘法、除法和取模运算符。
解决方案
基础思路是通过被除数减除数计数实现，但当被除数远大于除数时效率低下。优化方案采用位移操作加速减法过程：每次将除数按2的幂次扩大，当扩大后的值超过当前被除数时，减去前一次扩大值并累加对应倍数。
算法步骤：
- 处理边界情况（除数为0或INT_MIN/-1）
- 确定结果符号位
- 将被除数和除数转为正数（使用long long防溢出）
- 循环执行位移减法：每次寻找不超过当前被除数的最大除数位移值
- 累加位移倍数得到商
#include <iostream>
#include <climits>
#include <cmath>
using namespace std;
int integer_divide(int num1, int num2) {
if (num2 == 0 || (num1 == INT_MIN && num2 == -1))
return INT_MAX;
int result_sign = ((num1 < 0) ^ (num2 < 0)) ? -1 : 1;
long long abs_num1 = llabs(num1);
long long abs_num2 = llabs(num2);
long long quotient = 0;
while (abs_num1 >= abs_num2) {
long long divisor_temp = abs_num2;
long long multiplier = 1;
while (abs_num1 >= (divisor_temp << 1)) {
divisor_temp <<= 1;
multiplier <<= 1;
}
abs_num1 -= divisor_temp;
quotient += multiplier;
}
return result_sign == 1 ? quotient : -quotient;
}
int main() {
cout << integer_divide(15, 3) << endl; // 输出5
return 0;
}关键技术细节
1. 边界处理：对INT_MIN取绝对值需使用long long类型，避免32位整数溢出。当输入为INT_MIN和-1时直接返回INT_MAX
2. C++数据类型范围参考：
| 类型 | 字节数 | 取值范围 |
|---|---|---|
| int | 4 | -2,147,483,648 到 2,147,483,647 |
| long long | 8 | -9,223,372,036,854,775,808 到 9,223,372,036,854,775,807 |
| unsigned int | 4 | 0 到 4,294,967,295 |
3. 位移运算性能测试：
#include <iostream>
#include <ctime>
using namespace std;
const long long TEST_COUNT = 100000000;
void measure_shift_perf() {
clock_t timer1, timer2;
int int_val;
long long ll_val;
timer1 = clock();
for (int i = 0; i < TEST_COUNT; i++) {
for (int bits = 0; bits < 30; bits++) {
int_val << bits;
}
}
timer2 = clock();
double int_duration = double(timer2 - timer1)/CLOCKS_PER_SEC;
timer1 = clock();
for (int i = 0; i < TEST_COUNT; i++) {
for (int bits = 0; bits < 30; bits++) {
ll_val << bits;
}
}
timer2 = clock();
double ll_duration = double(timer2 - timer1)/CLOCKS_PER_SEC;
cout << "int位移耗时: " << int_duration << "秒\n";
cout << "long long位移耗时: " << ll_duration << "秒";
}
int main() {
measure_shift_perf();
return 0;
}