如何快速计算任意奇数在指定操作流程中的subtimes（减1次数）？

1. 规律与2^n的关联 #

这个规律完全和2^n相关。

形如2^n - 1的数，二进制形式是连续n个1（比如2^3-1=7，二进制为111）。按照规则处理时：

• 第一次减1得到2^n - 2（二进制111...110），subtimes加1；
• 之后每一步都是除以2，直到变成2^(n-1)-1（二进制为n-1个1）；
• 重复此过程直到数字变为0，总共需要n次减1操作，即subtimes = n。

而其他奇数的二进制中必然存在0，处理时遇到0对应的位可直接通过除以2跳过，无需额外减1操作，因此它们的subtimes必然小于同区间内最大的2^n-1的subtimes。这个规律的核心就是二进制中连续1的长度，而2^n-1恰好是二进制连续n个1的数，和2^n直接绑定。

2. 更快的计算方法 #

当然存在，无需逐次模拟操作，通过二进制分析就能快速算出subtimes：

subtimes的本质就是该奇数二进制表示中1的个数。原因很简单：每次遇到奇数减1，本质是把二进制末尾的1变成0（对应一次subtimes计数），之后除以2就是右移一位跳过末尾的0；整个过程就是逐个消除二进制中所有1的过程，每个1对应一次减1操作。

基于这个结论，我们可以写出时间复杂度为O(log num)的快速计算方法，远快于逐次模拟的O(num)：

def getsubtimes_fast(num):
    return bin(num).count('1')

验证几个例子：

• 21的二进制是0b10101，1的个数为3，对应subtimes=3，符合预期；
• 7的二进制是0b111，1的个数为3，对应subtimes=3，符合预期；
• 5的二进制是0b101，1的个数为2，实际处理过程为5→4→2→1→0，减1两次，结果正确。

对于大数比如2^1000 -1，直接统计二进制中1的个数就能得到subtimes=1000，无需循环上千次。

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