Reverse Bit Scan

Benchmark created on

Description

Ways to find the most significant bit inside a bigint.

Setup

function loop(a) {
	const one = BigInt(1);
	let position = -1;

	while (a > 0) {
		a = (a >> one);
		position++;
	}

	return position;
}

function clz1(a) {
	let offset = 0;
	for (; (a & ~BigInt(0xFFFFFFFF)) > 0; a >>= BigInt(32)) {
		offset += 32;
	}
	return offset + (31 - Math.clz32(Number(a)));
}

function clz2(a) {
	const MASK = ~BigInt(0xFFFFFFFF);
	const SHIFT = BigInt(32);
	let offset = 0;
	for (; (a & MASK) > 0; a >>= SHIFT) {
		offset += 32;
	}
	return offset + (31 - Math.clz32(Number(a)));
}

function clz3(a) {
	const MASK = ~0xFFFFFFFFn;
	let offset = 0;
	for (; (a & MASK) > 0; a >>= 32n) {
		offset += 32;
	}
	return offset + (31 - Math.clz32(Number(a)));
}

Test runner

Ready to run.

Testing in
TestOps/sec
Loop
let NO_OPTIMIZE = 0;
for (let i = 0; i < 10000; i++)
	NO_OPTIMIZE += loop(BigInt(i) * BigInt(i));

console.log(NO_OPTIMIZE);
ready
CLZ
let NO_OPTIMIZE = 0;
for (let i = 0; i < 10000; i++)
	NO_OPTIMIZE += clz1(BigInt(i) * BigInt(i));

console.log(NO_OPTIMIZE);
ready
CLZ w/ Const
let NO_OPTIMIZE = 0;
for (let i = 0; i < 10000; i++)
	NO_OPTIMIZE += clz2(BigInt(i) * BigInt(i));

console.log(NO_OPTIMIZE);
ready
CLZ w/ Const & Literal
let NO_OPTIMIZE = 0;
for (let i = 0; i < 10000; i++)
	NO_OPTIMIZE += clz3(BigInt(i) * BigInt(i));

console.log(NO_OPTIMIZE);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.