获取最左边的最后一个非零位
(Gettin last non zero bit on the left)这个问题的出现的原因是为了找到一个数中最左边的非零位，也就是最高位的1所在的位置。解决方法可以使用x86架构上的BSR指令（bit scan reverse），或者是PowerPC架构上的cntlz指令（count leading zeros）。
BSR指令的工作原理是搜索源操作数中最高位的1，然后将其位索引存储在目标操作数中。源操作数可以是寄存器或者内存位置，目标操作数是寄存器。位索引是相对于源操作数的第0位的无符号偏移量。如果源操作数的内容为0，则目标操作数的内容是未定义的。
以下是使用gcc编写的示例代码：
#includeint main (int,char**) { int n=1; for (;;++n) { int msb; asm("bsrl %1,%0" : "=r"(msb) : "r"(n)); std::cout << n << " : " << msb << std::endl; } return 0; }
BSR指令在一些x86架构的处理器上非常快速，但在其他处理器上可能是微码级别的。同样地，PowerPC架构上的cntlz指令也类似。
如果想要了解更多关于内嵌汇编的知识，可以参考这篇[内嵌汇编教程](https://doc.lagout.org/network/alp-folder/alp-ch09-inline-asm.pdf)，其中的第9.4节展示了使用内嵌汇编比循环代码要快得多。
实际上，这个指令通常会被微码级别地转化成一个循环，因此速度会比较慢。至于是BSR指令还是cntlz指令，根据上面提到的x86-timing.pdf文档，BSR指令只在Netburst Pentium处理器上比较慢。关于PowerPC架构的情况，我没有太多了解。
除了使用特定的指令，也可以使用GCC提供的`__builtin_clz`（或者`__builtin_clzll`）函数来实现相同的功能。这个函数在输入为0时的行为是未定义的，可以编译成x86上的单个BSR指令。如果有的话，还可以使用LZCNT指令，因为它在更多的CPU上速度更快（例如在AMD上，即使BSR很慢，LZCNT也很快，可能是因为BSR的奇怪行为是根据输入而不是结果设置ZF标志）。在目标架构上选择最佳的方法，因为它不仅限于x86。总之，尽量避免使用内嵌汇编，因为它会破坏常量传播和一些其他优化。
最后，需要注意的是，之前提到的两个链接已经失效了。对于自己的实际用例，进行基准测试是最好的方法。聪明的算法是否更快可能取决于CPU的执行单元与“附近”代码的联系（如果有的话），以及您要测试的值的分布等等。
获取最左边的最后一个非零位是一个常见的问题，可以通过以下方法解决。
首先，我们知道2^N是一个只有第N位设置为1的整数（1 << N），那么找到最高位设置为1的位置（N）就是对这个整数进行以2为底的对数运算。
下面是一种常见的解决方法，使用了一个简单的while循环和右移操作。代码中的条件判断语句(v >> 1)是将v右移一位，直到最左边的位被移出（注意，C将任何非零值视为true），同时使用一个计数器r记录右移的次数。
unsigned int v;
unsigned r = 0;
while (v >>= 1) {
r++;
}
这种"显而易见"的算法可能对于每个人来说都不是很透明，但是当你意识到代码重复右移一位，直到最左边的位被移出（注意，C将任何非零值视为true），然后返回右移的次数时，它就变得很容易理解。这也意味着即使有多个位被设置为1，结果也总是针对最高位。
在这个链接的页面中还有更快、更复杂的解决方法。然而，如果你知道你处理的是有很多前导零的数字，那么简单的方法可能提供可接受的速度，因为在C中位移是相当快的，而且简单的算法不需要对数组进行索引。
需要注意的是，在使用64位值时，对于使用过于聪明的算法要非常谨慎；其中许多算法仅对32位值有效。
有人可能会问，为什么我们不会一直右移位直到陷入while循环中。通过使用调试器逐步执行代码，可以解释循环为什么会退出。基本上，循环退出是因为条件表达式的值为0（C将0视为false），一旦最后一个1位被移出右侧，条件表达式的值就会为0。
这种方法使用了最终结果，这是个好主意 🙂
需要注意的是：对于有符号整数，右移操作可能会失败，所以必须使用无符号类型进行右移操作。
如果使用的是Java、JavaScript或D等语言，需要使用逻辑右移运算符`>>>`，并且可能还需要使用比较运算符`!= 0`和一些未指定的括号。
最后，这种方法比使用`(unsigned int)log2(val)`更快两倍（没有优化）。
需要注意的是，这是针对无符号整数的逻辑右移，对于有符号整数，它可能是逻辑右移，也可能不是（实际上通常是算术右移）。
"这种方法比使用`(unsigned int)log2(val)`更快两倍"——这是最微弱的赞美。
GCC提供了一些内置函数来计算一个数的前导零位数（leading zero bits），即从最高有效位开始连续的0的个数。这些内置函数包括`__builtin_clz`、`__builtin_clzl`和`__builtin_clzll`，分别用于无符号整型、无符号长整型和无符号长长整型。
这些函数的作用是返回输入值x的前导零位数。如果x为0，则结果是未定义的。
如果输入可以为0，可以使用一个有用的技巧来获取最左边的非零位，即`__builtin_clz(x | 1)`。将x或1会将最低位设置为1，而不会修改其他位，这样输出结果就会是31（对应于x=0），而对于其他任意输入，输出结果不会改变。
如果不想使用这种方法，另一种选择是使用特定平台的内部函数，比如ARM GCC的`__clz`（无需头文件），或者在支持`lzcnt`指令的x86 CPU上使用`_lzcnt_u32`（需注意，`lzcnt`在旧的CPU上被解码为`bsr`指令，对于非零输入，会得到31减去前导零位数）。
不幸的是，对于那些在输入为0时将结果定义为32或64（根据操作数宽度）的非x86平台，没有一种可移植的方式可以利用各种前导零位数指令。x86的`lzcnt`也是这样，而`bsr`则会产生一个位索引，编译器必须将其翻转，除非使用`31-__builtin_clz(x)`。
MSVC提供了`_BitScanReverse`函数用于获取最左边的非零位。对于x86架构，当`lzcnt`不可用时，它可以编译成单个BSR指令。这是`__builtin_ctz`相对于`ffs`的一个重要优势，后者需要编译成BSF和CMOV来处理输入为零的情况。对于没有足够短的实现（例如，没有`clz`指令的旧ARM）的架构，gcc会生成对libgcc辅助函数的调用。
需要注意的是，这些函数在输入为0时的行为是未定义的，这样可以让它们在x86上编译成单个BSR指令，即使没有`lzcnt`指令。这对于`__builtin_ctz`相对于`ffs`来说是一个巨大的优势，后者需要编译成BSF和CMOV来处理输入为零的情况。在没有足够短的实现（例如，没有`clz`指令的旧ARM）的架构上，gcc会生成对libgcc辅助函数的调用。
总之，为了获取一个数的从左边开始的最后一个非零位，可以使用GCC的内置函数`__builtin_clz`、`__builtin_clzl`和`__builtin_clzll`，或者根据平台使用相应的特定指令或函数。但是需要注意，对于输入为0的情况，结果是未定义的。