`
chunni
  • 浏览: 11933 次
  • 性别: Icon_minigender_1
  • 来自: 北京
最近访客 更多访客>>
社区版块
存档分类
最新评论

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

阅读更多

[转] http://www.matrix67.com/blog/archives/3985

 

 大家或许还记得 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 ,欢迎大家前去围观。

分享到:
评论

相关推荐

    WinRing0x32&64

    《深入理解WinRing0x32&64:驱动级编程与系统调用》 WinRing0x32&64是一款专为Windows系统设计的底层驱动工具,它提供了32位和64位版本的动态链接库(DLL),允许程序员进行更深度的系统级编程,特别是涉及到硬件...

    C51常量 单片机C语言知识点

    在C51中,字符串常量实际是以字符数组的形式存储,且在字符串末尾加上“\0”作为结束符。 位标量是一个二进制的常量,适用于表示只读的数据位,例如在数据表或字库中的固定位值。定义常量的方式有几种,包括使用...

    最新单片机仿真 用P0口显示字符串常量

    最新单片机仿真 用P0口显示字符串常量最新单片机仿真 用P0口显示字符串常量最新单片机仿真 用P0口显示字符串常量最新单片机仿真 用P0口显示字符串常量最新单片机仿真 用P0口显示字符串常量最新单片机仿真 用P0口显示...

    VL53L0X 驱动源码

    `vl53l0x_api_calibration.c`是关于校准的部分,VL53L0X在使用前通常需要进行校准以确保测量精度。该文件包含了校准算法和相关的数据处理逻辑。`vl53l0x_new.c`可能包含了一些新功能或者更新的实现,是驱动的扩展或...

    ARM微处理器中的常量

    非法常量的例子包括0x101、0x102、0xFF1、0xFF04、0xFF003、0xFFFFFFFF、0xF000001F等,这些数值没有通过允许的循环右移方式得到,因此在ARM指令集中不能直接表示为立即数。 总结一下,ARM微处理器中的常量是通过将...

    计算n!,能够算小于9999!,修改define可以无限计算

    在C语言或者C++这类支持预处理器宏定义的语言中,"修改define可以无限计算"可能指的是定义一个常量来限制可计算的最大阶乘值,如`#define MAX_FACTORIAL 9999`。通过改变这个常量的值,可以计算更大或更小的阶乘。但...

    VC10中的C++0x特性

    在Microsoft Visual Studio 2010 (VC10)中,C++编译器开始支持C++11标准的一部分,通常称为C++0x。这个版本的编译器引入了许多新特性,极大地增强了C++语言的功能性和现代性。以下是关于VC10中C++0x特性的详细解释:...

    2019上半年C语言模拟题库.rar.rar.rar

    1. **基本语法**:C语言的基础包括变量声明、常量定义、数据类型(如int、float、char等)、运算符(算术、比较、逻辑、位操作等)以及控制流程语句(如if-else、switch-case、for、while、do-while等)。...

    C枚举常量转换易语言源码

    在编程领域,枚举(Enumeration)是一种特殊的数据类型,它定义了一组命名的常量,这些常量在程序中代表特定的值。枚举在不同的编程语言中有着不同的实现方式和使用规则。在这个主题中,我们将关注的是C语言中的枚举...

    matlab开发-等量常量计算

    在MATLAB环境中进行等量常量计算,常常涉及到数值分析和科学计算,这在工程、物理、化学等领域中尤其常见。这里的"SRK方程"指的是Soave-Redlich-Kwong状态方程,它是一种广泛应用于流体性质预测的方程。SRK方程是在...

    API常量查询简单使用

    API常量查询 方便里查询!!!!!!!!!

    翻译的VL53L0x API英文文档目录

    - **vl53l0x宏定义(VL53L0XDefines)**:列出了用于简化代码编写的宏定义,包括常量、枚举等。 - **API中的错误和警告(API中的错误和警告)**:这部分定义了API函数可能返回的各种错误和警告码,有助于开发者更好地...

    常量查找工具

    "E_DAO_SQLDeleteSyntax=2148142138 <0x800A0C3A>" 这个例子就展示了这种转换的用例,"E_DAO_SQLDeleteSyntax"可能是一个常量名,其10进制数值是2148142138,同时也可以以16进制形式表示为0x800A0C3A,这对于理解和...

    计算机二级c常量与变量习题.pdf

    在C语言中,常量和变量是编程的基本概念,它们对于理解和编写程序至关重要。下面将详细解释这些知识点。 首先,让我们来看看常量。常量是程序中不可改变的值,它们一旦被定义就不能在程序执行过程中修改。在C语言中...

    Windows API常量查询器

    Windows API常量查询器是一款专为Windows平台开发者设计的实用工具,它可以帮助程序员轻松查找和理解Windows API函数中使用的各种常量值。Windows API(Application Programming Interface)是微软提供的一系列函数...

    模拟IIC驱动GY-530 VL53L0X激光传感器,C语言

    在本文中,我们将深入探讨如何使用C语言模拟IIC(Inter-Integrated Circuit)协议来驱动GY-530模块上的VL53L0X激光传感器。GY-530模块通常用于距离测量,而VL53L0X是STMicroelectronics生产的一款高级飞行时间(Time...

    计算机各种进制的转换.pdf

    在处理字符时,特别是在字符串常量中,我们可以使用转义序列来表示特殊字符。其中,转义序列可以包含一个八进制数,表示ASCII码对应的字符。例如,如果要表示ASCII码为63的字符(问号?),可以写成'\143'。需要注意...

    API常量查询

    例如,ERROR_SUCCESS(0x00000000)是Windows API中的一个错误代码常量,表示操作成功;TRUE(非零)和FALSE(零)则代表布尔值的真和假。查询API常量的能力可以帮助开发者准确无误地调用函数,避免因参数错误导致的...

    常量矩阵变换,用于方便计算各矩阵的初等变换

    在数学的线性代数领域,常量矩阵变换是一种重要的工具,主要用于简化矩阵运算,特别是进行初等变换。初等变换是线性代数中解决线性方程组、求解矩阵特征值以及理解矩阵性质的基本方法。这些变换通常包括行交换、行倍...

    易语言常量支持库1.6

    易语言常量支持库1.6是为易语言编程环境提供的一种重要的辅助工具,它包含了一系列预定义的常量,方便程序员在编写代码时直接引用,而无需手动定义。常量在程序设计中扮演着不可忽视的角色,它们代表固定不变的值,...

Global site tag (gtag.js) - Google Analytics