神秘常量复出!用0x077CB531计算末尾0的个数
旧闻一则:神秘的0x5f3759df 不可思议的Quake III源码
[URL=http://graphics.stanford.edu/~seander/bithacks.html]发源地[/URL]
以下是片段:
下面这个位运算小技巧可以迅速给出一个数的二进制表达中末尾有多少个 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 又是什么玩意儿呢?
oooO ↘┏━┓ ↙ Oooo
( 踩)→┃你┃ ←(死 )
\ ( →┃√┃ ← ) /
\_)↗┗━┛ ↖(_/