Python求最大n使2ⁿ≤X的性能优化问题求助

Hey there! I see you're working on this Python assignment on repl.it, and hitting issues with large numbers like 10^8 + 2—either the code crashes or gets super slow. Let's break down why your current code is struggling, then go through some efficient fixes.

What's Wrong with the Original Code? #

Let's look at your code first:

X = int(input())
a = X//2
while a > -1:
    if (2**a) <=x:  # Note: You used lowercase x here, but defined uppercase X—this is a bug!
        print(a)
        print(2**a)
        break
    else:
        a -= 1

Two big problems here:

• Variable name mismatch: You defined X but checked against x—that's a NameError waiting to happen (though you said small numbers work, maybe you fixed that typo locally?).
• Horrible efficiency for large numbers: For an input like 1e8, X//2 is 50,000,000. Your loop has to run 50 million times before finding the right n—that's why it's slow or crashes from too many iterations.

Efficient Solutions #

Let's go through a few optimized approaches, all of which run in O(log X) time (or even O(1)!) no matter how big X is.

1. Bitwise Operation (Fastest, O(1) Time) #

In binary, any number 2ⁿ is a 1 followed by n zeros. The position of the highest set bit in X gives us exactly n. For example:

• X=8 is 1000 in binary—highest bit is at position 3 (counting from 0), so n=3, 2³=8.
• X=10 is 1010—highest bit is position 3, 2³=8 ≤10.

Python makes this easy with the .bit_length() method:

X = int(input())
if X == 0:
    print("n doesn't exist (since 2ⁿ is always positive)")
else:
    n = X.bit_length() - 1
    power_of_two = 1 << n  # Equivalent to 2**n, but faster
    print(n)
    print(power_of_two)

This works instantly even for huge numbers like 10^100—no loops at all!

2. Logarithm with Precision Check (Mathematical Approach) #

We can use math.log2() to calculate the exponent, but we have to be careful with floating-point precision errors (since very large integers might not convert perfectly to floats). Here's how to handle it:

import math

X = int(input())
if X == 0:
    print("n doesn't exist (since 2ⁿ is always positive)")
else:
    n = int(math.log2(X))
    # Double-check to avoid precision issues (e.g., X=2^20 might log to 19.999999999999996)
    if (2 ** (n+1)) <= X:
        n +=1
    elif (2 ** n) > X:
        n -=1
    print(n)
    print(2**n)

This is almost as fast as the bitwise method, but requires a quick check to fix any floating-point inaccuracies.

3. Optimized Loop (Logarithmic Iterations) #

If you want to stick with a loop but make it efficient, instead of starting from X//2, we can start from 0 and double the exponent until we exceed X, then backtrack. This only takes log2(X) iterations:

X = int(input())
if X == 0:
    print("n doesn't exist (since 2ⁿ is always positive)")
else:
    n = 0
    current_power = 1  # 2^0
    # Find the first power larger than X
    while current_power * 2 <= X:
        current_power *=2
        n +=1
    print(n)
    print(current_power)

For X=1e8, this loop runs only 27 times—way better than 50 million!

Testing with Large Numbers #

All three methods will handle 10^8 +2 easily:

• Input: 100000002
• Output should be 26 and 67108864 (since 2^26=67108864 ≤100000002, and 2^27=134217728 >100000002).

Pick whichever method makes the most sense for your assignment—bitwise is the fastest and cleanest if you're allowed to use it!

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