5
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Jul 5, 2020 at 12:55
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Jul 5, 2020 at 12:58
  • \$\begingroup\$ Yes if I have to change anything to improve the performance that is welcome! I didn't think of indexing from the right. \$\endgroup\$ Commented Jul 5, 2020 at 15:20
  • 5
    \$\begingroup\$ "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 \$\endgroup\$ Commented Jul 5, 2020 at 16:45

2 Answers 2

Reset to default
8
\$\begingroup\$
  • 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.

\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jul 5, 2020 at 17:30
  • \$\begingroup\$ Wow you greatly simplified that! Thank you! \$\endgroup\$ Commented Jul 5, 2020 at 17:53
  • \$\begingroup\$ 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); \$\endgroup\$ Commented Jul 5, 2020 at 18:35
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jul 5, 2020 at 18:37
3
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jul 5, 2020 at 22:36
  • \$\begingroup\$ @Reinderien Yeah I wrote a 32 bit integer solution, but this can be modified to work with 64 bit integers too. \$\endgroup\$ Commented Jul 6, 2020 at 7:36
  • \$\begingroup\$ Though I should add to this: javascript doesn't actually support 64 bit integers. (see Number.MAX_SAFE_INTEGER) \$\endgroup\$ Commented Jul 6, 2020 at 8:11
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jan 11, 2021 at 12:27

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.