How to optimize bitwise get/set/clear of ranges of bits in JavaScript?

Question

I have been working for a few days on writing get, set, and clear bitwise functions in JavaScript to clear not individual bits from an integer n, but to clear entire ranges of bits in n.

For example, using the functions below, I would expect this behavior:

getNumBits(0b101) // 3
getNumBits(0b10100000) // 8

// getBitRange(integer, startIndex, size)
getBitRange(0b101110010001111, 1, 4) // 1110
getBitRange(0b101110010001111, 5, 7) // 1

// setBitRange(integer, startIndex, value)
setBitRange(0b101110010001111, 5, 0b1001) // 0b101111001001111

// clearBitRange(integer, startIndex, size)
clearBitRange(0b101110010001111, 5, 5) // 0b101110000001111
clearBitRange(0b101110010001111, 2, 3) // 0b100000000001111

How can I optimize these functions by removing or reordering any of the operations? Can we cut out any steps? I did my best to figure out how to just barely implement the function, but I am no master at bit operations yet. Wondering if one could rewrite these 4 functions to make them more optimal. Please keep each instruction on its own line so it's easier to see :)

function getNumBits(n) {
  let i = 0
  while (n) {
    i++
    n >>= 1
  }
  return i
}

function getBitRange(n, l, s) {
  let r = 8 - l - s
  let p = 1 << p
  let o = p - 1
  let ol = o << r
  let or = o >> l
  let om = or & ol
  let x = n & om
  return x >> r
}

function setBitRange(n, i, x) {
  let o = 0xff // 0b11111111
  let c = getNumBits(x)
  let j = 8 - i // right side start
  let k = j - c // right side remaining
  let h = c + i
  let a = x << k // set bits
  let b = a ^ o // set bits flip
  let d = o >> h // mask right
  let q = d ^ b //
  let m = o >> j // mask left
  let s = m << j
  let t = s ^ q // clear bits!
  let w = n | a // set the set bits
  let z = w & ~t // perform some magic https://stackoverflow.com/q/8965521/169992
  return z
}

function clearBitRange(n, i, c) {
  let s = i + c
  let r = 8 - s
  let p = 1 << 8
  let o = p - 1
  let j = o >> i
  let k = o << r
  let h = j & k
  let g = ~h
  let z = n & g
  return z
}

This is only concerned with 8-bit numbers.

Answer 1

• For any of the following suggestions, please do profile them to test the performance difference. Performance is likely to vary across multiple browser implementations of the JavaScript interpretation engine.
• Rather than a loop for getNumBits, try Math.floor(Math.log(n)/LN_2) - or maybe trunc instead of floor - where LN_2 is precomputed as Math.log(2).
• Try to avoid single-letter variables. Your functions are very impenetrable and will be neither legible nor maintainable by anyone else, or by you in a few weeks. In other words, you should not be a human minifier.
• Rewrite your code to assume that the index is zero-based starting from the least-significant bit and going left. This will greatly simplify your code and will obviate calls to getNumBits.

Example implementations:

LN_2 = Math.log(2);

function getNumBits(n) {
    return Math.trunc(Math.log(n) / LN_2) + 1;
}

function getBitRange(n, startIndex, size) {
    return (n >> startIndex) & ((1 << size) - 1);
} 

function setBitRange(n, startIndex, size, value) {
    const mask = (1 << size) - 1;
    return (
        n & ~(mask << startIndex)
    ) | ((value & mask) << startIndex);
}

function clearBitRange(n, startIndex, size) {
    const mask = (1 << size) - 1;
    return n & ~(mask << startIndex);
}

A comment about getNumBits and the alternate implementation offered by @potato. That one is indeed faster than calls to log; a local test of mine using Node and 10,000,000 iterations indicates by a factor of about 16. But that needs to be taken with a grain of salt.

If you're (for some reason) doing a massive amount of client-side data processing and needing to call this function many thousands of times, it might be justified (with HEAVY commenting) to use the bit-twiddle method. In all other cases, I don't recommend using something that's so obscure and difficult-to-understand.

Answer 2

There is a more efficient way to implement getNumBits (compared to @Reinderien's answer), if you use some bitwise magic:

function getNumBits(x){
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  x -= (x >> 1) & 0x55555555;
  x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
  return (((x >> 4) + x) & 0x0f0f0f0f) * 0x01010101 >> 24;
}

The first part (the |= operations) overlay the number with it's own bit shifts in order to turn all the bits into 1-bits except the bits to the left of the left-most 1-bit. Then the second part counts these 1-bits using this algorithm.

If you know that the number of bits is going to have an upper limit in some specific cases, then you can write even shorter functions to use in these cases. All you need is to understand how this bit count algorithm works.