【有书共读】《算法与数据结构题目最优解》（在线编程题总结7）

       该书第七章——《位运算》，参考博客：https://blog.csdn.net/shanghairuoxiao/article/details/75386508，主要是关于位运算的一些基础知识的理解。

位运算是面试中的常见考题一种，位操作有~, <<, >>, &, |, ^六种。

左移和右移规则
       对左移而言，移动正数和负数规则是相同的；对于右移而言，则有些差别，正数补0，负数补1。 举例说明： 
       对于一个16位的整数：0000 0000 0000 0101，左移一位是0000 0000 0000 1010，右移一位是0000 0000 0000 0010 
       对于一个16位的负数：1000 0000 0000 0101，左移一位是0000 0000 0000 1010，右移一位是1100 0000 0000 0010

       下面通过几个典型的题目来透彻分析位运算的一些常用技巧。

（1）技巧一
       对于正整数，左移一位，就是将数值乘2；右移一位就运算数值除2；但是位操作的效率要比运算符高。
（2）技巧二
       一个数和另一个数异或两次得到的还是原来的数。

a = a ^ b; b = a ^ b; a = a ^ b; 

int fun(int num)
{ int count = 0; while(num)
    {
        num = num & (num - 1);
        ++count;
    } return count；
}

• 题：判断一个数是不是2的幂。

//返回0表示是2的幂，返回非0值表示不是2的幂 int fun(int num)
{ return n & (n - 1);
}

      解析：如果一个数是2的幂，则其有且只有一位为1。因此，消除这一位后就会变成0。

• 题：判断一个32位整数是不是4的幂。

//返回0表示不是4的幂，返回非0表示是4的幂 int fun(int num)
{ if(!(n & (n - 1)))
    { return (n & 0x55555555);
    } return 0;
}

        解析：是4的幂的数一定是2的幂，因此先判断是不是2的幂，2的幂中1在基数位上的是4的幂，与0x55555555按位与，如果在基数位上有数则不为0。

• 题：输入两个整数m和n，计算需要改变多少位能使m变成n。

int fun(int m, int n)
{
    //将m和n按位异或，相同的位为0，不同的位为1
    m = m ^ n;
    int count = 0;
    //统计不同的位有多少个就ok
    while(m)
    {
        m = m & (m - 1);
        ++count;
    }
    return count；
}

（4）技巧四

       n & (~n + 1)提取出整数n最后一位为1的数 。
       举例：n = 01101，~n是将n按位取反就是10010，~n + 1 = 10011，最后，n & (~n + 1) = 00001

• 题：统计一个整数中二进制位上1的个数。

int fun(int num)
{ int count = 0; while(num)
    {
        n -= n & (~n + 1);
        ++count;
    } return count；
}

（5）技巧五

        不使用+，-，*，/完成整数相加

int Add(int num1, int num2)
 {
     int sum, carry;
     do{
         //将两个数异或，模拟加法中相加不进位的结果
         sum = num1 ^ num2;
         //只考虑进位的情况
         carry = (num1 & num2) << 1;
         num1 = sum;
         num2 = carry;
     }
     while(num2 != 0); //将结果相加的过程就重复上述过程，直到进位为0

     return sum;
 }

举例分析代码过程： 
将12(二进制表示为0000 1100)与5(二进制表示为0000 0101)相加

第一次循环： 
0000 1100 ^ 0000 0101 = 0000 1001 
(0000 1100 & 0000 0101) << 1 = 0000 1000

第二次循环： 
(0000 1001 ^ 0000 1000) = 0000 0001 
(0000 1001 & 0000 1000) << 1 = 0001 0000

第三次循环： 
(0000 0001 ^ 0001 0000) = 0001 0001 
(0000 0001 & 0001 0000) << 1 = 0000 0000

循环结束 
结果为0001 0001 = 17
--------------------- 
最后，感谢该文博主：https://blog.csdn.net/shanghairuoxiao。