设为首页 加入收藏

TOP

C语言编程笔记丨位反转的最佳算法
2019-04-03 22:08:06 】 浏览:56
Tags:语言编程 笔记 反转 最佳 算法

问:

实现如下转换的最佳算法是什么?

0010 0000 => 0000 0100

具体的转换是从MSB->LSB 到 LSB->MSB,所有的位都必须反转,那意味着,这并不是字节顺序的交换。

LSB(Least Significant Bit),意为最低有效位;MSB(Most Significant Bit),意为最高有效位。

 

最佳答案(来自Matt J

注意:下面的算法都用C实现,但应该可以迁移到其它语言(只是不那么快的时候可别找我)。

可选方案

内存占用少(32位int,32位机器)(来源于这里)


 

最快(查找表)


 

来自于著名的Bit Twiddling Hacks page:

你可以扩展这个算法到64位int的场景,或者为了更快的速度而牺牲多一些的内存(假设你的L1数据缓存足够大),有一个64K的查找表且每次反转16位。

其它方案

简单

 


 

更快(32位处理器)


ss="image-package">
 

更快(64位处理器)


 

如果你想在32位int环境这样做,那么只需要把每一个byte反转,然后再颠倒byte的次序即可。如下:


 

结果

我测试了两个最有效的方案,查找表和按位与(第一个方案)。测试机器为一台笔记本电脑,配置为4G DDR2内存,2.4GHz的

双核T7500处理器,4MB的L2缓存。我使用的是gcc 4.3.2,64位Linux。OpenMP(外加GCC绑定)被用来提高计时器的调度能力。

reverse.c


 

reverse_lookup.c


 在不同的优化级别(Optimizations),两个方案我都尝试了,每个级别跑3个案例,每个案例反转

1亿个随机的无符号整数。对于查找表方案,bitwise hacks page上面的两种方法(Option 1 and Option 2)我都测试过。

结果如下:

按位与


 

查找表(Option 1)


 

查找表(Option 2)


 结论

如果你比较在意性能,那么使用查找表Option 1(Byte的寻址不出意外的慢)。如果你需要尽可能的利用完每一个Byte内存

(且你也在意bit反转的性能),那么优化后的按位与方案也还不赖。

附加说明

我知道上面的代码只是一个粗略的版本,非常欢迎大家提供一些优化的建议。以下是我知道的几点:

(1)我没有权限访问ICC,那可能更快些(如果你可以测试请在评论中回复)。

(2)在一些L1缓存比较大的现代机器上面,64K的查找表可能工作得更好。

(3)-mtune=native对 -O2/-O3(发生符号重定义的错误)无效,所以我不相信产生的代码是为我的微架构而优化。

(4)SSE环境下应该有一种方法处理得更快。我不知道怎么做,但又更快的内存复制,批量的按位与,调整的指令集,

(5)总是有一些手段的。

(6)我知道仅仅x86的指令集是危险的,下面是GCC在-O3环境产生的代码,所以比我更厉害的大牛可以检查一下。

32-bit


 更改: 我也尝试在自己机器上使用uint64,看看是否性能有所提高。相对于32-bit性能大概提高了10%。

无论你是每次用64-bit类型去反转2个32-bit的int,或者实际上看作64-bit并分两次来反转,性能都大致相当。

代码如下(对于前者,每次反转2个32-bit的int):


 本文转载自:http://blog.jobbole.com/70993/,转载请注明出处。

笔者是一个有着7年工作经验的架构师,对于c++,自己有做资料的整合,一个完整学习C语言c++的路线,学习资料和工具。可以进我的Q群7418,18652领取,免费送给大家。希望你也能凭自己的努力,成为下一个优秀的程序员!另外博主的微信公众号是:C语言编程学习基地,欢迎关注!


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇C语言进阶指南(1)丨整型溢出和.. 下一篇数组标记法在算法题中的应用

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }