frendguo's blog

不使用运算符(+、-、*、/) 来进行四则运算(C#)

最近在LeetCode 上刷题,遇到一个非常有趣的题目,题目的大概意思就是在不使用运算符的情况下实现两个数的加法。。。原题点这里》》》
说实话,刚看到这题目,我是一脸懵逼的。
后来仔细想想,如果不能用运算符,那肯定是用原始方法了(位运算)。
后来,的确也证明我的想法是正确的。不过还是有种思路没想到,是参考了网上的。
在这里,我就来说说我所知道的两个方案。方法low,大牛可以点击右上角的×了。。。
注:以下讨论均基于整数之间的四则运算!部分来自网络~

【加法】

方案一(推荐):

此方法参照计算机的二进制计算
分两步:
  一:先进行没有进位的加法运算。可用 a^b;
  二:处理进位信息。a&b 可得到进位的位置信息,然后左移一位,就是两数相加后的进位信息了。所以可以用 (a & b) << 1;
    然后就是把前面得到的没有进位的和加上进位信息了,直到进位为0为止。因此代码可以这么写:
public static int GetSum(int a, int b)
        {
            if (b == 0)
            {
                return a;
            }
            int sum = a ^ b;
            int carry = (a & b) << 1;
            int result = GetSum(sum, carry);
            return result;
        }

方案二:

此方案在C#中不常使用。将利用指针的偏移来进行加法运算。
先上代码:
unsafe public static int GetSum_Point(int a, int b)
        {
            unsafe
            {
                byte* c = (byte*)a;
                int d = (int)&c[b];
                return d;
            }
        }
此处附上C#在VS2015中使用指针的方法(传送门)
例如a=5,b=10
c=(byte*) a,此时c的地址为0x00000005
c[b] 就是c的地址偏移sizeof(byte)*b
最终得到了c[b]的地址就是0x0000000f,即通过int强制转换得到15 。

 【减法】

按理来说,只要加法解决了,后面的运算都是小菜一碟了。本着思考的态度,我们还是要想想怎么用位运算来实现减法。
总的来说还是有两个方案实现的,以下依次来说说。

方案一:

原理其实也是参考计算机计算减法的操作。
这里需要用到一个叫“补码”的东西,不懂的同学点这里》》》
 
我们都知道两个数的减法可以当作一个正数和一个负数的加法。照这个思路,我们可以这么写:
public static int GetMargin(int a, int b)
        {
            return GetSum(a, GetSum(~b, 1));
        }

方案二:

此方案和【加法】中的方案一类似。都是二进制的计算
我们分以下几步来看:(以a - b为例)
  1.如果b 的值为0,那么结果显而易见就是a 了。
  2.b 不为0 的情况下,我们仍然先不考虑借位,先将被减数和减数同为1 的位置去掉。
    第一步,找出减数和被减数同为1 的位置。可使用 sameNum = a&b; 来实现;
    第二步,分别将被减数和减数同为1 的位置去掉1 ,这里可以用 a ^= sameNum; b ^= sameNum;
  3.此时,减数和被减数相同位只存在以下三种情况:
被减数:0 ;减数: 0;差:0;
被减数:0 ;减数: 1;差:1;
被减数:1 ;减数: 0;差:1;
  4.通过对被减数、减数和差的分析,很容易就能知道差值应该是被减数和减数的按位或的结果。于是我们便有:a | b 得到临时的结果;
  5.此时再考虑借位问题。很明显只有在减数为1的情况下,被减数与之对应的左一位才会出现借位,于是借位便可以用 b << 1 ; 来表示。
  6.再把临时结果减去借位,直到借位为0 ,得到的结果便是最终的结果了。综上,代码如下:
public static int GetMargin(int a, int b)
        {
            while (b != 0)
            {
                // 去掉被减数和减数中同为1的位
                int sameNum = a & b;
                a ^= sameNum;
                b ^= sameNum;
                
                // 此时,a 和 b 不存在同时为1 的位
                // 0 - 1 和 1 - 0 都为1
                a |= b; // 得到相减的临时结果(不考虑借位)
                b = b << 1; // 减数为1 时,必有借位
            }
            return a;
        }

【乘法】

1.先考虑正整数之间的乘法运算。
  在二进制中,每向左移动一次,都相当于原始数乘以2。而每个数据都可以写成k0×20+k1×21+...+km×2m的形式。因此我们可以得到以下式子:
  a x b = ax20xk0 +  ax21xk1 + .... + ax2mxkm 其中ki = {0, 1};
  因此我们可以很容易写出以下代码:
 
public static int GetProduct(int a, int b)
        {
            // 1.先只考虑正整数的相乘
            int result = 0;
            for (int bits = 1; bits != 0; bits <<= 1)
            {
                if ((bits & b) != 0)
                {
                    result = GetSum(result, a);
                }
                a <<= 1;
            }
            return result;
        }
 2.接下来,开始考虑正负号的情况(考虑溢出的情况)。
  这里有个简单的办法,直接判断a、b和0 的关系来判断正负。本着学习的态度(耳熟😀),我们不使用这种方法。
  我们都知道,在计算机中数据都是以补码的数据存储的,其中正数和负数的区别便是最高位是否为1;(负数的补码最高位为1)
  于是,我们便可以引入一个辅助函数,来帮助判断。
public static int maxNumFlag()
        {
            int bitsOfByte = 8;
            int maxNum = 0x80;
            int tmp = maxNum;
            while (tmp != 0)
            {
                maxNum = tmp;
                tmp <<= bitsOfByte;
            }
            return maxNum;
        }
  完善后的代码如下所示:
public static int GetProduct(int a, int b)
        {
            // 1.先只考虑正整数的相乘
            // 2.考虑正负情况和溢出问题
            int maxNum = maxNumFlag();
            int flag_a = 1;
            if ((maxNum & a) != 0)
            {
                flag_a = 0; // 负数
                a = GetSum(~a, 1);
            }
            int flag_b = 1;
            if ((maxNum & b) != 0)
            {
                flag_b = 0;
                b = GetSum(~b, 1);
            }
            int result = 0;
            for (int bits = 1; bits != 0; bits <<= 1)
            {
                if ((bits & b) != 0)
                {
                    result = GetSum(result, a);
                    if ((result & maxNum) != 0
                        || (a & maxNum) != 0)
                    {
                        throw new Exception("数据过大!");
                    }
                }
                a <<= 1;
            }
            return (flag_a ^ flag_b) == 0 ? result : GetSum(~result, 1);
        }

  【除法】

看到除法,就想起了减法运算,然后想到一个比较简单的思路和实现方法。后来发现网上还有一种方法,思路相同又不同。贴上来,大家看看~

方案一:

  除法没有溢出,但是有其他的限定条件,比如除数不能为“0”。
  这里先说下除法和减法之间的关系。以97÷23=4(余5)为例:
  也就是 97-23×4=5
     :=》97-23-23-23-23=5.
  于是,有以下代码:
public static int GetQuotient(int a, int b)
        {
            /*方法一*/
            if (b == 0)
            {
                throw new Exception("除数不能为0!!");
            }
            int maxNum = maxNumFlag();
            int flag_a = 1;
            if ((maxNum & a) != 0)
            {
                flag_a = 0; // 负数
                a = GetSum(~a, 1);
            }
            int flag_b = 1;
            if ((maxNum & b) != 0)
            {
                flag_b = 0;
                b = GetSum(~b, 1);
            }
            int index = 1;
            int tmp = GetMargin(a, b);
            if (tmp < 0)
            {
                return 0;
            }
            while (tmp >= b)
            {
                tmp = GetMargin(tmp, b); // 最后一次循环后的tmp 便是a/b 的余数
                index = GetSum(index, 1);
            }
            return (flag_a ^ flag_b) == 0 ? index : GetSum(~index, 1);
        }

方案二:

  方案二的大体思路如下:
预备工作:置商为0;
判断“被除数>=除数 ”是否成立:
成立,继续步骤3;
不成立,被除数的值赋给余数,计算结束。
备份除数,并设置商分子(一个临时变量,最终需加到商上面,故暂且如此命名)为1;
对商分子和除数同步向左移位,直到继续移位将大于被除数时为止;
从被除数上减去除数,并将商加上商分子。
通过备份的除数值还原除数,跳转到步骤2继续执行。
  个人还是觉得这样比较难理解,但是因为我们这讨论的是位运算,所以还是贴出来,研究研究。
 
  直接上代码:
public static int GetQuotient(int a, int b)
        {
            /*方法二*/
            if (b == 0)
            {
                throw new Exception("除数不能为0!!");
            }
            int maxNum = maxNumFlag();
            int flag_a = 1;
            if ((maxNum & a) != 0)
            {
                flag_a = 0; // 负数
                a = GetSum(~a, 1);
            }
            int flag_b = 1;
            if ((maxNum & b) != 0)
            {
                flag_b = 0;
                b = GetSum(~b, 1);
            }
            int quotient = 0;
            int backupB = b;
            while (a >= b)
            {
                int tempB = b << 1;
                int tempQ = 1;
                while ((tempB <= a) && ((tempB & maxNumFlag()) == 0))
                {
                    b = tempB;
                    tempQ <<= 1;
                    tempB <<= 1;
                }
                a = GetMargin(a, b);
                quotient |= tempQ;
                b = backupB;
            }
            if (((maxNum & a) != 0) && (a != 0))
            {
                quotient = GetSum(quotient, 1);
            }
            return (flag_a ^ flag_b) == 0 ? quotient : GetSum(~quotient, 1);
        }
 Happy Coding!o(* ̄▽ ̄*)o

Add comment

Loading