注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

简单代码

寻找代码的灵魂

 
 
 

日志

 
 
关于我

对于本博客内所有原创文章和代码的引用必须标明“来源:http://simplesource.blog.163.com/”。如需应用于商业目的必须经本人同意,本人对所有原创文章和代码保留一切权利。 PS:需要部分程序源代码的请留下邮箱地址

网易考拉推荐

引用 反转一个字节 和 判断32位整数二进制中1的个数 的算法  

2010-03-11 10:55:50|  分类: 技术文献 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 

引用

啤酒孩反转一个字节 和 判断32位整数二进制中1的个数 的算法

转载于:zxg623.cublog.cn

unsigned char reverse8( unsigned char c )
{
    c = ( c & 0x55 ) << 1 | ( c & 0xAA ) >> 1;
    c = ( c & 0x33 ) << 2 | ( c & 0xCC ) >> 2;
    c = ( c & 0x0F ) << 4 | ( c & 0xF0 ) >> 4;
    return c;
}

unsigned long func(unsigned long x)
{
    x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL);
    x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL);
    x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL);
    x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL);
    x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL);
    return x;
}

先看问题1: 反转一个字节。
它的算法是这样的: 首先是2位2位为一组,交换前一半和后一半。再4位4位为一组,交换前一半和后一半。再8位为一组,交换前一半和后一半


可能还有点说不清楚。我举个例子。
将1 2 3 4 5 6 7 8 反转。
(1)2个2个为一组,交换前一半和后一半, 变成。
  2 1 4 3 6 5 8 7
(2)4个4个为一组,交换前一半和后一半, 变成
  4 3 2 1 8 7 6 5
(3)再8个为一组,交换前一半和后一半, 变成
  8 7 6 5 4 3 2 1
反转成功。
这样的算法本来很是简单,很容易用数学归纳法证明其正确。这函数, 巧妙就巧妙在作了并行计算,分组,它一次就计算完了。

先看第一个语句。c = ( c & 0x55) << 1 | ( c & 0xAA ) >> 1; 
0x55其实就是01010101, 0xAA就是10101010
假设 c=abcdefgh
c & 0x55 = 0b0d0f0h,    c & 0xAA = a0c0e0g0
跟着,前者左移一位, b0d0f0h0, 后者右移一位, 0a0c0e0g, 再一个|运算,就两位两位交换了位置。
想象一下,你有一个长纸条,分成一格一格,每格写一个字,假如你将纸条每隔一格剪一个小洞,滑一格,覆盖在原来的纸条上,你就会看到两个两个字交换了位置。
(注: |运算可以换成+运算,想一想为什么)

第二个语句。 c = ( c & 0x33 ) << 2 | ( c & 0xCC ) >> 2;
0x33 = 00110011, 0xCC=11001100。 

第三个语句。c = ( c & 0x0F ) << 4 | ( c & 0xF0 ) >> 4;
0x0f = 00001111, 0xF0=11110000.

这两个语句的作用也是 分组,将一半位变成0,移位滑动,跟着再组合,就分组交换了位置。
不防想象两个小纸条剪洞叠加。

这方法应该可以推广。
理解了问题1,也就很容易理解问题2了.

问题2: 判断32位整数二进制中1的个数。
和问题1一样,也是采用了分组并行计算。

基本方法是: 2位2位为一组,相加,看看有几个1。再4位4位为一组,相加,看看有几个1......
还是说的不太明白。接着分析。

为了简单说明,先看看8位的情形。相应地,函数里面的语句变成。
x = (x & 0x55) + ((x >> 1) & 0x55);   (1)
x = (x & 0x33) + ((x >> 2) & 0x33);   (2)
x = (x & 0x0f) + ((x >> 4) & 0x0f);   (3)
return x;

假设x=abcdefgh. 0x55=01010101
x & 0x55 = 0b0d0f0h.  (x>>1) & 0x55 = 0a0c0e0g。相加。就可以知道2位2位一组1的个数。

比如x=11111111
x= (x & 0x55) + ((x >> 1) & 0x55); 之后x=10101010。你2位2位地看,10=2, 就是2 2 2 2, 就是说各组都是2个1。
比如x=00101001
x= (x & 0x55) + ((x >> 1) & 0x55); 之后x=00010101。你2位2位地看,就是0 1 1 1, 前1组只有0个1,后面的组都是1个1。

好啦。再来看。0x33=00110011。
x=abcdefgh. 
x=(x & 0x33)+((x >> 2)&0x33); 相当于, 00ab00ef + 00cd00gh。
因为语句(1)之后。ab指示了头两位有多少个1,cd指示了下两位有多少个1。相加00ab+00cd就指示前4位有多少个1。这样就是4位4位为一组。注意这样的分组,组与组之间永远都不会产生进位的。正因为不会产生进位,才可以分开来看。

  评论这张
 
阅读(394)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017