【编程技巧】条条大路通罗马

问题:对于一个字节(8bit)的变量,求其二进制表示中“1”的个数,要求算法的执行效率尽可能地高。

分析与解法

大多数的读者都会有这样的反应:这个题目也太简单了吧,解法似乎也相当地单一,不会有太多的曲折分析或者峰回路转之处。那么面试者到底能用这个题目考察我们什么呢?事实上,在编写程序的过程中,根据实际应用的不同,对存储空间或效率的要求也不一样。比如在PC 上的程序编写与在嵌入式设备上的程序编写就有很大的差别。我们可以仔细思索一下如何才能使效率尽可能地“高”。

【解法一】

可以举一个八位的二进制例子来进行分析。对于二进制操作,我们知道,除以一个 2,原来的数字将会减少一个0。如果除的过程中有余,那么就表示当前位置有一个1。以 10 100 010 为例;第一次除以 2 时,商为1 010 001,余为0。第二次除以 2 时,商为101 000,余为1。因此,可以考虑利用整型数据除法的特点,通过相除和判断余数的值来进行分析。于是有了如下的代码。

代码清单 2-1

【解法二】使用位操作

前面的代码看起来比较复杂。我们知道,向右移位操作同样也可以达到相除的目的。唯一不同之处在于,移位之后如何来判断是否有1 存在。对于这个问题,再来看看一个八位的数字:10 100 001。在向右移位的过程中,我们会把最后一位直接丢弃。因此,需要判断最后一位是否为1,而“与”操作可以达到目的。可以把这个八位的数字与00000001 进行“与”操作。如果结果为1,则表示当前八位数的最后一位为1,否则为0。代码如下:

代码清单 2-2

【解法三】

位操作比除、余操作的效率高了很多。但是,即使采用位操作,时间复杂度仍为O(log2v),log2v 为二进制数的位数。那么,还能不能再降低一些复杂度呢?如果有办法让算法的复杂度只与“1”的个数有关,复杂度不就能进一步降低了吗?同样用 10 100 001 来举例。如果只考虑和1 的个数相关,那么,我们是否能够在每次判断中,仅与1 来进行判断呢?为了简化这个问题,我们考虑只有一个 1 的情况。例如:01 000 000。如何判断给定的二进制数里面有且仅有一个 1 呢?可以通过判断这个数是否是2 的整数次幂来实现。另外,如果只和这一个“1”进行判断,如何设计操作呢?我们知道的是,如果进行这个操作,结果为0 或为1,就可以得到结论。如果希望操作后的结果为 0,01 000 000 可以和00 111 111 进行“与”操作。这样,要进行的操作就是 01 000 000 &(01 000 000 – 00 000 001)= 01 000 000 &00 111 111 = 0。因此就有了解法三的代码:

代码清单 2-3

最后,得到解法四:算法中不需要进行任何的比较便可直接返回答案,这个解法在时间复杂度上应该能够让人高山仰止了。

【解法四】查表法

代码清单 2-5

这是个典型的空间换时间的算法,把0~255 中“1”的个数直接存储在数组中,v 作为数组的下标,countTable[v]就是v 中“1”的个数。算法的时间复杂度仅为O(1)。在一个需要频繁使用这个算法的应用中,通过“空间换时间”来获取高的时间效率是一个常用的方法,具体的算法还应针对不同应用进行优化。

虽然是一个简单的问题,但是从上面看到还有这么多解决办法。你还能想到其他方法吗?

原文发布于微信公众号 - 程序员互动联盟(coder_online)

原文发表时间:2015-04-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏码洞

见缝插针 —— 深入 Redis HyperLogLog 内部数据结构分析

HyperLogLog算法是一种非常巧妙的近似统计海量去重元素数量的算法。它内部维护了 16384 个桶(bucket)来记录各自桶的元素数量。当一个元素到来时...

1062
来自专栏xingoo, 一个梦想做发明家的程序员

批处理作业调度-回溯法

问题描述:   给定n个作业,集合J=(J1,J2,J3)。每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先有机器1处理,然后再由机器2处理。作业...

1818
来自专栏陈树义

BloomFilter算法

Bloom filter 是由 Howard Bloom 在 1970 年提出的二进制向量数据结构,它具有很好的空间和时间效率,被用来检测一个元素是不是集合中的...

3598
来自专栏企鹅号快讯

1.12编程基础之函数与过程抽象/05:统计单词数

总时间限制: 1000ms 内存限制: 65536kB 描述 一般的文本编辑器都有查找单词的功能,该功能可以快速定位特定单词在文章中的位置,有的还能统计出特定单...

19010
来自专栏Petrichor的专栏

python: random模块

  在numpy 和 tensorflow 中有 相同功能 的实现, 见 《tensorflow: Constants, Sequences, and Ra...

491
来自专栏算法channel

直接插入排序到希尔排序做的那些改进

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

3259
来自专栏人工智能

如何为机器学习索引,切片,调整 NumPy 数组

具体在 Python 中,数据几乎被都被表示为 NumPy 数组。

4987
来自专栏生信技能树

R语言中的排序,集合运算,reshape,以及merge总结

不想排版,心情也不好,但是这个知识点很重要,尤其是学习R语言的朋友,请仔细看~ 一直以来我都是随便看了点R的编程教程,因为我学了一点点C,所以还算有基础,现在基...

26911
来自专栏Petrichor的专栏

tensorflow编程: Constants, Sequences, and Random Values

  注意: start 和 stop 参数都必须是 浮点型;     取值范围也包括了 stop; tf.lin_space 等同于 tf.lins...

382
来自专栏技术之路

算法时间复杂度

     算法复杂度分为时间复杂度和空间复杂度,一个好的算法应该具体执行时间短,所需空间少的特点。      随着计算机硬件和软件的提升,一个算法的执行时间是算...

1766

扫码关注云+社区