如何使用 "table" 优化在 JavaScript 中反转 32 位？

Question

所以我终于想通了how to reverse 8-bits, 16-bits, and possibly 32-bits。然而，它似乎在 JavaScript 的 32 位情况下不起作用。在 JavaScript 中，您如何使用优化的基于 table 的方法做到这一点？

Table 32 位解决方案

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')}`
}

注意日志说：

0b11110010111110111100110010101011 => 0b0-101010110011000010000010110001

什么时候应该说：

0b11110010111110111100110010101011 => 0b11010101001100111101111101001111

非table 32 位解决方案（不起作用）

// 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));
}

我认为这些可能不起作用，因为移位会创建大于 32 位的数字？不确定。任何提示将不胜感激。

非table 32 位解决方案（有效）

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')}`
}

首先，为什么我的 32 位 table 解决方案不起作用？那么，如何在 32 位整数上使用 JavaScript 中的 table 方法（不使用 BigInt，并且不使用“转换为字符串和反向”技巧）来完成这项工作？

我会注意到 JavaScript 中的这个“BigInt 64”版本有效，所以是的。

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

Answer 1

问题是在您的 reverseBits32 中，有时，带符号的 32 位数字是负数！喜欢，一半时间

一种处理方法是使用 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);
}

现在您可以随心所欲地使用位操作了

您会发现其他 non-working 函数有类似的解决方案

Table 基于解决方案

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')}`
}

如何使用 "table" 优化在 JavaScript 中反转 32 位？

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

javascript

bit-manipulation

Table 32 位解决方案

非table 32 位解决方案（不起作用）

非table 32 位解决方案（有效）