一些基本的位操作

判断整数的奇偶性：if((n & 1) == 0)

乘以2操作：n << 1

向下整除n // 2：n >> 1

实现某些库函数

乘法的实现

如何不用任何运算符计算两个正整数的乘积？

思路分析：

  • 先判断a和b的正负，保存正负号，如果a或者b是负数，要把a和b转换成正数；

  • 假设两个数a * b，相当于把a自加(b-1)次，而a的自加，可以通过位运算来实现，即a+a相当于a * 2，即把a向左移一位，如此只需做(b-1)的左移即可；a左移一位，增大一倍，b就右移一位，减少一半；此外当b为奇数时，保存a的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int multiplication(int a, int b)
{
    int sign = 1;
    if (b < 0)
    {
        sign = -sign;
        b = -b;
    }
    if (a < 0)
    {
        sign = -sign;
        a = -a;
    }
	
    // 以12*7为例子
    int ret = 0;
    while(b)
    {
        // 12 * 7
        if (b & 1 == 0)	// b为奇数
        {
            ret = ret + a; // ret先加上一个a,ret = 0 + 12
        }
        // 经过上一步，12 * 7 变为 12 * 6
        // 再把12*6->12*2*3->24*3->24*2
        a <<= 1;	// 相当于a*2
        b >>= 1;	// 相当于b减少一半
    }
    return ret*sign;
}