6

I am creating a simple bracket system and I need a way to check if there are a correct number of teams, OR if my program needs to compensate for bye rounds.

Right now, I am checking for "powers of two" with this function:

function validBracket(data) {
    var x = data.teams.length;
    return ((x != 0) && !(x & (x - 1)));
}

This works pretty well, but I am needing to know how many Bye rounds to add. For instance, if I had 16 teams, I would not need to add anymore teams. However, if I had 12 teams, I would need the first 4 teams to get a bye round.

How can I calculate number of bye rounds to add to my bracket? And would hard-coding an array of powers of two be better?

In pseudo code, something like this is what i was thinking of: 

if(validateBracket(data)) {
    // Valid number of teams (power of two). Keep going.
} else {
    var byeRounds = calculateByeRounds();
}

NOTE: I would rather not use an array of powers of two like below:

var powersOfTwo = [2,4,8,16,32,...];

The reasoning behind this is that I would be limiting the number of teams that could be put in the system (however, I don't think a person would have over 256 teams).

Hunter Mitchell
  • 7,063
  • 18
  • 69
  • 116
  • 2
    Calculate the next power of 2 [here](http://stackoverflow.com/questions/1322510/given-an-integer-how-do-i-find-the-next-largest-power-of-two-using-bit-twiddlin) and subtract from your current integer – Drakes Jun 14 '15 at 02:42
  • Hint: Each match eliminates one player. So a tournament of 12 players requires 11 matches. Tournaments are easy to design for powers of two, so make 12 players up to 16 by introducing 4 fictitious opponents. These are the byes. – Colonel Panic Jun 16 '15 at 10:57

2 Answers2

11
var needed = (1 << Math.ceil(Math.log2(n))) - n;

More generalized solution for extreme cases:

var needed = Math.pow(2, Math.ceil(Math.log2(n))) - n;
Patrick Roberts
  • 49,224
  • 10
  • 102
  • 153
Amadan
  • 191,408
  • 23
  • 240
  • 301
  • Very simplistic. Instead of my first function, I can check if this returns `0` then it is a perfect bracket. Thanks! – Hunter Mitchell Jun 14 '15 at 02:49
  • Not that this matters in this particular context but this binary logic has an upper boundary. This breaks if ``n > Math.pow(2, 30)``. – Patrick Roberts Jun 14 '15 at 02:56
  • @PatrickRoberts Why is this the case? Considering there will not be that many teams I assume it's ok. I would still llke to know the reasoning behind why it fails though. – Hunter Mitchell Jun 14 '15 at 02:58
  • 1
    @PatrickRoberts: True. In case OP has more than `1073741824` teams, he should substitute `(1 << ...)` with `Math.pow(2, ...)`. OP, the reason is that `1 << 31` is a negative number, and `1 << 32` is `1`, owing to `<<` being defined on the JavaScript's almost nonexistent integer type. – Amadan Jun 14 '15 at 02:59
0

const n = 2;
// Convert n to binary representation as a string and count the number of '1' characters
  
const count = n.toString(2).split('').filter(bit => bit === '1').length;
  
// Return true if there is exactly one '1' bit in the binary representation of n
 
const result = count === 1 ? `${n} is power of two` : `${n} is NOT power of two`;
 
console.log(result);
Muhammad Kashif
  • 19
  • 2