Skip to content

Instantly share code, notes, and snippets.

@dminkovsky
Last active December 19, 2015 22:19
Show Gist options
  • Save dminkovsky/6026582 to your computer and use it in GitHub Desktop.
Save dminkovsky/6026582 to your computer and use it in GitHub Desktop.
Round up to the next power of 2!
# Observations about binary and binary operations:
* Bitshifting by 1 either adds or subtracts a multiple of 2 from each factor of 2.
** Take, for example, the number 10 (decimal)
** 10 = 8 + 2 = 1*(2^3) + 0*(2^2) + 1*(2^1) + 0*(2^0), or 1010 in binary.
** If you shift each of these bits to the left by 1, you get 10100.
** This took each of the 1 bits (multiples of 2) in the binary representation and multplied each by 2:
*** 10100 is 1*(2^4) + 0*(2^3) + 1*(2^2) + 0*(2^1) + 0*(2^0) = 16 + 0 + 4 + 0 + 0 = 20.
*** Notice that 20 = 16 + 4 = 2*8 + 2*2 = 2*(8 + 2).
* | (OR) always produces a number greater or equal to its operands.
* Powers of 2 in binary are represented by numbers that are all 0s except a single 1.
* An example of the algo below:
n = 910 == 11,1000,1110 in binary.
0011,1000,1110 (subtract 1 from 910)
0011,1000,1101 (shift 1 to the right)
0001,1100,0110 (OR)
0011,1100,1111 (shift 4 to the right)
0000,0011,1100 (OR)
0011,1111,1111 (no need to continue; add 1)
0100,0000,0000 == 1024!
A lot more here!!
* http://stackoverflow.com/questions/364985/algorithm-for-finding-the-smallest-power-of-two-thats-greater-or-equal-to-a-giv
* http://stackoverflow.com/questions/466204/rounding-off-to-nearest-power-of-2
* http://graphics.stanford.edu/~seander/bithacks.html
// From https://github.com/joyent/node/blob/0882a7506394e07ae6564ccf3db401b8fb7f7071/lib/_stream_readable.js
// j << k shifts the bitwise representation of j to the left k times.
// j <<= k is equivalent to j = j << k
function roundUpToNextPowerOf2(n) {
if (n >= MAX_HWM) {
n = MAX_HWM;
} else {
// Get the next highest power of 2
n--;
for (var p = 1; p < 32; p <<= 1) n |= n >> p;
n++;
}
return n;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment