1
\$\begingroup\$

I have gathered from around the web a few functions and such to land on this:

const LEADING_ZERO_BIT_TABLE = makeLeadingZeroTable()

function makeLeadingZeroTable() {
  let i = 0
  const table = new Uint8Array(256)
  while (i < 256) {
    let count = 8
    let index = i
    while (index > 0) {
      index = (index / 2) | 0
      count--
    }
    table[i] = count
    i++
  }
  return table
}
// https://cs-fundamentals.com/tech-interview/c/c-program-to-count-number-of-ones-in-unsigned-integer


function clz1(n)
{
  let accum = 0;

  accum += LEADING_ZERO_BIT_TABLE[n >> 24];
  accum += (accum == 8 ) ? LEADING_ZERO_BIT_TABLE[(n >> 16) & 0xFF] : 0;
  accum += (accum == 16) ? LEADING_ZERO_BIT_TABLE[(n >>  8) & 0xFF] : 0;
  accum += (accum == 24) ? LEADING_ZERO_BIT_TABLE[ n        & 0xFF] : 0;

  return accum;
}


function clz2(n)
{
  let accum = LEADING_ZERO_BIT_TABLE[n >> 24];

  if (accum === 8) {
    accum += LEADING_ZERO_BIT_TABLE[(n >> 16) & 0xFF]
  }
  if (accum === 16) {
    accum += LEADING_ZERO_BIT_TABLE[(n >>  8) & 0xFF]
  }
  if (accum === 24) {
    accum += LEADING_ZERO_BIT_TABLE[ n        & 0xFF]
  }

  return accum;
}

console.log('clz1', clz1(0b00100010001000100010001000100010))
console.log('clz1', clz1(0b00000010001000100010001000100010))

console.log('clz2', clz2(0b00100010001000100010001000100010))
console.log('clz2', clz2(0b00000010001000100010001000100010))

How do I transform clz2 so it has the same output as clz1, but it does it in a more optimal way? I feel like the += can be optimized away somehow? Is there a way to remove the conditional branching? Or is this as good as it's going to get?

P.S. I know about the clz32 and other related builtins, just doing this out of curiosity and for a custom programming language.

I basically have this as of now, but would like to get rid of the conditional branching if possible.

function countLeadingZeroes32JS(n)
{
  let accum = LEADING_ZERO_BIT_TABLE[n >>> 24];

  if (accum === 8) {
    accum += LEADING_ZERO_BIT_TABLE[(n >>> 16)]
  }

  if (accum === 16) {
    accum += LEADING_ZERO_BIT_TABLE[(n >>>  8)]
  }

  if (accum === 24) {
    accum += LEADING_ZERO_BIT_TABLE[ n       ]
  }

  return accum;
}
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

What about using a hashmap instead? Have tested this with the given code and it looks like it works

const clz = new Map();

// Store a function in the hashmap, that performs the lookup
clz.set(8,  n => LEADING_ZERO_BIT_TABLE[ (n >> 16) & 0xFF]);
clz.set(16, n => LEADING_ZERO_BIT_TABLE[ (n >>  8) & 0xFF]);
clz.set(24, n => LEADING_ZERO_BIT_TABLE[ n & 0xFF]);

function clz3(n) {
    let accum = LEADING_ZERO_BIT_TABLE[n >> 24];

    // Without this, an error in the map lookup will crash this prog
    // might be worth revisiting error handling strategy... 
    try {
        // immediately invoke the expression stored inside the clz map, 
        // passing in 'n'
        accum += clz.get(accum)(n);
    } catch (e) {}

    return accum;
}
```
\$\endgroup\$
3
  • \$\begingroup\$ If this does work, a map will incur more processor steps (internally) than an if statement I think, was hoping for more bit-manipulation tricks if possible. But this is interesting, thank you. \$\endgroup\$
    – Lance
    Commented Apr 20, 2022 at 13:15
  • \$\begingroup\$ I can't speak to the validity of that to be honest.. Another alternative I can suggest would be a switch statement. With a switch in lower level languages, a switch is usually better optimised by the compiler. I don't know enough about the internals of V8 to comment on whether the same is true for JS... food for thought :) \$\endgroup\$ Commented Apr 20, 2022 at 13:23
  • \$\begingroup\$ okay, on a bit of reading- the performance gain is likely negligible... a bit twiddling solution would certainly give you more here \$\endgroup\$ Commented Apr 20, 2022 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.