专栏首页ICSOC.TECH硬件设计之 Distributed Arithmetic 一例

硬件设计之 Distributed Arithmetic 一例

下面是一段常见的c代码,用于计算下面这个问题。

问题:求一个32位整数的二进制表示中 1 的数量。

unsigned long CountOnes(unsigned long X) {
    X = (X & 0x55555555) + (X >> 1 & 0x55555555);
    X = (X & 0x33333333) + (X >> 2 & 0x33333333);
    X = (X & 0x0F0F0F0F) + (X >> 4 & 0x0F0F0F0F);
    X = (X & 0x00FF00FF) + (X >> 8 & 0x00FF00FF);
    X = (X & 0x0000FFFF) + (X >> 16 & 0x0000FFFF);
    return(X);
}

它背后的原理是什么呢?这篇文章尝试从硬件设计领域中 Distributed Arithmetic(DA算法)的角度来解释。

首先把这个问题转换成不那么专业的数学语言。

已知一个 32 位正整数

X=\sum_{b=0}^{N-1}x_b\cdot2^b

,其中

x_b

表示 X 的第 b 位,取值 0 或者 1。该位的权值即 2 的 b 次幂,

2^b

。N 在此例中等于 32。

求 X 的二进制表示中的 1 的数量,即

\sum_{b=0}^{N-1}x_b

上面 c 代码函数中的第一步

    X = (X & 0x55555555) + (X >> 1 & 0x55555555);

的结果可以用下式表示,

X=\sum_{b=0}^{n/2-1}(x_{2b}+x_{2b+1})\cdot2^{2b}

其中,b 的取值是 0 到 15。它的含义就是每相邻两个 bit 中含有的 1 的个数,这 16 个个数是单独体现在每两个 bit 组成的整数中,把这 16 个两 bit 数组合在一起,1 的个数的含义就模糊不清了,因为每个两 bit 数都用 2 的 2b 次幂加权了。分开看才会清楚,这也是这段 c 代码容易使人困惑的主要原因。

直接考虑用硬件实现的时候,不必用 1 个 32 bit 宽的加法器,而是用 16 个 1 bit 加法器并行计算。这就是 DA 算法的分布式计算特点。

上面 c 代码函数中的第二步

    X = (X & 0x33333333) + (X >> 2 & 0x33333333);

的结果可以用下式表示,

X=\sum_{b=0}^{n/4-1}(x_{4b}+x_{4b+1}+x_{4b+2}+x_{4b+3})\cdot2^{4b}

其中,b 的取值是 0 到 7。它的含义就是每四个 bit 中含有的 1 的个数,这 8 个个数是单独体现在每四个 bit 组成的整数中,同样这 8 个四 bit 数组合在一起,含义也是隐藏起来的,因为每个四 bit 数都用 2 的 4b 次幂加权了。同样也是分开看才清楚。

类似的第三步可以用下式表示,

X=\sum_{b=0}^{n/8-1}(x_{8b}+x_{8b+1}+x_{8b+2}+{...}+x_{8b+7})\cdot2^{8b}

其中,b 的取值是 0 到 3。

第四步可以用下式表示,

X=\sum_{b=0}^{n/16-1}(x_{16b}+x_{16b+1}+x_{16b+2}+ {...} +x_{16b+15})\cdot2^{16b}

其中,b 的取值是 0 到 1。

第五步,及最后一步可以表示为,

X=\sum_{b=0}^{n/32-1}(x_{32b}+x_{32b+1}+x_{32b+2}+ {...} +x_{32b+31})\cdot2^{32b}

其中,b 的取值只有 0,即上式可以简化为

X=x_0+x_1+x_2+{...}+x_{31}=\sum_{b=0}^{N-1}x_b

从这里就可以看到,此时 X 的取值,就是原来的 32 位整数 X 的二进制表示中的 1 的个数了。

看到这里,读者朋友们对这几句“奇技淫巧”般的代码背后的数学原理应该有所了解了吧。不过这种代码也并不只是在面试中为难面试者的,它还真是用来解决实际问题的。

比如,编码理论中经常提到的计算一个编码符号的 hamming weight,就是这个编码符号相对于全零编码符号的 hamming distance,二进制情况下也就是这个编码符号中 1 的个数。

本文分享自微信公众号 - icsoc(ic-soc),作者:韩京飞

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-25

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 当我们做后仿时我们究竟在仿些什么(补充)

    自从上次关于后仿的文章发布以后,又陆续收集到了一些关于后仿的其它小技巧。这次整理出来作为前文的补充,希望对大家有所帮助。文中提到的仿真器默认是VCS.

    icsoc
  • Pin/PAD Design In SoC

    已经有很长一段时间不做 SoC Integration 方面的工作了,这篇是芯片 IO 相关的一些设计经验总结,主要是方便自己将来重新拾起,同时也希望能和大家分...

    icsoc
  • 当我们做后仿时我们究竟在仿些什么(四)

    就像人类容易接受自然数,但对于负数缺乏某种直觉上的认识一样;后仿过程中经常出现的 Negative Delay 和 Negative Timing Check ...

    icsoc
  • X86 DBCA, NETCA GIVE JAVA HOTSPOT ERROR IF ON X86_64 HARDWARE

        在使用DBCA命令创建新的数据库时,DBCA命令无法启动。运行的环境是宿主机64bit+AMD cpu, 而客户机为Linux 32bit + Grid...

    Leshami
  • 557.Reverse Words in a String III(String-Easy)

    Given a string, you need to reverse the order of characters in each word within ...

    Jack_Cui
  • CloudFoundry应用的自定义端口的命令行设置方式

    app guid: 6d75ef4d-40ca-435d-a7a0-fd2acc1fed12

    Jerry Wang
  • TCP和Http的区别! 我都搞懂了,你就别迷糊了!

    Java学习123
  • Matlab - sort函数

    在Matlab中排序某个向量(一维)时,可以使用sort(A),其中A为待排序的向量,如果仅是用来排序A,那么直接使用sort(A)即可,如果排序后还需要保留原...

    AIHGF
  • 一种有效的平面光束法平差方法

    本方法(PBA, Planar Bundle Adjustment)使用点到面的 cost 同时优化深度相机位姿和三维重

    用户1150922
  • OpenTK 入门系列

    本来是很久以前的帖子了, 居然还有人需要, 所以又翻了出来, 重新整理并发布到 github 。

    beginor

扫码关注云+社区

领取腾讯云代金券