神秘常量复出!用0x077CB531计算末尾0的个数

标签: 算法 Brain Storm 图论 代码 C语言 | 发表时间:2010-12-13 22:02 | 作者:Matrix67 KK
出处:http://www.matrix67.com/blog

    大家或许还记得 Quake III 里面的一段有如天书般的代码,其中用到的神秘常量 0x5F3759DF 究竟是怎么一回事,着实让不少人伤透了脑筋。今天,我见到了一段同样诡异的代码。
    下面这个位运算小技巧可以迅速给出一个数的二进制表达中末尾有多少个 0 。比如, 123 456 的二进制表达是 1 11100010 01000000 ,因此这个程序给出的结果就是 6 。

unsigned int v;  // find the number of trailing zeros in 32-bit v
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

    熟悉位运算的朋友们可以认出, v & -v 的作用就是取出右起连续的 0 以及首次出现的 1 。当 v = 123 456 时, v & -v 就等于 64 ,即二进制的 1000000 。怪就怪在,这个 0x077CB531 是怎么回事?数组 MultiplyDeBruijnBitPosition 又是什么玩意儿呢?


    这还得从 0x077CB531 本身的一个性质开始说起。把这个常数写成 32 位二进制,可以得到

00000111011111001011010100110001

    这个 01 串有一个无比牛 B 的地方:如果把它看作是循环的,它正好包含了全部 32 种可能的 5 位 01 串,既无重复,又无遗漏!其实,这样的 01 串并不稀奇,因为构造这样的 01 串完全等价于寻找一个有向图中的 Euler 回路。如下图,构造一个包含 16 个顶点的图,顶点分别命名为 0000, 0001, 0010, …, 1111 。如果某个点的后 3 位,正好等于另一个点的前 3 位,就画一条从前者出发指向后者的箭头。也就是说,只要两个顶点上的数满足 abcd 和 bcde 的关系( a 、 b 、 c 、 d 、 e 可能代表相同的数字),就从 abcd 出发,连一条到 bcde 的路,这条路就记作 abcde 。注意,有些点之间是可以相互到达的(比如 1010 和 0101 ),有些点甚至有一条到达自己的路(比如 0000 )。

  

    构造一个字符串使其包含所有可能的 5 位 01 子串,其实就相当于沿着箭头在上图中游走的过程。不妨假设字符串以 0000 开头。如果下一个数字是 1 ,那么 00001 这个子串就被包含了,同时最新的 4 位数就变成了 0001 ;但若下一个数字还是 0 ,那么 00000 就被包含了进来,最新的 4 个数仍然是 0000 。从图上看,这无非是一个从 0000 点出发走了哪条路的问题:你是选择了沿 00001 这条路走到了 0001 这个点,还是沿着 00000 这条路走回了 0000 这个点。同理,每添加一个数字,就相当于沿着某条路走到了一个新的点,路上所写的 5 位数就是刚被考虑到的 5 位数。我们的目的便是既无重复又无遗漏地遍历所有的路。显然图中的每个顶点入度和出度都是 2 ,因此这个图一定存在 Euler 回路,我们便能轻易构造出一个满足要求的 01 串了。这样的 01 串就叫做 De Bruijn 序列。

    De Bruijn 序列在这里究竟有什么用呢?它的用途其实很简单,就是为 32 种不同的情况提供了一个唯一索引。比方说, 1000000 后面有 6 个 0 ,将 1000000 乘以 0x077CB531 ,就得到

   00000111011111001011010100110001
-> 11011111001011010100110001000000

    相当于把 De Bruijn 序列左移了 6 位。再把这个数右移 27 位,就相当于提取出了这个数的头 5 位:

   11011111001011010100110001000000
->                            11011

    由于 De Bruijn 序列的性质,因此当输入数字的末尾 0 个数不同时,最后得到的这个 5 位数也不同。而数组 MultiplyDeBruijnBitPosition 则相当于一个字典的功能。 11011 转回十进制是 27 ,于是我们查一查 MultiplyDeBruijnBitPosition[27] ,程序即返回 6 。
    注意到当输入数字的末尾 0 个数超过 27 个时,程序也是正确的,因为左移时低位正好是用 0 填充的。

    这段神一般的代码取自 http://graphics.stanford.edu/~seander/bithacks.html ,欢迎大家前去围观。

相关 [常量 0x077cb531 计算] 推荐:

神秘常量复出!用0x077CB531计算末尾0的个数

- KK - Matrix67: My Blog
    大家或许还记得 Quake III 里面的一段有如天书般的代码,其中用到的神秘常量 0x5F3759DF 究竟是怎么一回事,着实让不少人伤透了脑筋. 今天,我见到了一段同样诡异的代码.     下面这个位运算小技巧可以迅速给出一个数的二进制表达中末尾有多少个 0. 比如, 123 456 的二进制表达是 1 11100010 01000000 ,因此这个程序给出的结果就是 6.

oracle license计算

- Fenng - eagle's home
Oracle license的计算是基于CPU core的. 用core的数目乘以一个系数core factor就可以得到所需的oracle license的数目. 对于不同的CPU,core factor是不一样的,可以从oracle提供的这张列表中查到 Oracle Processor Core Factor Table.

String 常量池和 String#intern()

- - ImportNew
String是Java基础的重要考点. 可问的点多,而且很多点可以横向切到其他考点,或纵向深入JVM. 本文略过了String的基本内容,重点在于String#intern(). String常量可能会在两种时机进入常量池:. 编译期:通过双引号声明的常量(包括 显示声明、 静态编译优化后的常量,如”1”+”2”优化为常量”12”),在前端编译期将被静态的写入class文件中的“常量池”.

理解云计算

- 车东 - oneoo's 私家花园
  现在互联网最热门的关键字“云计算”,大大小小的公司纷纷加入到这块领域. 简单来说,目前的“云计算”主要分为:SaaS、PaaS和IaaS三大类.   其中SaaS云计算,为软件即服务的概念. 把传统客户端软件部署在互联网上,用户只需要一个浏览器就可以使用到软件的模式. 其实早在2000年就已经有B/S结构的软件服务,与现在所说的SaaS云计算相近,但此前的B/S结构软件服务,数据库等服务端是需要用户自行部署的,而非由软件提供商进行统一部署.

钢琴计算器

- 丑秋 - 专利之家-设计发明与创意商机
这款太阳能计算器别出心裁地设计了黑白相间的按键,看起来像钢琴的琴键一样,十分有趣. 或许这样的计算器可以给枯燥的计算工作增添一点乐趣,让它不再乏味.

10问云计算

- - 《商业价值》杂志
与数百位关注和实践云计算的CIO们共同解读云计算热点问题. 被视作IT界第三次革命的云计算,已经从炙手可热的概念逐渐走向了实际应用. 2011年8-11月, ITValue社区联合英特尔公司,与数百位关注和实践云计算的CIO们一起展开深入探讨,话题涉及云计算的商业价值、安全性、开放性、高效性、简单性等方面.

Java堆、栈和常量池原理

- - 研发管理 - ITeye博客
一:在JAVA中,有六个不同的地方可以存储数据:  . 这是最快的存储区,因为它位于不同于其他存储区的地方——处理器内部. 但是寄存器的数量极其有限,所以寄存器由编译器根据需求进行分配. 你不能直接控制,也不能在程序中感觉到寄存器存在的任何迹象. ------最快的存储区, 由编译器根据需求进行分配,我们在程序中无法控制..

Java常量池理解与总结

- - 移动开发 - ITeye博客
用final修饰的成员变量表示常量,值一旦给定就无法改变. final修饰的变量有三种:静态变量、实例变量和局部变量,分别表示三种类型的常量. Class文件中的常量池. 在Class文件结构中,最头的4个字节用于存储魔数 Magic Number,用于确定一个文件是否能被JVM接受,再接着4个字节用于存储版本号,前2个字节存储次版本号,后2个存储主版本号,再接着是用于存放常量的常量池,由于常量的数量是不固定的,所以常量池的入口放置一个U2类型的数据(constant_pool_count)存储常量池容量计数值.

Java堆栈常量池深入

- - Java - 编程语言 - ITeye博客
转自: http://uule.iteye.com/blog/1417299. 1.寄存器:最快的存储区, 由编译器根据需求进行分配,我们在程序中无法控制. 栈:存放基本类型的变量数据和对象的引用,但对象本身不存放在栈中,而是存放在堆(new 出来的对象)或者常量池中(字符串常量对象存放在常量池中.

云计算的困局

- Star Ocean - It Talks--上海魏武挥的博客
有个媒体朋友打电话咨询我一个事. 说在江浙一带,有一位搞国际货运代理的民营企业家,想利用云计算来整合各种资源,比如运输车队、仓库、集装箱乃至货船. 这些资源的调配信息对任何一家从事外贸的企业都很重要,如果将这些信息放在所谓的“云”上,并加以运算,这些企业再以各种设备联入这个“云”,这位企业家觉得是一个很有前途的买卖.