获取二进制串Most significant not set bit与Least significant not set bit的高效方法

给定二进制字符串（例如10111101111），需要找到：

• 最高位未设置位：从左侧（最高位方向）开始的第一个0的索引
• 最低位未设置位：从右侧（最低位方向）开始的第一个0的索引

已知O(n)的遍历解法，以下是关于更高效实现的分析：

核心结论 #

针对二进制字符串本身，不存在理论上比O(k)更优的算法（k为目标位到字符串端点的距离）——因为字符串是线性存储的序列，必须从端点开始逐个检查字符，直到找到目标的0。但可以利用语言内置的字符串操作优化实际运行效率，这类操作通常是底层优化实现，比手写循环更快。

具体实现方案 #

1. 最高位未设置位（左数第一个0）

直接使用语言内置的「正向查找第一个指定字符」方法，比如Python的str.find('0')、Java的String.indexOf('0')。这类方法底层经过优化，执行效率优于手写for循环，最坏时间复杂度仍为O(n)（比如全1字符串需遍历到末尾），但实际性能更优。

示例（Python）：

binary_str = "10111101111"
msb_not_set_idx = binary_str.find('0')  # 返回1，对应左数第一个0的索引

2. 最低位未设置位（右数第一个0）

使用语言内置的「反向查找最后一个指定字符」方法，比如Python的str.rfind('0')、Java的String.lastIndexOf('0')。同样是底层优化实现，反向定位目标字符，实际运行效率高于手动反向遍历。

示例（Python）：

binary_str = "10111101111"
lsb_not_set_idx = binary_str.rfind('0')  # 返回6，对应右数第一个0的索引

额外说明：二进制数值的特殊情况 #

如果处理的是二进制数值类型（而非字符串），可以通过位运算实现O(1)或O(log n)的查找，比如：

• 最高位未设置位：计算数值的总位数后，用掩码定位；
• 最低位未设置位：利用~num & (num + 1)这类位运算直接获取位置。
  但这类方法仅适用于数值，无法直接迁移到字符串场景。

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