#【翻译+整理】Bit Twiddling Hacks 位操作技巧

原文：http://graphics.stanford.edu/~seander/bithacks.html#OperationCounting

By Sean Eron Andersonseander@cs.stanford.edu

本文中出现的代码片段是公开的（除非有特别标注）——你可以把它们用在任何地方。这些资料是由© 1997-2005 Sean Eron Anderson 搜集整理的。本文给出了代码相应的说明并希望它们对你有所帮助。但本文不对内容提供担保并且不对代码是否适用于一些特定用途提供担保。截止2005.5.5，所有的代码都被完全测试过。上千人阅读了本文。此外，卡耐基梅隆大学计算机系的院长Randal Bryant教授使用它的Uclid代码测试系统测试了几乎所有代码。我也测试了32位机上所有可能的输入。对于第一个发现代码中bug的人，我将支付10美元（通过支票或paypal）（注：译者表示我不背锅（逃）），或是支付20美元用于慈善。

##关于复杂度计算方法

当我们统计算法中共进行了几步操作时，所有C运算符被视为一步操作。所有不需要被写入内存中的中间步骤不计数。当然，这里的计算方法仅用于估算实际的机器指令数量和CPU时间。此外，假设所有的指令执行时间相同，虽然这不符合事实，但CPU的技术将朝这个方向发展。每个系统因为很多细微的差异，因此运行这些代码时的速度都各不相同，如高速缓存大小，内存带宽，指令集等的差异。最后，基准测试是判断一个算法比其他算法高效的最好方法，所以请在目标机器上测试，以确定是否使用下面技巧。

计算整数的符号

####类型定义：

1
2
3
4
int v;      // 我们希望确定v的符号
int sign;   // 结果存在这 

// CHAR_BIT 是一个字节的比特数（一般是8）

####算法1

1
sign = -(v < 0);  // 如果 v < 0 则sign=-1, 否则sign=0.

####算法2

如果希望避免指令执行时发生跳转（如IA32） （注：一般执行 v<0 ,会执行test eax,edx（假设eax和edx分别存放v和0），然后jge或jb）

1
sign = -(int)( (unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT -1) );

####算法3

如果需要更少的指令数（但可移植性差） 

1
sign = v >> ( sizeof(int) * CHAR_BIT -1 );

最后一个表达式对于32位的整数相当于 sign = v >> 31。这明显比第一种要快。

算法4

如果你希望返回值是+1和-1 

1
sign = +1 | (v >> (sizeof(int) * CHAR_BIT - 1));

算法5

或者你希望返回值是+1,0和-1

#####5.1

1
sign = (v != 0) | -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));
5.2

可移植性较差但更快

1
sign = (v != 0) | (v >> (sizeof(int) * CHAR_BIT - 1)); // -1, 0, or +1
5.3

可移植性好且简洁（注：但跳转多）

1
sign = (v > 0) - (v < 0); // -1, 0, or +1

算法6

希望测试一个数是不是非负数，返回+1或0

1
sign = 1 ^ ((unsigned int)v >> (sizeof(int) * CHAR_BIT - 1)); // if v < 0 then 0, else 1

解释

算法3：当有符号整数右移时，当原数为负，最高位（最左一位）填充1，否则填充0。而当数字二进制位为全1时即为-1。不幸的是这个特点与架构有关（不可移植）。

####附注：

2003.3.7，Angus Duggan指出1989年的ANSI C标准没有对有符号数右移的结果给出明确的标准（ implementation-defined），所以在一些系统上这些代码可能不能用 。为了更好的可移植性，Toby Speight在2005.9.28建议加入CHAR_BIT而不是假设每个字节都是8个比特。Angus于2006.3.4推荐了上面这种更具移植性的算法。 Rohit Garg于2009.9.12推荐了判断非负数的算法。

译者注解

算法1不解释，v<0返回的是0或1

算法2和算法3原理类似。注意，算法有个前提就是C编译器对于有符号数位移操作采取算术右移 而非 逻辑右移 对于无符号数相反（附注中说明了这个行为其实取决于编译器）。对于算法2，先将v转换为无符号，之后位移。因为为无符号，因此高位补0，移位后v中只保留了原数的最高位，因为int型为补码存储，最高位为符号位，若原数小于0，则结果为000…001，反之为000…000，因此sign返回-1或0。

算法3因为v为有符号，因此如果符号位为1，右移高位补1，结果为111…111，即补码的-1，反之为000…000

算法4为算法3的结果 或+1，对于-1，-1 | +1 = 111…111 | 000…001 = 111…111 = -1，对于0，为+1

算法5.1和5.2与4原理相同，当v!=0时进行或运算的就是+1，否则为0.

算法5.3，若v>0，则 (v>0)-(v<0) = 1-0=1 若v<0为-1，若v=0为0

算法6改或为异或，当后一个式子为0时，即v>=0时结果为1；后一个式子为1时（注意这里为逻辑右移）结果0。

判断两数符号是否相反

1
2
3
int x, y;               // 待比较的数

bool f = ((x ^ y) < 0); // 如果x和y符号相反则为真

附注：

Manfred Weis于2009.11.26建议加入

译者注解

若x和y符号相反，即符号位不同。此时进行位异或运算，符号位为1，因此运算结果为一负数。

不使用跳转计算一个整数的绝对值

####定义

1
2
3
4
int v;           // 计算v的绝对值
unsigned int r;  // 结果

int const mask = v >> sizeof(int) * CHAR_BIT - 1;//定义一个掩码，值为v算术右移至仅保留最高位

####算法1

1
r = (v + mask) ^ mask;

####算法2 （已被申请专利）

1
r = (v ^ mask) - mask;

####解释：

一些CPU没有取整数绝对值的指令（或者编译器不支持）。在那些跳转开销较大的机器上，上面的程序要比

1
r = (v < 0) ? -(unsigned)v : v;

来的快，即使两者指令数相同。

附注：

2003.3.7，Angus Duggan指出1989年的ANSI C标准没有对有符号数右移的结果给出明确的标准（ implementation-defined），所以在一些系统上这些代码可能不能用 （好像很熟悉？是的跟第一个程序的附注是同样的）。我曾阅读ANSI C，里面并未要求整数必须用补码表示，所以程序也有可能因此不能用 。（在一些很古老的机子里用的可能是反码）。2004.3.14，Keith H. Duggar向我发送了上面提到的专利算法。这是我最早提出的算法

1
r=(+1|(v>>(sizeof(int)*CHAR_BIT-1)))*v

的升级版，因为少用了一个乘法。不幸的是，这个算法于2000.6.6被 Vladimir Yu Volkonsky申请了专利并用到了Sun系统上。2006.8.13，Yuriy Kaminskiy告诉我专利可能是无效的，因为在申请专利之前这个方法就已经被公开发表，比如1996年11月9日Agner Fog的《How to Optimize for the Pentium Processor》（如何为奔腾处理器做优化）。Yuriy还提到这个文档1997年的时候被翻译成了俄文，Vladimir可能读过了。此外，网站时光倒流机器（The Internet Archive）也存在到这里的旧链接。2007.1.30，Peter Kankowski 给作者分享了一个版本的求绝对值，灵感来源于Microsoft’s Visual C++编译器的输出。在这里作为最终解决方案。2007.12.6 Hai Jin抱怨运算的结果是有符号的，所以当计算负数中的最大值时，得到的结果还是负数。2008.4.15 Andrew Shapira指出上述三元运算符的方法可能会出现溢出，因为缺少(unsigned)的类型说明；为了最佳的可移植性，他建议写作： (v < 0) ? (1 + ((unsigned)(-1-v))) : (unsigned)v。2008.7.9 Vincent Lefèvre说服作者删除了它（上述的式）而采用了原来的式（解释中提到的那个式子）。因为即使在非二进制补码的机器上，根据ISO C99规范， -(unsigned)v也是正确的。-(unsigned)v运算时，先通过加2^N转换为无符号数，得到v的补码表示，我们称为U。所以U=v+2^N，又因为

-v=2^N - (v+2^N) = 2^N - U = 0 - U = -U ，所以 -(unsigned)v = -U = -v

译者注解

若v<0，则mask=111…111，算法1=(v-1)^-1 =-v 算法2=(v^-1) +1 = -v

算法1因为v-1除符号位外其余各位都与v相反，又 ^-1相当于按位取反，因此运算完毕后符号位清零，其余各位保留-v的原码。

算法2更直接，就是平时常用的补码和原码转换。

若v>=0，则mask=000…000，算法1= (v+0) ^0 =v 算法2= (v^0) - 0=v

计算两个整数的最大值和最小值（无跳转）

定义

1
2
3
int x;  // 两个整数
int y;   
int r;  // 结果

算法1

1
2
r = y ^ ((x ^ y) & -(x < y)); // min(x, y)
r = x ^ ((x ^ y) & -(x < y)); // max(x, y)

在极少数的机器上，跳转开销很大且没有条件转移指令，上述代码可能比有跳转的实现要快

1
r = (x < y) ? x : y

即使它多使用了两个指令（但一般跳转实现更快）。

解释：

因为若 x<y，-(x<y)为-1（补码为111…111），所以相当于 r= y^( (x^y) & ~0) = y^x^y =x

若x>=y，-(x<y)为0，所以相当于 r=y^( (x^y) & 0) = y^0=y

max同理

####算法2

如果能保证 INT_MIN <= x-y <= INT_MAX，则可以使用下面的代码，因为只用算一次 x-y所以更快

1
2
r = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // min(x, y)
r = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // max(x, y)

附注

1989 ANSI C没有明确右移行为，所以代码可能无法移植。如果因为溢出抛出异常

Ref：

https://site.douban.com/196781/ God-Mode 豆瓣小站，在该站的奇技淫巧（emmm。。。）条目下有本文大概半篇多的翻译。本人的很多翻译也参考了站内大神的翻译。