Power of 2 game code in python

This can actually be solved with a super efficient 1 line of code, but the explanation is long :)
(and there are a few other things I should point out first)

Your code will fail with any input bigger than \$2^{62}\$ because you never overshoot this number by multiplying by 2 a power of 2 (in your code: current). This is because a signed long has only enough bits to represent powers of 2 up to \$2^{62}\$ (you could have used it as an unsigned variable to have one extra bit, but it still wouldn't be enough to avoid this problem with the biggest numbers that the challenge says are expected input), multiplying it by 2 will cause the left most bit to become 1, which turns it into a big negative number, and multiplying it by 2 again will make it 0 which will then stay 0 no matter how much you multiply it, so your code will enter an infinite loop.

Once you detect that a number is a power of 2 you shouldn't reset previous and current to 2 because a power of 2 divided by 2 is still a power of 2, so you know you can divide current by 2 together with n.

A thing you could use to your advantage is the way powers of 2 look in binary code:

power | number | binary | even/odd power
2^0   = 1      = 00001  | even
2^1   = 2      = 00010  | odd
2^2   = 4      = 00100  | even
2^3   = 8      = 01000  | odd
2^4   = 16     = 10000  | even

Notice how all bits are 0 except one, the position of this 1 bit tells you if you need an odd or even number of divisions (turns in the game) to reach 1.

long filter = 0b101010101010101010101010101010101010101010101010101010101010101L;
boolean oddPower = (n & filter) == 0;

As soon as you reach a power of 2, this check is enough to tell you who's gonna win. An odd number of turns left means that the player whose turn it is now will win, otherwise the other player will win.

We can go further with looking at the bits and bypass the need to find the next lower power of 2 to divide n by it if n is not a power of 2. As you already know, any power of 2 is represented by a single 1 bit and lots of 0 bits. Now let's take a look at a few numbers represented in binary code:

3 = 0011
4 = 0100
5 = 0101
6 = 0110
7 = 0111
8 = 1000

When the number isn't a power of 2, according to the game you need to remove the next lower power of 2. In binary it's gonna look like removing the left most bit (you can look at the numbers above to confirm this). Given our knowledge and solutions so far, we can rewrite the rules of the game to simple binary operations:

if ( number is a power of 2 ) then:
    use the check from the previous part of my answer to figure out the winner.
else:
    turn the most left 1 bit to 0.

This means the number of turns until we reach a power of 2 and find the answer depends on how many 1-bits are in the number, and knowing if this number is odd or even - combined with the answer to whether the power you reach is odd or even - is all you really need to know to predict the outcome of the game!

Let's test this solution: here's what you see when you track the changes in a number as the game is played, in binary:

1000000110100
0000000110100
0000000010100
0000000000100
0000000000010
0000000000001

There are 4 1s (even number) but you don't remove the last 1 bit so ignore it and say there are 3 1s to be removed (odd number) and the first power of 2 you reach is 4 (even) so overall there will be an odd number of turns taken in the whole game, which you can see is true.

Here is the most optimized code I could possibly write to solve this:

static String counterGame(long n){
    boolean richardWins = true;

    while((n & 1) == 0){
        richardWins = !richardWins;
        n >>>= 1;
    }
    while(n != 1){
        if((n & 1) == 1)
            richardWins = !richardWins;
        n >>>= 1;
    }

    return richardWins ? "Richard" : "Louise";
}

This code looks at each bit once, so the time complexity of this code is O(log(N)) where N is the input number, and log(N) is the worst case scenario for the number of bits needed to represent the input number in binary.

Judging by the fact that the exception to the rules (where Richard wins when Louise gets the 1 at the start of the game) emerges naturally with this solution if you don't add an if statement at the start to take care of it, I'd say this is what the author of this challenge expected to be the best possible answer.

Bonus

There are processor instructions for counting 1 bits and trailing zeros, so you could actually do the whole thing in one line instead of manually looping through the bits, and using these processor instructions is faster:

static String counterGame(long n){
    return ((Long.numberOfTrailingZeros(n) & 1) == 1) ^ ((Long.bitCount(n) & 1) == 1) ? "Richard" : "Louise";
}

EDIT: a shorter code suggested by @JS1:

By subtracting one, it turns all the trailing zeroes into trailing ones, so that they can be counted by bitCount.

static String counterGame(long n){
    return ((Long.bitCount(n-1) & 1) == 0) ? "Richard" : "Louise";
}

How do you code a power of 2 in Python?

How do you code a power of 2?

How do you code a power in Python?

What number is power of 2?