How to check if number of lines in a text file is power of 2?-CodePudding

I'm making a program that would simulate something like a March Madness tournament where 64 teams were to play against each other. I've used fstream to read in the teams from the file. The problem I've having is that I must make sure that there are at least a power-of-2 teams in the file at all times or it wouldn't run properly. How would I implement a function that checks if there is the power of 2 lines?

CodePudding user response：

Check if there is exactly one bit set in the number of teams.

bool powerOfTwo = std::popcount(numberOfTeams) == 1;

CodePudding user response：

A trick with binary numbers is that if n is a power of 2, or 0, then n & (n - 1) is 0. Otherwise it's not.

i.e.

bool isPowerOfTwo(int n) {
    return (n & (n - 1)) == 0;
}

This works because:

Powers of 2 have a single 1 bit in binary and the rest of the bits are 0s.
To subtract 1 from a number in binary, you change the last 1 bit and all the bits after it.
If that was the only 1 bit in the entire number, then all the bits that didn't change were 0s. Otherwise they weren't all 0s.

Example:

    0000 0000 0010 0000 (32)
  & 0000 0000 0001 1111 (31)
  = 0000 0000 0000 0000 (0) (so 32 is a power of 2)

    0000 0000 0110 0100 (100)
  & 0000 0000 0110 0011 (99)
  = 0000 0000 0110 0000 (96) (so 100 is not a power of 2)