Skip to content

Instantly share code, notes, and snippets.

@Rudxain
Last active February 25, 2023 03:37
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Rudxain/ad3d70e52c4d392411f9f2184c7003cf to your computer and use it in GitHub Desktop.
Save Rudxain/ad3d70e52c4d392411f9f2184c7003cf to your computer and use it in GitHub Desktop.
Algorithms to count binary trailing zeros in the mathematical value of floats
'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