使用位运算实现int32位整数的加减乘除

ゝ一世哀愁。 2023-06-04 04:57 43阅读 0赞

我觉得比较难想的是加法吧。

首先加法，脑海中脑补二进制加法，相同位相加，超过2 ，则进1，留0

那么用位运算怎么实现呢？其实理解了异或和与操作，就很容易想出来了。

我觉得异或操作和与操作完全就是实现加法的。 异或就是相同位相加最后留下的结果，而与就是相同位相加是否进1的结果。

异或：相同位 相同为0，不同为1。  
与：相同位 都是1结果才是1，否则都是0。

这不就是二进制相加吗？  
异或 与  
1+1 = 0 进1

1+0 = 1 进0

0+0= 0 进0

所以加法就是，每次先异或一下，然后算出来进位的结果，再左移一位，因为是进位嘛

static int Add(int x, int y)
            {
                while (y != 0)
                {
                    int z = x;
                    x ^= y;
                    y &= z;
                    y <<= 1;
                }
    
                return x;
            }

减法，就很容易实现了，减一个数等于加上这个数的负数

一个数怎么变成负数呢？取反码然后+1

所以减法就是

static int Sub(int x, int y)
            {
                int z = Add(~y, 1);
                return Add(x, z);
            }

那么乘法呢，简单的想法是，一个一个想加呗，a\* b不就是b个a相加，对不对，想法的是对的，但是我们要利用二进制的思想，也就倍增的思想。

任何两个数相乘可以看成，举个例子

15 \* 19

= 15 \* 1 + 15 \* 2 + 15 \* 16

而15 \* 1 就是 15 << 0  
15 \* 2 就是 15 << 2

所以原本要加19次的，现在变成了加三次，并且每次向左移动一位就可以了。

那么怎么把19 变成 16 + 2 + 1呢？

很简单，for 循环，看代码吧

static int Multiply(int x, int y)
            {
                int res = 0;
    
                for (int i = 30; i >= 0; i--)
                {
                    if ((1 << i) <= y)
                    {
                        res = Add(res, x << i);
                        y = Sub(y, 1 << i);
                    }
    
                    if (y == 0)
                        break;
                }
    
                return res;
            }

除法和乘法类似，我们可以用倍增的思想，任何数字都可以由2^x+2^y+2^z......组成的。

所以我们用被除数减去 除数\*2^x ，那么商就+= 2^x ,然后减去得到差，继续再减 除数的2^x

c++

static int Dev(int x, int y)
            {
                int res = 0;
                for (int i = 30; i >= 0; i--)
                {
                    if (y << i <= 0) continue;
                    if (y << i <= x)
                    {
                        res = Add(res, 1 << i);
                        x = Sub(x, y << i);
                    }
    
                    if (x == 0)
                        break;
                }
    
                return res;
            }

最后再补充位运算一个有趣的网站

[http://graphics.stanford.edu/~seander/bithacks.html\#IntegerLog][http_graphics.stanford.edu_seander_bithacks.html_IntegerLog]

[http://www.matrix67.com/blog/archives/3985][http_www.matrix67.com_blog_archives_3985]

转载于:https://www.cnblogs.com/dacc123/p/11408334.html

[http_graphics.stanford.edu_seander_bithacks.html_IntegerLog]: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
[http_www.matrix67.com_blog_archives_3985]: http://www.matrix67.com/blog/archives/3985