做电商网站一般多少钱,搜索引擎优化seo论文,网站外链,wordpress获取当前文章名称要求#xff1a;对于一个字节#xff08;8bit#xff09;的变量#xff0c;求其二进制表示中“1”的个数#xff0c;要求算法的执行效率尽可能地高。 大多数的读者都会有这样的反应#xff1a;这个题目也太简单了吧#xff0c;解法似乎也相当地单一#xff0c;不会有太…要求对于一个字节8bit的变量求其二进制表示中“1”的个数要求算法的执行效率尽可能地高。 大多数的读者都会有这样的反应这个题目也太简单了吧解法似乎也相当地单一不会有太多的曲折分析或者峰回路转之处。那么面试者到底能用这个题目考察我们什么呢事实上在编写程序的过程中根据实际应用的不同对存储空间或效率的要求也不一样。比如在PC上的程序编写与在嵌入式设备上的程序编写就有很大的差别。我们可以仔细思索一下如何才能使效率尽可能地“高”。 【解法一】 可以举一个八位的二进制例子来进行分析。对于二进制操作我们知道除以一个2原来的数字将会减少一个0。如果除的过程中有余那么就表示当前位置有一个1。 以10 100 010为例 第一次除以2时商为1 010 001余为0。 第二次除以2时商为101 000余为1。 因此可以考虑利用整型数据除法的特点通过相除和判断余数的值来进行分析。于是有了如下的代码。 版本1 int count(int v) { int num 0; while(v) { if(v % 2 1) { num; } v v/ 2; } return num; } 【解法二】使用位操作 前面的代码看起来比较复杂。我们知道向右移位操作同样也可以达到相除的目的。唯一不同之处在于移位之后如何来判断是否有1存在。对于这个问题再来看看一个八位的数字10 100 001。 在向右移位的过程中我们会把最后一位直接丢弃。因此需要判断最后一位是否为1而“与”操作可以达到目的。可以把这个八位的数字与00000001进行“与”操作。如果结果为1则表示当前八位数的最后一位为1否则为0。代码如下 版本2 int count(int v) { int num 0; while(v) { num v 0x01; v 1; } return num; } 【解法三】 位操作比除、余操作的效率高了很多。但是即使采用位操作时间复杂度仍为Olog2vlog2v为二进制数的位数。那么还能不能再降低一些复杂度呢如果有办法让算法的复杂度只与“1”的个数有关复杂度不就能进一步降低了吗 同样用10 100 001来举例。如果只考虑和1的个数相关那么我们是否能够在每次判断中仅与1来进行判断呢 为了简化这个问题我们考虑只有一个1的情况。例如01 000 000。 如何判断给定的二进制数里面有且仅有一个1呢可以通过判断这个数是否是2的整数次幂来实现。另外如果只和这一个“1”进行判断如何设计操作呢我们知道的是如果进行这个操作结果为0或为1就可以得到结论。 如果希望操作后的结果为001 000 000可以和00 111 111进行“与”操作。 这样要进行的操作就是 01 000 000 01 000 000 – 00 000 001 01 000 000 00 111 111 0。 因此就有了解法三的代码 版本3 int count(int v) { int num 0; while(v) { v (v-1); num; } return num; } 【解法四】使用分支操作 解法三的复杂度降低到OM其中M是v中1的个数可能会有人已经很满足了只用计算1的位数这样应该够快了吧。然而我们说既然只有八位数据索性直接把0~255的情况都罗列出来并使用分支操作可以得到答案代码如下 版本4 int count(int v) { int num 0; switch (v) { case 0x0: num 0; break; case 0x1: case 0x2: case 0x4: case 0x8: case 0x10: case 0x20: case 0x40: case 0x80: num 1; break; case 0x3: case 0x6: case 0xc: case 0x18: case 0x30: case 0x60: case 0xc0: num 2; break; // } return num; } 解法四看似很直接但实际执行效率可能会低于解法二和解法三因为分支语句的执行情况要看具体字节的值如果a 0那自然在第1个case就得出了答案但是如果a 255则要在最后一个case才得出答案即在进行了255次比较操作之后 看来解法四不可取但是解法四提供了一个思路就是采用空间换时间的方法罗列并直接给出值。如果需要快速地得到结果可以利用空间或利用已知结论。这就好比已经知道计算12 … N的公式在程序实现中就可以利用公式得到结论。 最后得到解法五算法中不需要进行任何的比较便可直接返回答案这个解法在时间复杂度上应该能够让人高山仰止了。 【解法五】查表法 /* 预定义的结果表 */int countTable[256] { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 };int count(int v) { //check parameter return countTable[v]; } 这是个典型的空间换时间的算法把0~255中“1”的个数直接存储在数组中v作为数组的下标countTable[v]就是v中“1”的个数。算法的时间复杂度仅为O1。 在一个需要频繁使用这个算法的应用中通过“空间换时间”来获取高的时间效率是一个常用的方法具体的算法还应针对不同应用进行优化。 扩展问题 1. 如果变量是32位的DWORD你会使用上述的哪一个算法或者改进哪一个算法 2. 另一个相关的问题给定两个正整数二进制形式表示A和B问把A变为B需要改变多少位bit也就是说整数A 和B 的二进制表示中有多少位是不同的
