数字之魅——小感小悟

迷南。 2022-08-02 15:51 159阅读 0赞

## 求二进制中1的个数 ##

查看网友评论有这样一句话：一个分支判断会耗上14个左右的时钟周期。  
这里我就联想到了我看CSAPP中的几个知识点。

*  现在CPU一般都是一条指令一个时钟周期
 *  普通线程之间的切换需要消耗20000个时钟周期，但是在现在cpu中基本都是超线程的，比如我笔记本是酷睿i5，2个实际内核，4个逻辑内核。也可以说是2房间4个门吧。在这种超线程的cpu中，线程切换只需要1个时钟周期。  
    上面只是联想，网友想说明的问题是分支循环效率较低，能避免就避免。

对于解法五的查表法，提供了一种很好的思想，虽然被大牛给否决了，但是在处理小规模，或者多次查表的应用中不失为一种很好的方法，比如我的博客中整型转字符串的算法就是用的这种方法([http://blog.csdn.net/z702143700/article/details/46715893][http_blog.csdn.net_z702143700_article_details_46715893])。

下面是大牛的评论，大致意思精简如下，非常好。  
对于这种小规模问题，CPU时钟周期和内存读取可能就比时间复杂度显得更加重要了。这里用到一个访存操作，且第一次访存的时候很有可能数组不在cache里，这样一个cache miss导致的后果就是耗去几十甚至上百个时钟周期，所以这里虽然时间复制度为O(1)，但是性能是很差的。

对于时钟周期的概率可以参考（[http://blog.csdn.net/z702143700/article/details/46278069][http_blog.csdn.net_z702143700_article_details_46278069]）  
最后，最好的解法并不是书中提到的，所以感叹一句没有最好，只有更好。  
更好的解法见博客（[http://blog.csdn.net/justpub/article/details/2292823][http_blog.csdn.net_justpub_article_details_2292823]）

## 不要被阶乘吓到 ##

给我的启发是乘除的效率是较低的，移位运算需要我们经常拿来考虑。

*  奇偶判断可以用来移位  
    如： if(x>>1)或者if(x&1)
 *  整除2可以用移位  
    如：x>>1 ==>> x / 2 x>>2 ==>> x / 4 ……

未完待续。。。

[http_blog.csdn.net_z702143700_article_details_46715893]: http://blog.csdn.net/z702143700/article/details/46715893
[http_blog.csdn.net_z702143700_article_details_46278069]: http://blog.csdn.net/z702143700/article/details/46278069
[http_blog.csdn.net_justpub_article_details_2292823]: http://blog.csdn.net/justpub/article/details/2292823