本文共 3695 字,大约阅读时间需要 12 分钟。
今天看了一位师兄去年的笔经总结,其中有一题是“不许用%和/来实现求任意数除以3的余数”,我想考官的目的应该是想考察学生对位运算的熟悉程度吧,于是我把题目扩展成“只能用+,-和位运算实现正整数除法(/)和取模(%)”,注意:这里不能使用其它的库例程来辅助计算,如log,log10等。在思考这道题目的过程中,我又涉及到了许多二进制相关的题目,如:
判断给定的整数是不是2的整数次幂 判断给定的整数是不是4的整数次幂 求给定整数的二进制表示中1的个数 求给定整数的二进制表示中0的个数 求给定整数的二进制表示中最高位1的位置 求大于等于给定整数的最小的2的整数次幂 求给定整数的二进制表示的有效位数 ... 9月21日补充:这里只考虑值为正整数的情况。 这些题目都是经典老题,频繁出现于各类笔试面试题中,除了能考察位运算外,还能考察应聘者能否给出创新的算法来更好地解决问题。可以说这些题目都不难,如果使用32位的int来表示整数的话,蛮力法都可以比较好地完成任务,但是如果想尽可能地提高效率,那就需要动一番脑经了。下面给出我对这些问题的整理和C++实现,并在下次的文章中给出只用+,-和位运算实现的正整数除法和取模。 从某种意义上讲,特别是从充分利用底层硬件的计算能力(利用特殊的cpu指令)来看,这些解法肯定不是最优的,所以还希望大侠们多多指点。 判断给定的整数是不是2的整数次幂 这应该是最简单的,利用最高位是1,其后所有位为0的特性,常数时间解决问题:
求给定整数的二进制表示中1的个数
考虑到n-1会把n的二进制表示中最低位的1置0并把其后的所有0置1,同时不改变此位置前的所有位,那么n&(n-1)即可消除这个最低位的1。
这样便有了比顺序枚举所有位更快的算法:循环消除最低位的1,循环次数即所求1的个数。此算法的时间复杂度为O(n的二进制表示中的1的个数),最坏情况下的复杂度O(n的二进制表示的总位数)。
既然有了求给定整数的二进制表示中1的个数的办法,那么想要求给定整数的二进制表示中0的个数就很简单了。事实上,在二进制中,完全可以把0和1看作是对称的两个对象,取反操作(~)可以任意的切换这两个对象,只要先对n进行一次取反,然后再用上述算法即能得到二进制表示中0的个数。首先看下面的代码:
不知大家有没有看出问题来?是的,~操作符会把所有高位的都取反,而不是只把有效位取反,所以我们需要一个能保持高位不变的位取反操作,下面是我的实现,时间复杂度和求二进制表示中1的个数的算法相同,都与二进制表示中1的个数有关:
有了这个特殊的取反操作,求给定整数的二进制表示中0的个数的办法就简单了:
看到这里,聪明的读者肯定看出问题来了,其实我干了一件很蠢的事情。看看上述算法的时间复杂度,negate_bits花了O(n的二进制表示中1的个数),while循环计算取反后的n的二进制表示中1的个数,事实上就是O(n的二进制表示中0的个数),两部分加起来其实就是二进制表示总的有效位数,换句话说,这个算法是线性的,而事实上,我们完全可以先线性地求出这个总的有效位数,然后减去1的位数,即得到0的位数,根本不用费那么大劲去整个保持高位的取反操作,两者的时间复杂度在渐进意义上也是相同的。所以,我犯傻了,但是这里又引出另一个问题:
事实上这就涉及到上面求二进制表示位数的问题,所以目前为止在此基础上的算法都是线性时间的。
那有没有不用计算位数m,从而效率更好的算法呢,能不能像在计算二进制表示中1的个数时那样根据1的个数来设计算法呢?回到那一题中,“n-1会把n的二进制表示中最低位的1置0并把其后的所有0置1”,那么n|=n-1就把n的二进制表示中最低位1后的所有0置1,再加上1,那么就把最低位1左移了一位。
于是,便有了更好的算法:循环左移最低位的1,直到n是2的整数次幂。该算法跟二进制表示中的1的个数和位置有关,最坏时间复杂度还是O(二进制表示位数),但是比起上一个实现,这个算法在多数情况下都比上一个算法快。实现如下:
算法很直观,但是比起is_2exp的常数时间is_4exp的线性时间总让我觉得不能接受,期待有人更好的改进。
原文出处:http://www.cppblog.com/xiaoyisnail/archive/2010/11/24/96707.html#134462
转载地址:http://smzqi.baihongyu.com/