Calculating the number of rounds required to complete a tournament We're running an heads-up tournament on our website, where the goal is to keep playing until a single winner remains. This works much the same as e.g. a tennis tournament bracket.

However, it only works perfectly if the number of participants is a power of 2, and this happens only rarely, so most of the time the first step is to play a round where some number of participants get a free win (a "bye") into the next round, in order to get the number of players down to the closest power of 2.

Everything works just fine, but I have a nagging suspicion that the part that calculates the number of rounds required to complete the tournament can be heavily improved. Here's the code I'm using to calculate it:

function totalRounds($participants)
{
    $closestLowerPow2 = pow(2, (strlen(decbin($participants)) - 1));

    $roundsWithoutByes = (int) log($closestLowerPow2, 2);

    return $participants == $closestLowerPow2
        ? $roundsWithoutByes
        : $roundsWithoutByes + 1;
}


So the length of the binary minus 1 is the closest power. Use log to find out how many rounds that requires, since if e.g. there are 8 participants, then there are 3 rounds to play, as 2³ = 8. Finally, add a round if we need to have a round with byes before that.

Is there a smarter way I'm overlooking? :)
Well, I feel like an idiot but I finally figured out why it seemed like there should be an obvious solution - one hour after posting, and three after starting to think about it. If I'm not allowed to post the answer myself, please let me know and I'll remove it.

function totalRounds($participants)
{
    return strlen(decbin($participants - 1));
}


The logic goes as follows: each bit in a string representation of the number of participants as a binary can be seen as a doubling of the number of participants, as long as the total number is a power of 2.

Then, by the same logic, each bit (except for the left-most one) can be seen as the reverse - a halving of the number of participants. And this is exactly what we want: each round, half of the players should be eliminated.

If we need to assign byes, that basically means we need to do one more round than that - so we can just use the string length straight away. But if we don't, then we need to disregard the left-most bit.

So if we start by subtracting one from the number of participants, that means that e.g. 8 participants = 1000 in binary turns into 7 = 111, which requires three rounds. For 9-15 participants, the string length would not change, so it's still correct. And for 16, the same logic applies as did to 8 - and so on.