Polyfills for Math.clz32

Benchmark created by sjrd on

Setup

var $clz32 = Math.clz32;
  var $imul = Math.imul;
  
  function v8MathClz32BeforeIntrinsified(x) {
    if (x == 0) return 32;
    var result = 0;
    if ((x & 0xFFFF0000) === 0) { x <<= 16; result += 16; };
    if ((x & 0xFF000000) === 0) { x <<= 8;  result += 8;  };
    if ((x & 0xF0000000) === 0) { x <<= 4;  result += 4;  };
    if ((x & 0xC0000000) === 0) { x <<= 2;  result += 2;  };
    if ((x & 0x80000000) === 0) { x <<= 1;  result += 1;  };
    return result;
  }
  
  function hackersDelight(x) {
    if (x == 0) return 32;
    var result = 1;
    if ((x & 0xFFFF0000) === 0) { x <<= 16; result += 16; };
    if ((x & 0xFF000000) === 0) { x <<= 8;  result += 8;  };
    if ((x & 0xF0000000) === 0) { x <<= 4;  result += 4;  };
    if ((x & 0xC0000000) === 0) { x <<= 2;  result += 2;  };
    return result + (x >> 31);
  }
  
  /* From http://aggregate.org/MAGIC/#Leading%20Zero%20Count
   * and http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
   */
  
  function bitCountBasedClz32(x) {
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    var t1 = x - ((x >> 1) & 0x55555555);
    var t2 = (t1 & 0x33333333) + ((t1 >> 2) & 0x33333333);
    return 32 - ($imul((t2 + (t2 >> 4) & 0xF0F0F0F), 0x1010101) >> 24);
  }

Test runner

Ready to run.

Testing in
TestOps/sec
Built-in Math.clz32
var ok = (
  $clz32(0) == 32 &&
  $clz32(1) == 31 &&
  $clz32(0xffff) == 16 &&
  $clz32(-1) == 0 &&
  $clz32(0x80000000) == 0 &&
  $clz32(0x12345678) == 3);
if (!ok)
  throw Error("Incorrect implementation");
ready
V8's implementation before it was an intrinsic
var ok = (
  v8MathClz32BeforeIntrinsified(0) == 32 &&
  v8MathClz32BeforeIntrinsified(1) == 31 &&
  v8MathClz32BeforeIntrinsified(0xffff) == 16 &&
  v8MathClz32BeforeIntrinsified(-1) == 0 &&
  v8MathClz32BeforeIntrinsified(0x80000000) == 0 &&
  v8MathClz32BeforeIntrinsified(0x12345678) == 3);
if (!ok)
  throw Error("Incorrect implementation");
ready
V8 version improved with Hacker's Delight tricks
var ok = (
  hackersDelight(0) == 32 &&
  hackersDelight(1) == 31 &&
  hackersDelight(0xffff) == 16 &&
  hackersDelight(-1) == 0 &&
  hackersDelight(0x80000000) == 0 &&
  hackersDelight(0x12345678) == 3);
if (!ok)
  throw Error("Incorrect implementation");
ready
bitCount-based implementation
var ok = (
  bitCountBasedClz32(0) == 32 &&
  bitCountBasedClz32(1) == 31 &&
  bitCountBasedClz32(0xffff) == 16 &&
  bitCountBasedClz32(-1) == 0 &&
  bitCountBasedClz32(0x80000000) == 0 &&
  bitCountBasedClz32(0x12345678) == 3);
if (!ok)
  throw Error("Incorrect implementation");
ready

Revisions

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