我已经实现了一个大量使用 ffs() 函数的应用程序。我想为它提供兼容性实现，并且就 uint8_t 有如下内容（只是为了给你一个尽可能最小的示例，因为64位版本会更复杂）：

static inline int ffsu8(uint8_t v)
{
  int r; 
  static const int MultiplyDeBruijnBitPosition[8] =
  { 
    0,1,6,2,7,5,4,3
  };
  r = MultiplyDeBruijnBitPosition[((uint8_t)((v & -v) * 0x1d)) >> 5];
  return v?(r+1):0;
}

可以通过将查找表做得更长（并通过试错重新计算其中的内容）、将 0x1d 改为在正确比特宽度上的一个合适的De Bruijn序列、并相应地修改右移操作来为查找表提供足够的位数，来实现对16位、32位和64位值的类似处理。

我对 v & -v 的技巧提取最低有效置位并把其他所有置位清零感到有些担心。

我理解 v + (-v) = 0是一个应该成立的关系，在无符号世界中，只有当 -v 计算出 v 的二进制负数（即 -v）时，v + (-v) 才为真。

然而，并不能保证某台机器在带符号数上使用二进制补码运算。另外，在 -v 中，编译器是不是会在计算逆运算前把一个 uint8_t 自动提升为一个 int，这意味着逆运算是在有符号数的算术里计算的，而不是在无符号数的算术里？然而，对于 uint64_t 来说，这样的提升很可能不会发生，因为很难相信 int 比 uint64_t 更宽。

那么，我是否可以在任意位宽上可靠地使用 v & -v 这一技巧来提取最低有效置位？“可靠”在这里指的是在所有符合ISO C99的实现中都成立。如果不能保证对无符号逆运算使用二的补码算术，那 v & (~v+1) 呢？编译器很可能会把它检测为二的补码逆运算，实际使用单条指令来完成。

编辑：根据我在回答中的发现以及Eric Postpischil的精彩回答和下面的评论，我决定这样做：

static inline int ffsu8(uint8_t v)
{
 int r; 
 static const int MultiplyDeBruijnBitPosition[8] =
 { 
   0,1,6,2,7,5,4,3
 };
 r = MultiplyDeBruijnBitPosition[((uint8_t)(((uint8_t)(v&(uint8_t)-v))*0x1d))>>5];
 return v?(r+1):0;
}

之所以这样可行，是因为 v 的类型是无符号类型。

解决方案

摘要

-(uintN_t)x, (v & -v), 和 v & (~v+1) 并不安全。下面给出能证明这一点的示例。

v & - (uintmax_t) v 是安全的。

细节

从问题标题来看：

… -(uintN_t)x …

考虑 x = 1、一个 uint16_t 强制转换，以及一个使用32位反码 int 的C 实现。期望的结果是1 的32位二的补数，即11111111 11111111 11111111 111111112。在这种情况下，1将被转换为 uint16_t，这不会改变数值，得到1。然后这个 uint16_t 值被提升为 int，再次得到1。随后对这个 int 取负。由于 int 是反码，结果是11111111 11111111 11111111 111111102，这并不是期望的结果。

来自问题正文：

… (v & -v) …

考虑 v = 1，以及一个使用32位反码 int 的C 实现。这里期望的结果是 -v 产生二的补数，11111111 11111111 11111111 111111112，而 v & -v 产生1。在这种情况下，对于 -v，1将在反码 int 中被取反，产生11111111 11111111 11111111 111111102。然后 & 将产生0，这不是期望的结果。

因此答案是否定的，这两个代码片段都不能被保证符合C 1999标准而按期望工作。

C 2024增加了一个要求，规定使用二的补码（在6.2.6.2条款中），因此上述两个片段在C 2024中会工作。

此外，来自问题：

If it's not guaranteed that two's complement arithmetic is used for unsigned inverse, what about v & (~v+1)?

如果 v 的值的量级不太大，这将起作用。然而，即使在二的补码系统中，如果 v 太大，也可能失败。考虑一个使用32位二的补码的C 实现，其中 int，且 v = − 2^31 = 10000000 00000000 00000000 000000002。则 ~v 产生01111111 11111111 11111111 111111112。这是最大 int 值，即2^31−1。然后 ~v+1 溢出，其行为不受C 标准定义。然而，只要 v 是无符号类型，这种情况是安全的，因为它要么比 int 更窄，不能产生麻烦的值，或者它足够宽，不会被提升到 int。

另一个与 v & (~v+1) 相关的问题在于 ~v 可能产生陷阱表示（本质上是一种保留用于指示该类型没有有效值的位模式）。在此陷阱表示上再加1 将导致未定义行为。陷阱表示在符号-幅度表示或二的补码表示中为10000000 00000000 00000000 000000002，在一的补码中为11111111 11111111 11111111 111111112。前者可以在 v 的 unsigned int 值01111111 11111111 11111111 111111112时从 ~v 产生，后者可以从0 产生，因此即使 v 为无符号类型，v & (~v+1) 也并非始终安全。

v & - (uintmax_t) v 在C 1999中会起作用，因为此时的取反是在一个不能被提升为带符号类型的无符号类型中完成。一个优秀的编译器可能会把它优化成使用更小类型的代码，在必要时（尤其是它被立即转换为更窄的类型时）会更明显。