嘿，这个问题问得太棒了！你提到的逐位检查的朴素方法虽然好理解，但在现代CPU上，咱们完全能做到**O(1)**时间复杂度的实现，比线性遍历高效太多——这绝对不是理论最优，而是有实打实的位运算技巧和硬件指令支持的。

核心思路：利用位运算直接定位 #

找最低0位的本质，其实是找原数中第一个为0的位。我们可以通过以下技巧快速定位：

• 反向思维：找~x（按位取反）中的最低1位——因为原数的0位取反后就是1位，而找最低1位可以用经典的y & -y（y就是~x）。
• 更直接的组合运算：对于无符号64位整数x，(~x) & (x + 1)会直接给出最低0位对应的掩码。举个例子：
  • 假设x = 0b1011（二进制4位），x + 1 = 0b1100，~x = 0b0100，两者按位与得到0b0100，正好对应原数中最低的0位（第2位，0索引）。
  • 原理：x + 1会把原数中最低的连续1全部翻转为0，并把第一个遇到的0翻转为1；~x则把原数的0翻转为1，1翻转为0。两者按位与后，就只剩下那个被x+1翻转的1位——也就是原数的最低0位。

快速获取位位置 #

得到掩码后，要获取具体的位索引（从0开始计数），可以用编译器内置的位操作函数：

• 在GCC/Clang中，用__builtin_ctzll(mask)：返回掩码中末尾连续0的个数，也就是最低0位的索引。比如掩码0b0100，返回2。
• 在MSVC中，用_tzcnt_u64(mask)，功能完全一致。

这些内置函数会被编译器直接翻译成CPU的单条指令（比如x86的BSF、ARM的CLZ配合移位），速度快得离谱。如果非要纯位运算实现（不依赖编译器特性），也可以用分治式位运算技巧，但实际开发中完全没必要舍近求远。

边界情况处理 #

如果x是全1的64位掩码（0xFFFFFFFFFFFFFFFF），那不存在0位，这时候(~x) & (x + 1)会得到0，需要单独判断这种情况，比如返回-1或者64（根据你的业务逻辑而定）。

对比朴素迭代法 #

• 朴素迭代法的时间复杂度是O(n)，最坏情况要遍历全部64位（比如全1的情况）；
• 位运算方法是O(1)，不管输入是什么，都是固定次数的运算，直接利用CPU硬件支持的指令，速度提升非常明显。

什么时候朴素法有用？ #

只有在一些极端老旧的CPU（不支持位运算指令）或者非常受限的嵌入式环境中，朴素迭代法可能才是可行选项——但现在几乎所有现代CPU都支持这些位操作指令，所以优先选择O(1)的方法。

内容的提问来源于stack exchange，提问作者Makogan