How to optimize bitwise get/set/clear of ranges of bits on 8-bit integers 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.

• Reinderien: You have written this in JavaScript, so I am tagging it JavaScript. There is nuance around possible, assumed and undefined behaviour of bit-manipulation between various languages, so a review covering one language is unlikely to cover the rest of them.
• Reinderien: It looks like your start index assumes index from left-to-right starting with the most significant non-zero bit (?) or maybe starting with the most-significant bit assuming a 16-bit word (?) Which of these is it, and is it strictly necessary? This indexing may be your performance bottleneck and indexing from the right would simplify everything, if it is possible.
• Lance Pollard: Yes if I have to change anything to improve the performance that is welcome! I didn't think of indexing from the right.
• Vogel612: "As a side-note, asking for language-agnostic feedback is treading on thin ice, and the only reason I consider this on-topic is that it has a concrete implementation in JavaScript. To clarify a few things I've asked in meta." - taken from the answer by Reinderien

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:

const 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.

• Lance Pollard: Writing the variables is outside of what my question was. Besides, I find what I did more readable than every example I've seen, such as return (n & ~((0xff << (8 - c)) >> i)) | (x << (8 - c - i)), which is definitely impenetrable.
• Lance Pollard: Wow you greatly simplified that! Thank you!
• user73941: Could I be right, if I claim that you don't need the mask in this section: ((value & mask) << startIndex of setBitRange(), so that you could simplify it to: return clearBitRange(n, startIndex, size) | (value << startIndex);
• Reinderien: It's unsafe. If you accept a size, then the implication (that you should document) is that value will be masked to size. The inverse will produce a slower function: do not accept a size, in which case you would not need to mask this but you would need to figure out the size of value. The implementation shown here could also be a feature: someone might want the explicit size-based mask.

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.

• Reinderien: Aside from the comments I wrote about this approach contrasting to use of log in my own answer - this will fall over for 64-bit numbers, or indeed anything above 32.
• potato: @Reinderien Yeah I wrote a 32 bit integer solution, but this can be modified to work with 64 bit integers too.
• potato: Though I should add to this: javascript doesn't actually support 64 bit integers. (see Number.MAX_SAFE_INTEGER)
• greybeard: This counts the number of set bits, while Lance Pollard's (and "the log approach") yield the number of indispensable bits/position of most significant 1.