How to reverse 32-bits in JavaScript using the "table" optimization?

Question

So I finally figured out how to reverse 8-bits, 16-bits, and possibly 32-bits. However it doesn't appear to work in the 32-bit case in JavaScript. How do you do this in JavaScript using an optimized table-based approach?

Table Solution in 32 Bits

const BIT_REVERSAL_TABLE = new Array(256)

for (var i = 0; i < 256; ++i) {
  var v = i, r = i, s = 7;
  for (v >>>= 1; v; v >>>= 1) {
    r <<= 1;
    r |= v & 1;
    --s;
  }
  BIT_REVERSAL_TABLE[i] = (r << s) & 0xff;
}

function reverseBits32(n) {
  return (BIT_REVERSAL_TABLE[n & 0xff] << 24) |
    (BIT_REVERSAL_TABLE[(n >>> 8)  & 0xff] << 16) |
    (BIT_REVERSAL_TABLE[(n >>> 16) & 0xff] << 8) |
    BIT_REVERSAL_TABLE[(n >>> 24) & 0xff];
}

log32(0b11110010111110111100110010101011)

function log32(n) {
  console.log(`${bits(n, 32)} => ${bits(reverseBits32(n), 32)}`)
}

function bits(n, size) {
  return `0b${n.toString(2).padStart(size, '0')}`
}

Notice the logs are saying:

0b11110010111110111100110010101011 => 0b0-101010110011000010000010110001

When it should say:

0b11110010111110111100110010101011 => 0b11010101001100111101111101001111

Non-table Solutions in 32 Bits (that don't work)

// brev_knuth
function reverseBits32(a) {
  let t
  a = (a << 15) | (a >> 17);
  t = (a ^ (a >> 10)) & 0x003f801f;
  a = (t + (t << 10)) ^ a;
  t = (a ^ (a >>  4)) & 0x0e038421;
  a = (t + (t <<  4)) ^ a;
  t = (a ^ (a >>  2)) & 0x22488842;
  a = (t + (t <<  2)) ^ a;
  return a;
}

function reverseBits32(x) {
  x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
  x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
  x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
  x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
  return((x >> 16) | (x << 16));
}

I think these probably don't work because the bit-shifting creates a larger than 32-bit number? Not sure. Any hints would be appreciated.

Non-table Solution in 32 Bits (that works)

function reverseBits32(n) {
  let res = 0;
  for (let i = 0; i < 32; i++) {
    res = (res << 1) + (n & 1);
    n = n >>> 1;
  }

  return res >>> 0;
}

log32(0b11110010111110111100110010101011)

function log32(n) {
  console.log(`${bits(n, 32)} => ${bits(reverseBits32(n), 32)}`)
}

function bits(n, size) {
  return `0b${n.toString(2).padStart(size, '0')}`
}

First, why doesn't my 32-bit table solution work? Then, how can you make this work using the table approach in JavaScript (without using BigInt, and without using "convert to string and reverse" hacks) on a 32-bit integer?

I will note that this "BigInt 64" version in JavaScript works, so yay.

function reverseBits64(n) {
  return  (BigInt(BIT_REVERSAL_TABLE[Number(n & 255n)]) << 56n) |
    (BigInt(BIT_REVERSAL_TABLE[Number((n >> 8n) & 255n)]) << 48n) |
    (BigInt(BIT_REVERSAL_TABLE[Number((n >> 16n) & 255n)]) << 40n) |
    (BigInt(BIT_REVERSAL_TABLE[Number((n >> 24n) & 255n)]) << 32n) |
    (BigInt(BIT_REVERSAL_TABLE[Number((n >> 32n) & 255n)]) << 24n) |
    (BigInt(BIT_REVERSAL_TABLE[Number((n >> 40n) & 255n)]) << 16n) |
    (BigInt(BIT_REVERSAL_TABLE[Number((n >> 48n) & 255n)]) << 8n) |
    BigInt(BIT_REVERSAL_TABLE[Number((n >> 56n) & 255n)]);
}

// 0b1111001011111011110011001010101111110010111110111100110010101011 =>
// 0b1101010100110011110111110100111111010101001100111101111101001111

you could of course `x.toString(2).padStart(32, '0').split('').reverse().join('')` where `x` is just the original number — Bravo, Apr 20 '22 at 05:33
Yeah I want to do it with bit manipulation tricks or tables, in this case a table. No string hacks. — Lance, Apr 20 '22 at 05:33
Well in my particular case, I want a general "bit-manipulation/table" solution so I can apply it to many regular and custom programming languages. So using a quirk of JavaScript is less than ideal :) plus it is a hack in this case haha. — Lance, Apr 20 '22 at 05:35
the easiest way in javascript is BigInt's ... because the 32bit numbers javascript use in bit manipulation are signed (not so with BigInt) - there's other ways to fix it, but it makes the code really messy for javascript — Bravo, Apr 20 '22 at 05:50
I would like to see the table-based solution specifically, I see how it can work with BigInt but this question is focused on the table-based approach. Why does it go negative in (half) the cases? How do you prevent this in a table-based solution? — Lance, Apr 20 '22 at 06:13

Bravo · Accepted Answer · 2022-04-20T06:19:13.297

The issue is that in your reverseBits32, sometimes, a signed 32 bit number is negative! like, half the time

One way to deal with it is using BigInt

const reverseBits32= (x) => {
    x = BigInt(x);
    x = (((x & 0xaaaaaaaan) >> 1n) | ((x & 0x55555555n) << 1n));
    x = (((x & 0xccccccccn) >> 2n) | ((x & 0x33333333n) << 2n));
    x = (((x & 0xf0f0f0f0n) >> 4n) | ((x & 0x0f0f0f0fn) << 4n));
    x = (((x & 0xff00ff00n) >> 8n) | ((x & 0x00ff00ffn) << 8n));
    x = ((x >> 16n) | (x << 16n)) & 0xffffffffn;
    return Number(x);
}

Now you're using bit manipulation as you wanted

You'll find there's a similar solution to the other non-working functions

Table based solution

const BIT_REVERSAL_TABLE = new Array(256)

for (var i = 0; i < 256; ++i) {
  var v = i, r = i, s = 7;
  for (v >>>= 1; v; v >>>= 1) {
    r <<= 1;
    r |= v & 1;
    --s;
  }
  BIT_REVERSAL_TABLE[i] = (r << s) & 0xff;
}

function reverseBits32(n) {
  return (BIT_REVERSAL_TABLE[n & 0xff] * 2**24) +
    (BIT_REVERSAL_TABLE[(n >>> 8)  & 0xff] * 2 **16) +
    (BIT_REVERSAL_TABLE[(n >>> 16) & 0xff] * 2 **8) +
    BIT_REVERSAL_TABLE[(n >>> 24) & 0xff];
}

log32(0b11110010111110111100110010101011)

function log32(n) {
  console.log(`${bits(n, 32)} => ${bits(reverseBits32(n), 32)}`)
}

function bits(n, size) {
  return `0b${n.toString(2).padStart(size, '0')}`
}

Awesome, I figured out the BigInt solution just now (and updated the question with it) just before I saw your post. But cool. However, is there no way to use a table to accomplish this in 32-bits with JavaScript? — Lance, Apr 20 '22 at 05:51
I really HATE table lookups - there probably is, but I won't touch it :p seriously ... 24 math operations to reverse 32 bits is good economy :D that would probably translate to about 30 CPU instructions (though, maybe not with javascript of course) — Bravo, Apr 20 '22 at 05:54
@Lance - table solution just for you :p perfectly safe since Number in javascript is integer safe up to 2**53 - 1 — Bravo, Apr 20 '22 at 06:19
[Here](https://stackoverflow.com/questions/71898951/how-to-find-trailing-leading-ones-zeroes-for-8-bit-16-bit-and-32-bit-integers) is my last quest to figure out `countLeadingZeroes[8/16/32]` and `countLeadingOnes[8/16/32]` in JavaScript using a similar table-based approach. — Lance, Apr 20 '22 at 07:03

How to reverse 32-bits in JavaScript using the "table" optimization?

Table Solution in 32 Bits

Non-table Solutions in 32 Bits (that don't work)

Non-table Solution in 32 Bits (that works)

1 Answers1