大整数归约至0的操作步数统计优化方案咨询

Great question! Let's dig into how we can supercharge this step-counting function using binary representations and bitwise operations—this is a classic example of leveraging how computers natively handle integers to avoid slow loops.

Why the Original Code Slows Down for Large Integers #

Your initial implementation simulates every single step (subtract 1 or divide by 2) one by one. For extremely large integers, this means hundreds, thousands, or even millions of loop iterations—each with a conditional check and arithmetic operation. That's where the slowdown happens.

The Binary Representation Insight #

We can skip the loop entirely by using the binary form of the integer to calculate the total steps directly. Here's the breakdown:

• Binary 0s: These correspond to even numbers. Each 0 requires one step (divide by 2, which is a right shift in binary).
• Binary 1s: These correspond to odd numbers. Every 1 (except the highest-order 1) requires two steps: subtract 1 to turn it into a 0, then divide by 2. The highest-order 1 only needs one step (subtract 1 to reach 0, no division needed).

Putting this all together, the total steps equal:

1. (Number of bits in binary - 1): This accounts for all the divide-by-2 (right shift) operations.
2. (Number of 1s in binary): This accounts for all the subtract-1 operations.

Let's verify with examples:

• 7 (binary 111): (3 bits -1) + 3 ones = 2 + 3 = 5 steps (matches manual calculation)
• 4 (binary 100): (3 bits -1) + 1 one = 2 + 1 = 3 steps (correct)
• 1 (binary 1): (1 bit -1) +1 one = 0 +1 =1 step (correct)

Optimized Implementation #

Using Python's built-in bitwise methods, we can write an extremely fast version of the function:

For Python 3.10+ (Fastest Option)

bit_count() is a built-in method for integers in Python 3.10+, optimized for speed:

def counting_steps(my_number):
    if my_number == 0:
        return 0
    return (my_number.bit_length() - 1) + my_number.bit_count()

For Older Python Versions

If you're on a version before 3.10, use bin(my_number).count('1') to count the 1s:

def counting_steps(my_number):
    if my_number == 0:
        return 0
    return (my_number.bit_length() - 1) + bin(my_number).count('1')

Bonus: Manual Efficient Bit Counting #

If you want to implement the bit-counting logic yourself (though the built-in methods are already optimized), Brian Kernighan's algorithm is a fast way to count set bits by repeatedly clearing the rightmost 1:

def count_set_bits(n):
    count = 0
    while n:
        n &= n - 1  # Clear the rightmost set bit
        count += 1
    return count

def counting_steps(my_number):
    if my_number == 0:
        return 0
    return (my_number.bit_length() - 1) + count_set_bits(my_number)

Performance Boost #

This optimization drops the time complexity from O(k) (where k is the total number of steps, linear with the integer's size) to O(1) (or O(log n) for manual bit counting)—a massive speedup for large integers. No more looping through every single step!

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