位运算之美——用+,-和位运算实现正整数除法和取模(一)

位运算之美——用+,-和位运算实现正整数除法和取模(一)

9月21日，对本文从格式到部分内容上都进行了修改
另外，鉴于某些转载没有注明出处，考虑到版权问题，特声明如下：
作者：翼帆@cppblog 
原文地址：http://www.cppblog.com/xiaoyisnail/archive/2009/09/19/96707.html
本文版权归作者和cppblog共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

    今天看了一位师兄去年的笔经总结，其中有一题是“不许用%和/来实现求任意数除以3的余数”，我想考官的目的应该是想考察学生对位运算的熟悉程度吧，于是我把题目扩展成“只能用+,-和位运算实现正整数除法(/)和取模(%)”，注意：这里不能使用其它的库例程来辅助计算，如log,log10等。在思考这道题目的过程中，我又涉及到了许多二进制相关的题目，如：
    判断给定的整数是不是2的整数次幂
    判断给定的整数是不是4的整数次幂
    求给定整数的二进制表示中1的个数
    求给定整数的二进制表示中0的个数
    求给定整数的二进制表示中最高位1的位置
    求大于等于给定整数的最小的2的整数次幂
    求给定整数的二进制表示的有效位数
    ...
    9月21日补充：这里只考虑值为正整数的情况。
    这些题目都是经典老题，频繁出现于各类笔试面试题中，除了能考察位运算外，还能考察应聘者能否给出创新的算法来更好地解决问题。可以说这些题目都不难，如果使用32位的int来表示整数的话，蛮力法都可以比较好地完成任务，但是如果想尽可能地提高效率，那就需要动一番脑经了。下面给出我对这些问题的整理和C++实现，并在下次的文章中给出只用+,-和位运算实现的正整数除法和取模。
    从某种意义上讲，特别是从充分利用底层硬件的计算能力(利用特殊的cpu指令)来看，这些解法肯定不是最优的，所以还希望大侠们多多指点。
   
    判断给定的整数是不是2的整数次幂
    这应该是最简单的，利用最高位是1，其后所有位为0的特性，常数时间解决问题：

1 //判断n是否是2的正整数冪
2 inline bool is_2exp(unsigned int n)
3 {
4     return !(n&(n-1));
5 }

    求给定整数的二进制表示中1的个数
    考虑到n-1会把n的二进制表示中最低位的1置0并把其后的所有0置1，同时不改变此位置前的所有位，那么n&(n-1)即可消除这个最低位的1。这样便有了比顺序枚举所有位更快的算法：循环消除最低位的1，循环次数即所求1的个数。此算法的时间复杂度为O(n的二进制表示中的1的个数)，最坏情况下的复杂度O(n的二进制表示的总位数)。

 1 //计算n的二进制表示中1的个数
 2 inline int count1(unsigned int n)
 3 {
 4     int r = 0;
 5     while(n)
 6      {
 7         n &= n-1;
 8         r++;
 9     }
10     return r;
11 }

    既然有了求给定整数的二进制表示中1的个数的办法，那么想要求给定整数的二进制表示中0的个数就很简单了。事实上，在二进制中，完全可以把0和1看作是对称的两个对象，取反操作(~)可以任意的切换这两个对象，只要先对n进行一次取反，然后再用上述算法即能得到二进制表示中0的个数。首先看下面的代码：

 1 //计算n的二进制表示中0的个数
 2 inline int count0_wrong(unsigned int n)
 3 {
 4     int r = 0;
 5     n &= ~n;
 6     while(n)
 7      {
 8         n &= n-1;
 9         r++;
10     }
11     return r;
12 }

    不知大家有没有看出问题来？是的,~操作符会把所有高位的都取反，而不是只把有效位取反，所以我们需要一个能保持高位不变的位取反操作，下面是我的实现，时间复杂度和求二进制表示中1的个数的算法相同，都与二进制表示中1的个数有关：

 1 //保持高位取反
 2 inline unsigned int negate_bits(unsigned int n)
 3 {
 4     if(n==0) return 1;
 5     unsigned int r=0, m=~n;
 6     while(n)
 7      {
 8         r |= (n^(n-1))&m;
 9         n &= n-1;
10     }
11
12     return r;
13 }

    有了这个特殊的取反操作，求给定整数的二进制表示中0的个数的办法就简单了：

 1 //计算n的二进制表示中0的个数
 2 inline int count0( unsigned int n)
 3 {
 4     int r = 0;
 5     n = negate_bits(n);
 6     while(n)
 7      {
 8         n &= n-1;
 9         r++;
10     }
11     return r;
12 }

    看到这里，聪明的读者肯定看出问题来了，其实我干了一件很蠢的事情。看看上述算法的时间复杂度，negate_bits花了O(n的二进制表示中1的个数)，while循环计算取反后的n的二进制表示中1的个数，事实上就是O(n的二进制表示中0的个数)，两部分加起来其实就是二进制表示总的有效位数，换句话说，这个算法是线性的，而事实上，我们完全可以先线性地求出这个总的有效位数，然后减去1的位数，即得到0的位数，根本不用费那么大劲去整个保持高位的取反操作，两者的时间复杂度在渐进意义上也是相同的。所以，我犯傻了，但是这里又引出另一个问题：

    求给定整数的二进制表示的有效位数
    上面提到了线性地求这个位数(下文记为m)，即“循环右移1位，记录右移次数”，时间复杂度O(m)。但是我想，一看到这个题目，所有人的第一反应应该是floor(log2(n))+1吧，但是请注意，本文在一开始就规定了“不能使用库例程”，那么在这个限制下该怎么做呢？有没有比线性时间更好的算法呢？其实到目前为止我也没有什么特别好的算法，希望谁有什么精妙的算法能指点一下，不要打我。。。

 1 //求给定整数的二进制表示的位数，线性算法
 2 int count_bit(unsigned int n)
 3 {
 4     int r = 0;
 5     while(n)
 6      {
 7         n>>=1;
 8         r++;
 9     }
10     return r;
11 }

    求大于等于给定整数的最小的2的整数次幂
    首先是最简单的思路：求出n的二进制表示的总位数m，于是1<即为所求值，当然这里要排除n自身就是2的整数次幂的情况，复杂度O(m)，实现如下：

 1 //求大于等于n的最小的2的正整数冪，方法1
 2 //时间复杂度O(n的二进制位长度)
 3 unsigned int high_2exp_1(unsigned int n)
 4 {
 5     if(n<=1) return 1;
 6     if(is_2exp(n)) return n;
 7
 8     unsigned int r = 1;
 9     while(n)
10      {
11         n >>= 1;
12         r <<= 1;
13     }
14
15     return r;
16 }

    事实上这就涉及到上面求二进制表示位数的问题，所以目前为止在此基础上的算法都是线性时间的。   
    那有没有不用计算位数m，从而效率更好的算法呢，能不能像在计算二进制表示中1的个数时那样根据1的个数来设计算法呢？回到那一题中，“n-1会把n的二进制表示中最低位的1置0并把其后的所有0置1”，那么n|=n-1就把n的二进制表示中最低位1后的所有0置1，再加上1，那么就把最低位1左移了一位。于是，便有了更好的算法：循环左移最低位的1，直到n是2的整数次幂。该算法跟二进制表示中的1的个数和位置有关，最坏时间复杂度还是O(二进制表示位数)，但是比起上一个实现，这个算法在多数情况下都比上一个算法快。实现如下：

 1 //求大于等于n的最小的2的正整数冪，方法2
 2 //计算时间与n的二进制表示中1的个数和位置有关，比方法1效率高
 3 //最坏情况下的时间复杂度与方法1相同
 4 unsigned int high_2exp_2(unsigned int n)
 5 {
 6     if(n<=1) return 1;
 7
 8     while(!is_2exp(n))
 9      {
10         n |= n-1;
11         n++;
12     }
13
14     return n;
15 }

    
    最后来一个简单的扩充题目：
    判断给定的整数是不是4的整数次幂
    观察4的整数次幂的特征，容易发现除了满足n&(n-1)==0外，唯一的1位后的0的个数是偶数，这从4^x=2^2k也能简单地得到。这就很直观地衍生出一个简单的算法：

 1 //判断n是否是4的整数次幂
 2 bool is_4exp(unsigned int n)
 3 {
 4     if(!is_2exp(n)) return false;
 5
 6     int bit_len = count_bit(n)-1;//线性时间求二进制位数
 7     if((bit_len&0x1)!=1)
 8         return true;
 9     else
10         return false;
11 }

    算法很直观，但是比起is_2exp的常数时间is_4exp的线性时间总让我觉得不能接受，不过无奈还是没有想出好办法来，哎。。。求大牛指点啊
   
    说明：写这篇文章，已经三次丢失全文了，把我快搞疯了，firefox下好像有点问题，先把文章发上来，过会儿换到IE下继续。。。
    再说明：换了IE后就没再出问题了，不过写着写着发现写了好久，先歇会儿，得看书补习功课了
    最后的说明：下次会给出本文最初提出的问题(只能用+,-和位运算实现正整数除法(/)和取模(%))的实现。