用位运算实现整数的加减乘除和多种操作

一、常见的位运算操作实现功能

• 1、 负数的等式变换：-n == ~(n-1) == ~n+1。
  负数的二进制形式==补码表示==原码的反码+1

负数在计算机中的二进制是以原码（十进制直接转换）的补码形式存在的。（正数也可以说是这样的，因为正数的原码反码补码都一样）。减法运算时也是用负数的补码在进行加法计算然后得到补码结果存到计算机内存中，要表示成十进制再将补码转换成原码输出为10进制结果。
比如若n=20则n的二进制是00...0010100（int共32bit）
》-n=-20原码是20的原码的符号位变1，即10...0010100，反码是保留符号位其他位取反即11...1101011，反码加1即为补码11...1101100。即二进制的-n==11...1101100。
》二进制的 n-1==00...0010011，取反后~(n-1)==11...1101100。
》二进制的n取反~n==11...1101011，则~n + 1==11...1101100。

• 2、有趣的 n -1。

n -1 是会将最后一个1变为0，然后这个1前面的各位保持不变，后面的各位全变成1（或者这个1刚好是最后一位的话后面没有了）。比如1100 1000-1==1100 0111

n&(n-1)会将从最后一个1及后面的位数全部清零。如上得1100 1000&1100 0111==1100 0000
》 n&~(n-1) 会将最后一个1前面的位数全部清零。如上得 1100 1000&0011 1000== 0000 1000

• 3、 获取整数n的二进制中最后一个1：n&(-n) 或者 n&~(n-1)，或者n&(~n+1)。

如：n=010100，则-n=101100，n&(-n)=000100

• 4、 去掉整数n的二进制中最后一个1：n&(n-1)，

如：n=010100，n-1=010011，n&(n-1)=010000

二、只用位运算实现非负整数（无符号数）的加减乘除，不出现+-*/操作符

（1）加法实现

原理：对于10进制加法，17+39=56，可以看成是对应位数相加的结果，再相加。即个位7+9=16，十位1+3=4，则40+16=56。

对于二进制加法，对应位数的“异或操作”可得到该位的数值，对应位的“与操作”再左移一位后可得到该位产生的高位进位，因此可以很容易地用“异或”和“与”操作实现整数加法运算。如：a=010010，b=100111，计算步骤如下：
a+b== (a^b + (a&b)<<1)循环或递归 + 直到第二个加数等于0。
第一轮：a^b=110101，(a&b)<<1=000100， 由于进位（000100）大于0，则进入下一轮计算，a=110101，b=000100，a^b=110001，(a&b)<<1=001000，由于进位大于0，则进入下一轮计算：a=110001，b=001000，a^b=111001，(a&b)<<1=0，进位为0，终止，计算结果为：111001。

//方法一：使用循环
int bit_add(int a, int b)
{
    int add, carry;  //carry代表进位
    do{
        add = a ^ b;
        carry = (a & b) << 1;
        a = add;
        b = carry;
    } while (carry != 0);

    return add;
}

//方法二：使用递归
int bit_add2(int a, int b)
{
    int add, carry;  //carry代表进位
    if (0 == b)   //退出递归条件，进位为0时
    {
        return a;
    }

    add = a ^ b;
    carry = (a & b) << 1;
    //递归操作
    return bit_add2(add, carry);
}

（2） 减法实现

减法可很容易地转化为加法：a - b = a + (-b) = a + (~b + 1 )

代码如下：

int bit_subtract(int a, int b)
{
    return bit_add(a, bit_add(~b, 1));
}

（3） 乘法实现

先看一个实例：1011*1010：

1011
* 1010
----------
10110 < 1011乘以0010，即左移一位
+ 1011000 < 1011乘以1000，即左移3位
----------
1101110

其思想就是乘法的分配律，1011*1010=11*10=11*(2+8)=11*2+11*2^3

因而乘法可以通过系列移位和加法完成。（暂时不考虑运算结果越界问题）

int bit_multiply(int a, int b)
{
    if (!a || !b)
    {
        return 0;
    }
    int sign_flag = 0; //最终结果的符号，0为正，1为负
    sign_flag = (a > 0) ^ (b > 0);
    //全都转化为正数来计算
    if (a < 0)
    {
        a = bit_add(~a, 1); //-a==~a + 1
    }
    if (b < 0)
    {
        b = bit_add(~b, 1); //-b==~b + 1
    }

    int sum = 0;
    //循环移位b，并同时移位a直到b为0
    while (b != 0)
    {
        int b_bit = b & 1;  //得到b的最后一位是0还是1
        //如果为1，则a移位后的值要加到sum中 
        if (b_bit)
        {
            sum = bit_add(sum, a);
        }
        // b >> 1;      //b右移一位 //这是一个不容易发现的错误，
        //  对数进行移位操作后，还必须赋值
        b = b >> 1;
        a = a << 1;  //同时，a左移一位
    }

    if (sign_flag)
    {
        sum = bit_add(~sum, 1);
    }
    return sum;
}

（4） 除法实现

除法的思想，原本就是利用了减法，除意思是分、瓜分，被除数即是被瓜分的数。比如20/5=4，可理解为20-5减了（瓜分了）4次才减完。
代码如下：

int bit_divide(int a, int b)
{
    if (!a || !b)
    {
        //暂时把除数b为0的错误结果也当做0
        return 0;
    }
    int sign_flag = 0; //最终结果的符号，0为正，1为负
    sign_flag = (a > 0) ^ (b > 0);
    //全都转化为正数来计算
    if (a < 0)
    {
        a = bit_add(~a, 1); //-a==~a + 1
    }
    if (b < 0)
    {
        b = bit_add(~b, 1); //-b==~b + 1
    }

    int divide_times = 0;
    while (a >= b)
    {
        divide_times = bit_add(divide_times, 1);
        a = bit_subtract(a, b);
    }

    if (sign_flag)
    {
        //结果为负，则负数补码=反码+1
        divide_times = bit_add(~divide_times, 1);
    }
    return divide_times;
}