Skip to content

Instantly share code, notes, and snippets.

@qntm
Last active December 8, 2021 00:32
Show Gist options
  • Save qntm/15e57796af751676afff6767a22fcf2a to your computer and use it in GitHub Desktop.
Save qntm/15e57796af751676afff6767a22fcf2a to your computer and use it in GitHub Desktop.
Determine whether a JavaScript value is a power of two (non-broken edition)
// Exports a function which determines whether a JavaScript value is a power of
// two or not. Unlike the npm package `is-power-of-two`, this actually returns
// the correct answer in all cases.
const countSetBits = i => {
// Based on <https://stackoverflow.com/a/109025/792705> but with some of the
// performance optimisations reverted for the sake of improved legibility.
i = (i & 0b01010101010101010101010101010101) + ((i & 0b10101010101010101010101010101010) >>> 1)
i = (i & 0b00110011001100110011001100110011) + ((i & 0b11001100110011001100110011001100) >>> 2)
i = (i & 0b00001111000011110000111100001111) + ((i & 0b11110000111100001111000011110000) >>> 4)
i = (i & 0b00000000111111110000000011111111) + ((i & 0b11111111000000001111111100000000) >>> 8)
i = (i & 0b00000000000000001111111111111111) + ((i & 0b11111111111111110000000000000000) >>> 16)
return i
}
module.exports = n => {
if (!Number.isFinite(n) || n <= 0) {
return false
}
// A finite, positive binary number is a power of two iff its binary
// representation has exactly one set bit.
const float64Array = new Float64Array([n])
const uint32Array = new Uint32Array(float64Array.buffer)
// 11-bit exponent
const exponent = (uint32Array[1] & 0b01111111111100000000000000000000) >> 20
// Leading bit is fixed at 1 in most cases, but 0 for subnormals
const leadBit = exponent === 0 ? 0b0 : 0b1
// most significant 20 bits of the 52-bit mantissa
const mantissaU = uint32Array[1] & 0b00000000000011111111111111111111
// least significant 32 bits of the 52-bit mantissa
const mantissaL = uint32Array[0]
// `countSetBits(leadBit)` is always equal to `leadBit` itself but whatever
return countSetBits(leadBit) + countSetBits(mantissaU) + countSetBits(mantissaL) === 1
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment