Last active
February 25, 2023 03:37
-
-
Save Rudxain/ad3d70e52c4d392411f9f2184c7003cf to your computer and use it in GitHub Desktop.
Algorithms to count binary trailing zeros in the mathematical value of floats
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
'use strict' | |
const {trunc} = Math | |
/** mantissa bit-length of IEEE 754 "binary64" double-float */ | |
const M_LEN = 52n | |
/** | |
Bitcast. Keep in-memory bits the same, but change the type. | |
@param {number} f | |
*/ | |
const castFloatToBigInt = f => new BigUint64Array(new Float64Array([f]).buffer)[0] | |
/** | |
https://en.wikipedia.org/wiki/Find_first_set#CTZ | |
@param {number} x | |
*/ | |
const ctz32 = x => x | 0 ? 31 - Math.clz32(x & -x) : 32 | |
/** | |
CTZ using trial division by 2. | |
@param {number|bigint} n | |
*/ | |
const ctz_trial = n => { | |
const | |
B = typeof n == 'bigint', | |
ONE = B ? 1n : 1 | |
if (!B) { | |
if (!isFinite(n = trunc(n))) return NaN | |
if (!n) return 0x400 //based on `Number.MAX_VALUE` | |
} | |
if (!n) return Infinity | |
let c = ONE ^ ONE //auto-type zero | |
while ( !(n & ONE) ) {c++; n = B ? n >> 1n : trunc(n / 2)} | |
return c | |
} | |
/** | |
CTZ by type-casting (not coercion). | |
Made for performance, but it's not good practice in hi-level langs. | |
@param {number} n | |
*/ | |
const ctz_cast = n => { | |
n = trunc(n) | |
if ( !isFinite(n) ) return NaN | |
if (!n) return 0x400 | |
if (n % 2) return 0 | |
n = castFloatToBigInt(n) | |
const e = ((n >> M_LEN) & 0x3ffn) - (M_LEN - 1n) //get exponent | |
n &= ~(-1n << M_LEN) //mask mantissa | |
n = n ? ctz_trial(n) : M_LEN | |
return Number(e + n) | |
} | |
/** | |
DO NOT USE. Unless you're using a lang without bitcast | |
(eg: Llamalab Automate: https://llamalab.com/automate/community/flows/40981 ). | |
@param {number} n | |
@deprecated | |
*/ | |
const ctz_in_place = n => { | |
n = trunc(n) | |
if ( !isFinite(n) ) return NaN | |
if (!n) return 0x400 | |
const c = trunc(Math.log2(n)) - Number(M_LEN) | |
if (c > 0) n /= 2 ** c //remove all but the most significant 53b | |
//floats larger than 53b always have trailing zeros, so there's no need for `trunc` | |
return (c > 0 && c) + ctz32(n) + (n | 0 ? 0 : n >= 2 ** 32 && ctz32(n / 2 ** 32)) | |
} | |
//LICENSE: https://unlicense.org |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment