C语言编程笔记丨位反转的最佳算法

问：

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

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位处理器)

 

更快(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语言编程学习基地，欢迎关注！