3

Given that the language is javascript, and that the input is < 1073741824, what's the fastest way to obtain the equivalent to:

Math.floor(Math.log(len) / Math.log(32))

I've tried with an if:

if (len < 1024) return 1;
if (len < 32768) return 2;
if (len < 1048576) return 3;
if (len < 33554432) return 4;
if (len < 1073741824) return 5;

and with bitwise operators:

// 0000000000000000000000000100000 // 32
// 0000000000000000000010000000000 // 1024
// 0000000000000001000000000000000 // 32768
// 0000000000100000000000000000000 // 1048576
// 0000010000000000000000000000000 // 33554432
// 1000000000000000000000000000000 // 1073741824
function log32(len) {
    return (
        0 + 
        !!(len >>> 30) + 
        !!(len >>> 25) + 
        !!(len >>> 20) + 
        !!(len >>> 15) + 
        !!(len >>> 10) +
        !!(len >>> 5
    )
}

is there a way to do this cleaner or with less ops? (performance measured with: https://jsperf.com/log32-perf/)

BenG
  • 1,756
  • 15
  • 17
  • 1
    What about [bit twiddling hack](https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog)? – Gonras Karols Apr 19 '17 at 20:14
  • What do you consider to be wrong with your `if` cascade approach? I can't imagine a *faster* way, or a way with fewer ops, even if it looks hacky or mathematically inelegant. (BTW given your initial assumption, that the input is always less than 1073741824, you don't even need the final comparison operation and `if` conditional—just `return 5;` would do it.) – jez Apr 19 '17 at 20:24

1 Answers1

4

I would go for the very efficient Math.clz32 method, which returns the number of leading zero bits in the 32-bit binary representation of a number.

const log32 = x => Math.floor((31 - Math.clz32(x))/5);

console.log(log32(1023)); // 1
console.log(log32(1024)); // 2

This will return the correct value for any x > 0 within the 32-bit range.

trincot
  • 317,000
  • 35
  • 244
  • 286
  • 1
    Nice +one; better than log2(). Btw you can replace `/5` with `*0.2` which is generally faster. – Matt Apr 19 '17 at 20:42
  • impressive +1. if we trade Math.floor for result | 0 we can shave another hair., which then measures faster than my if – BenG Apr 19 '17 at 21:06
  • 1
    In FF I don't get any significant improvement with `*0.2`, nor with `|0`: either solution comes out fastest about 50% of the time. – trincot Apr 19 '17 at 21:23