这篇文章翻译自Bit Twiddling Hacks，相关版权信息可以参考原文

关于指令计数方法

在此处的计算算法的指令总数中，任何C运算符都计为一个指令。无需写入RAM的中间指令不计算在内。当然，这种方法只能用作机器指令实际数量和CPU时间的近似值。假定所有操作都花费相同的时间，这在现实中是不正确的，但是随着时间的流逝，CPU计算花费的时间会一直朝着这个方向发展。有许多细微差别决定了系统运行给定代码样本的速度，例如缓存大小，内存带宽，指令集等。最后，基准测试是确定一种方法是否真的比另一种方法更快的最佳方法，因此请考虑在你的CPU体系架构中使用该方法进行测试。

计算一个整数的符号

1
2
3
4
5
6
7
8
9
int v;    // we want to find the sign of v
int sign; // the result goes here

// CHAR_BIT is the number of bits per byte (normally 8).
sign = -(v < 0); // if v < 0 then -1, else 0
// or, to avoid branching on CPUs with flag registers (IA32)
sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));
// or, for one less instruction (but not portable)
sign = v >> (sizeof(int) * CHAR_BIT - 1);

对于一个32位的整数, 最后一个式子和sign = v >> 31是相等的，这个操作要比sign = -(v < 0)更快。这个技巧能够工作的原因在于，当执行右移操作时，最左边的一位会复制到其他位，当被移位的数是负数时，最左边一位是1，当被移动的数是正数时，最左边的一位是0，而当所有位都为1时，代表的就是-1。不幸的是，这种行为是和体系结构有关的。

如果你想要你的结构变成1或则-1，那么使用

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

另一方面，如果你想让结果变成-1，0或1, 那么使用

1
2
3
4
5
sign = (v != 0) | -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));
// Or, for more speed but less portability:
sign = (v != 0) | (v >> (sizeof(int) * CHAR_BIT - 1));  // -1, 0, or +1
// Or, for portability, brevity, and (perhaps) speed:
sign = (v > 0) - (v < 0); // -1, 0, or +1

相反，如果您想知道某数是否为非负数，结果用1或0表示，请使用

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

注意事项：2003年3月7日，Angus Duggan指出1989年的ANSI C规范保留了有符号右移实现定义的结果，因此在某些系统上，这种方法可能不起作用。为了获得更大的可移植性，Toby Speight在2005年9月28日建议在此处和全文中使用CHAR_BIT，而不是假设字节长8位。Angus推荐了上述更具移植性的版本，在2006年3月4日给出示例。Rohit Garg于2009年9月12日建议使用非负整数的版本。

判断两个整数是否有相反的符号

1
2
int x, y;                 // input values to compare signs
bool f = ((x ^ y) < 0);   // true if x and y have opposite signs

Manfred Weis 建议，我在2009年11月26日添加这个条目。

不用分支判断计算一个整数的绝对值

这种位运算已经失效, 不要使用

1
2
3
4
5
int v;           // we want to find the absolute value of v
unsigned int r;  // the result goes here
int const mask = v >> sizeof(int) * CHAR_BIT - 1;

r = (v + mask) ^ mask;

有专利的变更

1
r = (v ^ mask) - mask;

一些CPU没有计算绝对值的方法(或则使用他们的时候编译失败)。在机器上使用分支是昂贵的，上面的方法会比常规方法(即r = (v < 0)?-(unsigned)v:v)更快, 即便操作数是相同的。

在2003年3月7日，Angus Duggan指出1989年的ANSI C标准保留了有符号数右移的实现定义，所以在一些机器上该方法可能不会工作。我读过ANSI C，它并没有要求将值表示为二进制补码，因此也可能由于这个原因而不能工作(在数量很少的旧机器上仍使用二进制补码)。在2004年3月14号，Keith H. Duggar发给了我上述的变更版本, 它优于我最初想到的那个r = (+1|(v>>(sizeof(int)*CHAR_BIT-1)))*v，因为不使用乘法。然而不幸的是，在2000年6月6日该方法被Vladimir Yu Volkonsky申请了专利，并将专利交个了 Sun Microsystems。2006年8月13日，Yuriy Kaminskiy告诉我，该专利可能无效，因为该方法早在专利提交之前就已发布，例如1996年11月9日Agner Fog撰写的How to Optimize for the Pentium Processor。Yuriy还提到该文件于1997年被翻译成俄文，Vladimirk可能已经读过。此外，Internet存档也有一个旧链接。2007年1月30日，Peter Kankowski与我分享了他发现的abs版本，该版本受Microsoft Visual C++编译器输出的启发。它在此处作为主要解决方案。2007年12月6日，Hai Jin说结果是有符号的，因此在计算最负值的绝对值时仍为负。2008年4月15日，Andrew Shapira指出，通常的方法可能会溢出，因为当时缺少(无符号的)强制转换; 为了获得最大的可移植性，他建议使用(v < 0) ? (1 + ((unsigned)(-1-v))) : (unsigned)v。但是引用2008年7月9日的ISO C99规范，Vincent Lefèvre让我删除它，因为即使在非二进制补码机上-(unsigned)v也会是正确的。对-(unsigned)v首先通过加2N2^N来将负数转换为无符号数，得到v的二进制补码表示，我称之为U。然后将U取反，得到所需结果，即−U=0−U=2N−U=2N−(v+2N)=−v=abs(v)-U = 0 - U = 2^N - U = 2^N - (v + 2^N) = -v = abs(v)

不用分支判断计算两个整数的最大值或最小值

未测试

1
2
3
4
5
int x; // we want to find the minimum of x and y
int y;
int r; // the result goes here

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

在某些分支判断非常昂贵且不存在条件移动指令的稀有机器上，上述表达式可能比通常的方法快，即r = (x < y)?x：y，即使它多涉及了两个指令。(一般来说，通常的方法是最好的。)之所以可行，是因为如果x < y，则-(x < y)将全部为1，因此r = y ^ (x ^ y) & ~0 = y ^ x ^ y = x。否则，如果x >= y，则-(x < y)将全为零，因此r = y ^ ((x ^ y) & 0) = y。在某些机器上，将(x < y)计算为0或1需要分支指令，因此可能没有优势。

为了找到最大值, 使用

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

快速和肮脏的版本

如果您知道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规范未指定带符号的右移的结果，因此它们不可移植。如果在溢出时抛出异常，则x和y的值应为无符号或强制转换为无符号，以免不必要地抛出异常。

2003年3月7日，Angus Duggan指出了右移可移值性问题。2005年5月3日，Randal E.Bryant提醒我需要先决条件INT_MIN <= x-y <= INT_MAX，并建议使用非快速且肮脏的版本作为补丁。这两个问题仅涉及快速而肮脏的版本。Nigel Horspoon在2005年7月6日观察到gcc由于其评估方式(x < y)而在奔腾上产生的代码与通常的解决方案相同。在2008年7月9日，Vincent Lefèvre指出了以前版本的r = y +((x-y)&-(x <y))在减去时有潜在的溢出异常。Timothy B. Terriberry建议在2009年6月2日使用xor而不是add和subsub来避免转换和溢出风险。

判断一个整数是否是2的n次幂

未测试

1
2
3
4
unsigned int v;  // we want to see if v power of 2
bool f;          // the result goes here

f = (v & (v - 1)) == 0

请注意，此处错误地将0视为2的幂。要解决此问题，请使用:

1
f = v && !(v & (v - 1));

符号扩展(sign extending)

从固定位宽进行符号扩展(sign extending from a constant bit-width)

对于内置类型，例如char和int，符号扩展是自动的。但是，假设您有一个有符号的二进制补码x，它仅使用b位存储。此外，假设您想将x转换为一个具有b位以上位数的整数。如果x为正数，则可以简单的使用复制操作，但如果为负数，则必须扩展符号。例如，如果我们只有4位存储数字，则3以二进制形式表示为1101。如果我们有8位，则3为11111101。当我们转换为具有更多位数的表示形式时，将4位表示形式的最高有效位依次复制以填充目标位置。这就是符号扩展。在C语言中，从固定位宽进行符号扩展很简单，因为可以用结构或联合指定位字段。例如，要将5位转换为整数:

1
2
3
4
int x; // convert this from using 5 bits to a full int
int r; // resulting sign extended number goes here
struct {signed int x:5} s;
r = s.x = x;

以下是一个C++模板函数，该函数使用相同的语言功能在一个操作中从B位进行转换(当然，编译器会生成更多位)。

1
2
3
4
5
6
7
8
template <typename T, unsigned B>
inline T signextend(const T x)
{
  struct {T x:B;} s;
  return s.x = x;
}

int r = signextend<signed int,5>(x);  // sign extend 5 bit number x to r

John Byrd于2005年5月2日在代码中找到了一个错误(归因于html格式)。2006年3月4日，Pat Wood指出ANSI C标准要求位域必须具有关键字signed的签名；否则，符号未定义。

这里我以自己的语言重新解释一下这段c代码。

假设在x中存储的是一个5位的二进制，例如-16，及10000，则x为0x00000010，也就是说此时的x是10进制下的16。这段c代码的作用就是将x转换成一个32位的整数，即让r为-16。有如下测试程序:

1
2
3
4
5
6
7
8
9
10
11
12
// test.c
#include <stdio.h>

int main(void) {
    int x = 16;
    int r = 0;
    struct {signed int x:5} s;
    s.x = x;
    r = s.x;
    printf("test is: %d, result is: %d\n", x, r);
    return 0;
}
1
2
3
> gcc test.c -o test
> ./test
  test is: 16, result is: -16

从可变位宽进行符号扩展(sign extending from a variable bit-width)

未测试

有时候我们需要扩展一个数的符号，但是我们不知道它所表示的位数b。(或者我们可以使用类似 Java 的语言编程，这种语言没有位字段。)

1
2
3
4
5
6
7
unsigned b; // number of bits representing the number in x
int x;      // sign extend this b-bit number to r
int r;      // resulting sign-extended number
int const m = 1U << (b - 1) // mask can be pre-computed if b is fixed

x = x & ((1U << b) - 1); // (Skip this if bits in x above position b are already zero.)
r = (x ^ m) - m;

上面的代码需要四次操作，但是当位宽是一个常量而不是变量时，它只需要两次快速操作，假设上面的位已经是零。

一个不依赖位置b上方x的位为零的更快但不那么方便的方法是:

1
2
int const m = CHAR_BIT * sizeof(x) - b;
r = ( x << m ) >> m;

Sean A. Irvine建议我于2004年6月13日在此页面上添加符号扩展方法，他提供了m =(1 <<(b-1))-1; r =-(x＆~m) | x;作为优化的起点，我使m = 1U <<(b-1); r =-(x＆m) | x。但是在2007年5月11日，Shay Green建议使用上述版本，该版本所需的操作量比我的操作少一个。2008年10月15日，Vipin Sharma建议我添加一个步骤来处理x除我们要符号扩展的b位以外的其他位。2009年12月31日，Chris Pirazzi建议我添加更快的版本，对于恒定的位宽，只需要进行两个操作，对于可变的宽度，只需要进行三个操作。

用3次操作从可变位宽进行符号扩展(Sign extending from a variable bit-width in 3 operations)

未测试

在某些机器上，由于需要进行乘法和除法运算，因此以下操作可能会很慢。这个版本是4次操作。如果您知道初始位宽b大于1，则可以使用r =(x * multipliers [b]) / multipliers[b]在3次操作中进行这种符号扩展，这种方法只需要一个查找表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
unsigned b;  // number of bits representing the number in x
int x;       // sign extend this b-bit number to r
int r;       // resulting sign-extended number
#define M(B) (1U << ((sizeof(x) * CHAR_BIT) - B )) // CHAR_BIT=bits/byte
static int const multipliers[] =
{
  0,     M(1),  M(2),  M(3),  M(4),  M(5),  M(6),  M(7),
  M(8),  M(9),  M(10), M(11), M(12), M(13), M(14), M(15),
  M(16), M(17), M(18), M(19), M(20), M(21), M(22), M(23),
  M(24), M(25), M(26), M(27), M(28), M(29), M(30), M(31),
  M(32)
}; // (add more if using more than 64 bits)
static int const divisors[] =
{
  1,    ~M(1),  M(2),  M(3),  M(4),  M(5),  M(6),  M(7),
  M(8),  M(9),  M(10), M(11), M(12), M(13), M(14), M(15),
  M(16), M(17), M(18), M(19), M(20), M(21), M(22), M(23),
  M(24), M(25), M(26), M(27), M(28), M(29), M(30), M(31),
  M(32)
}; // (add more for 64 bits)
#undef M
r = (x * multipliers[b]) / divisors[b];

以下变体不是可移植的，但是在采用算术右移并保持符号的体系结构上，它应该很快。

1
2
const int s = -b; // OR:  sizeof(x) * CHAR_BIT - b;
r = (x << s) >> s;

Randal E. Bryant在2005年5月3日指出了一个早期版本的错误(该错误使用multipliers[]作为除数[])，在x = 1和b = 1的情况下失败。

有条件地在不分支的情况下设置或清除位(Conditionally set or clear bits without branching)

未测试

1
2
3
4
5
6
7
8
bool f;           // conditional flag
unsigned int m;   // the bit mask
unsigned int w;   // the word to modify:  if (f) w |= m; else w &= ~m;

w ^= (-f ^ w) & m;

// OR, for superscalar CPUs:
w = (w & ~m) | (-f & m);

在某些体系结构上，缺少分支可以节省似乎是两倍多的运算量。例如，在AMD Athlon™XP 2100+上进行的非正式速度测试表明，速度提高了5-10％。 Intel Core 2 Duo运行超标量版本的速度比第一个快16％。 Glenn Slayden于2003年12月11日给了我第一个表达式。2007年4月3日，Marco Yu与我分享了超标量版本，并在两天后提醒我有个打字错误。

有条件地在不分支的情况下对值求反(Conditionally negate a value without branching)

未测试

如果仅在标志为false时才需要求反，请使用以下方法避免分支:

1
2
3
4
5
bool fDontNegate;  // Flag indicating we should not negate v.
int v;             // Input value to negate if fDontNegate is false.
int r;             // result = fDontNegate ? v : -v;

r = (fDontNegate ^ (fDontNegate - 1)) * v;

如果你只需要在flag为true时进行求反，那么使用以下命令:

1
2
3
4
5
bool fNegate;  // Flag indicating if we should negate v.
int v;         // Input value to negate if fNegate is true.
int r;         // result = fNegate ? -v : v;

r = (v ^ -fNegate) + fNegate;

Avraham Plotnitzky建议我在2009年6月2日添加第一个版本。为避免乘法运算，我于2009年6月8日提出了第二个版本。AlfonsoDe Gregorio在2009年11月26日指出代码缺少一些括号，并且获得了漏洞赏金。

根据掩码合并两个值中的某些位(Merge bits from two values according to a mask)

1
2
3
4
5
6
unsigned int a;    // value to merge in non-masked bits
unsigned int b;    // value to merge in masked bits
unsigned int mask; // 1 where bits from b should be selected; 0 where from a.
unsigned int r;    // result of (a & ~mask) | (b & mask) goes here

r = a ^ ((a ^ b) & mask);