求解释C语言中统计二进制连续1的代码行n = (n & (n<<1))

核心运算规则 #

&是按位与运算符，运算规则为：对两个操作数的每一位二进制位逐一比对，只有对应位置的两个值都为1时，结果的对应位才为1，其余情况均为0。

整行代码的作用 #

当你把n和左移1位后的n做按位与时，本质是把n的二进制表示中，所有连续1的段长度统一减1：

举个示例，假设n的二进制为1101110：

• 原n补前导0对齐后为 01101110
• n << 1的结果为 11011100
• 按位与的结果为 01001100
  你可以明显看到：原来的3段连续1（长度2、1、3），运算后变成了长度1、0、2的连续1段，恰好都比原来短1位。

对应统计最大连续1需求的使用逻辑 #

统计二进制连续1的最大个数时，你可以循环执行这行代码，每执行一次计数加1，直到n变为0时停止循环，最终的计数值就是二进制中连续1的最大个数，示例验证如下：

• 示例输入n=14，二进制为1110，最大连续1个数为3
  1. 第一次执行代码：n = 1110 & 11100 = 01100，计数为1
  2. 第二次执行代码：n = 01100 & 11000 = 01000，计数为2
  3. 第三次执行代码：n = 01000 & 10000 = 0，计数为3
  4. 此时n为0，循环结束，得到结果3和预期一致

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