如何优化从LSB遍历整数位的函数，遇连续0链后停止？

需求说明 #

• 现有两个TypeScript位遍历函数：walkBitsFromLSB（从最低有效位LSB开始遍历）和walkBitsFromMSB（从最高有效位MSB开始遍历）
• 已实现walkRelevantBitsFromMSB，仅遍历第一个非零位起的相关位
• 需要优化walkBitsFromLSB：从LSB开始遍历，遇到高位连续0链时停止，禁止使用缓存/哈希表，需直接从输入整数n推导停止的遍历长度
• 示例：对于整数0b00000000000000000001111011101101，遍历需在最后一个1的位置结束

实现思路 #

核心是找到整数n的最高有效位（MSB）位置，因为超过该位置的所有位都是连续的0，只需遍历从LSB（第0位）到该位置的范围即可：

1. 特殊处理n=0的情况，直接终止遍历
2. 通过位右移操作推导最高有效位的位置
3. 遍历范围限定在第0位到最高有效位之间

优化后的TypeScript实现 #

function walkBitsFromLSB(n: number, callback: (bit: 0 | 1, position: number) => void): void {
  // 输入为0时无有效位，直接返回
  if (n === 0) return;

  // 计算最高有效位的位置（从0开始计数）
  let msbPosition = 0;
  let temp = n;
  while (temp >>= 1) {
    msbPosition++;
  }

  // 从LSB遍历到最高有效位
  for (let pos = 0; pos <= msbPosition; pos++) {
    const bit = (n >> pos) & 1 ? 1 : 0;
    callback(bit, pos);
  }
}

代码说明 #

• 先判断输入是否为0，避免无效遍历
• 通过循环右移临时变量temp，直到temp变为0，此时记录的msbPosition就是最高有效位的位置
• 遍历过程中通过位运算提取对应位置的位，调用传入的回调函数
• 全程无缓存/哈希表，完全通过位运算推导停止位置，符合需求

示例验证 #

以整数0b00000000000000000001111011101101（十进制7853）为例：

• 计算得最高有效位为第12位（2^12=4096，213=8192>7853）
• 遍历范围为第0位到第12位，刚好覆盖所有非零位后停止，与需求一致

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