【整活】C++不用加减乘除模运算符实现加减乘除模
Tuesday, February 21, 2023
本文共1205字
3分钟阅读时长
⚠️本文是作者P3troL1er原创，首发于https://peterliuzhi.top/posts/%E6%95%B4%E6%B4%BBc++%E4%B8%8D%E7%94%A8%E5%8A%A0%E5%87%8F%E4%B9%98%E9%99%A4%E6%A8%A1%E8%BF%90%E7%AE%97%E7%AC%A6%E5%AE%9E%E7%8E%B0%E5%8A%A0%E5%87%8F%E4%B9%98%E9%99%A4%E6%A8%A1/。商业转载请联系作者获得授权，非商业转载请注明出处！
Always tell the truth. That way, you don’t have to remember what you said.
— Mark Twain
最近在上数字逻辑，想起以前做过的一道算法题（不用加法符实现两数相加），突发奇想想要纯用位运算实现一下加减乘除模
以前最多实现加减乘，对除法一直没想到纯粹位运算的方式，今天算是“圆梦”了
注意，我写的这几个函数只能用于整数（包括int、long、long long还有他们的unsigned形式），使用C++主要是可以使用模板实现泛型，如果纯用C可能就需要转成void*之类的比较复杂的操作（或者使用宏中的##连接符实现重载）
下面是具体的代码，如果您发现了bug可以在下面的评论告诉我~
template <typename NUM>
NUM add(NUM a, NUM b){
while (b != 0)
{
// 筛选出a中位为1的同时b中位为1，然后左移一位当作进位
NUM tmp = (a & b) << 1;
a ^= b;
b = tmp;
}
return a;
}
template <typename NUM>
NUM minus(NUM a, NUM b){
while (b != 0)
{
// 筛选出a中位为0的同时b中位为1，然后左移一位当作进位
NUM tmp = ((~a) & b) << 1;
a ^= b;
b = tmp;
}
return a;
}
template <typename NUM>
NUM multiply(NUM a, NUM b){
bool sign = false;
if (a < 0)
{
sign = !sign;
a = add(~a, 1);
}
if (b < 0)
{
sign = !sign;
b = add(~b, 1);
}
// 有一个等于0直接返回
if (a == 0 || b == 0)
{
return 0;
}
NUM sum = 0; // 记录结果
char cnt = 0; // 记录左移多少位
while (b != 0)
{
// 如果这位是1，就要将a左移cnt位并加上
if (b & 0x1)
{
sum = add(sum, a << cnt);
}
b >>= 1;
++cnt;
}
// 处理符号
if (sign)
{
return add(~sum, 1);
}else
{
return sum;
}
}
template <typename NUM>
NUM* basic_divide(NUM a, NUM b, NUM* ret){
if (a == 0)
{
ret[0] = 0;
ret[1] = 0;
return ret;
}else if (b == 0)
{
ret[0] = a;
ret[1] = 0;
std::cerr << "dividing 0!\n";
return ret;
}
bool sign = false;
if (a < 0)
{
sign = !sign;
a = add(~a, 1);
}
if (b < 0)
{
sign = !sign;
b = add(~b, 1);
}
NUM result = 0;
NUM max = b;
char cnt = 1;
while ((b << 1) < a)
{
b <<= 1;
++cnt;
}
while (cnt > 0)
{
if (a >= b)
{
a = minus(a, b);
result = (result << 1) ^ 0x1;
}else
{
result <<= 1;
}
b >>= 1;
--cnt;
}
if (sign)
{
ret[0] = add(~result, 1);
ret[1] = add(~a, 1);
}else
{
ret[0] = result;
ret[1] = a;
}
return ret;
}
template <typename NUM>
NUM divide(NUM a, NUM b){
NUM result[2] {0};
return basic_divide(a, b, result)[0];
}
template <typename NUM>
NUM mod(NUM a, NUM b){
NUM result[2] {0};
return basic_divide(a, b, result)[1];
}
由于模板函数的定义和声明不能分开，所以这些代码都得放在头文件中，当然也可以放在cpp文件中然后在头文件包含它：
#ifndef __ARITH_ARITH_H__
#define __ARITH_ARITH_H__
#include "arith.cpp"
#endif /* __ARITH_ARITH_H__ */
加法的思路就是用且运算获取同为1的位，然后左移一位作为进位，一直while循环直到进位为0
减法的思路就是用复杂的位运算获取被减数为0而减数为1的位，然后左移一位作为借位，一直while循环直到借位为0
乘法的思路就是将其中一个乘数看作数个权值的和，比如3 = 0b11 = 2^0 + 2^1，而一个数乘以2的n次方可以看作向左移动n位，然后将他们全部加起来就是结果了（乘法很可能溢出……在汇编中mul指令会把结果放在两个寄存器中，我比较懒，这么搞比较复杂，就没有搞）
除法的思路就是左移除数让其刚好再移一位就大于被除数，然后被除数减去它，并在结果推进一个1，这时候被除数的总位数一定会少一位（因为除数*2 > 被除数，那么被除数 - 除数一定会小于被除数 » 1），然后让除数右移一位，如果此时被除数小于除数，就在结果推进一个0，然后再右移除数……本质上是模拟竖式除法运算。这个思路可以一次性得出结果和余数。
笔者的思路可能不是最高效的，也可能有一定问题，如果您读完本文及代码，有一些疑问或建议，欢迎在评论区指出！谢谢！
扫码阅读此文章
点击按钮复制分享信息
点击订阅