JavaScript中BigInt如何实现无符号右移？

Question

我尝试了 this 种实现方式，但它似乎不起作用。

function urs32(n, amount) {
  const mask = (1 << (32 - amount)) - 1
  return (n >> amount) & mask
}

function flip32(n) {
  const mask = (1 << 32) - 1
  return ~n & mask
}

log(~0b10101010 >>> 0, urs32(~0b10101010, 0))
log(~0b10101010 >>> 0, flip32(0b10101010))

function log(a, b) {
  console.log(a.toString(2), b.toString(2))
}

我希望 a 在这两种情况下都等于 b，如果做得对的话。基本上我正在尝试 flip 32 位（所以 1 变成 0，0 变成 1）。我看到了 1 << 32 === 0，所以为了得到值，我做了 2 ** 32，但仍然不起作用。

如何在 BigInt 上实现 ~n >>> 0 的等价物？

基本上我想做的是创建 countLeadingOnes 函数（在 countLeadingZeroes 函数之外），像这样：

const LEADING_ZERO_BIT_TABLE = makeLeadingZeroTable()

function makeLeadingZeroTable() {
  let i = 0
  const table = new Uint8Array(256).fill(0)
  while (i < 256) {
    let count = 8
    let index = i
    while (index > 0) {
      index = (index / 2) | 0
      count--
    }
    table[i] = count
    i++
  }
  return table
}

function countLeadingZeroes32JS(n)
{
  let accum = LEADING_ZERO_BIT_TABLE[n >>> 24];

  if (accum === 8) {
    accum += LEADING_ZERO_BIT_TABLE[(n >>> 16)]
  }
  if (accum === 16) {
    accum += LEADING_ZERO_BIT_TABLE[(n >>>  8)]
  }
  if (accum === 24) {
    accum += LEADING_ZERO_BIT_TABLE[ n       ]
  }

  return accum;
}

function countLeadingZeroes16JS(n)
{
  let accum = LEADING_ZERO_BIT_TABLE[n >>> 8]

  if (accum === 8) {
    accum += LEADING_ZERO_BIT_TABLE[n]
  }

  return accum;
}

function countLeadingZeroes8JS(n)
{
  return LEADING_ZERO_BIT_TABLE[n]
}

console.log('countLeadingZeroes32JS', countLeadingZeroes32JS(0b10100010001000100010001000100010))
console.log('countLeadingZeroes32JS', countLeadingZeroes32JS(0b00100010001000100010001000100010))
console.log('countLeadingZeroes32JS', countLeadingZeroes32JS(0b00000010001000100010001000100010))
console.log('countLeadingZeroes16JS', countLeadingZeroes16JS(0b1010001000100010))
console.log('countLeadingZeroes16JS', countLeadingZeroes16JS(0b0010001000100010))
console.log('countLeadingZeroes16JS', countLeadingZeroes16JS(0b0000001000100010))
console.log('countLeadingZeroes16JS', countLeadingZeroes16JS(0b0000000000100010))
console.log('countLeadingZeroes8JS', countLeadingZeroes8JS(0b10100010))
console.log('countLeadingZeroes8JS', countLeadingZeroes8JS(0b00100010))
console.log('countLeadingZeroes8JS', countLeadingZeroes8JS(0b00000010))

function countLeadingOnes32JS(n) {
  return countLeadingZeroes32JS(~n >>> 0)
}

function countLeadingOnes16JS(n) {
  return countLeadingZeroes16JS(~n >>> 0)
}

function countLeadingOnes8JS(n) {
  return countLeadingZeroes8JS(~n >>> 0)
}

console.log('countLeadingOnes32JS', countLeadingZeroes32JS(0b00100010001000100010001000100010))
console.log('countLeadingOnes32JS', countLeadingZeroes32JS(0b11100010001000100010001000100010))
console.log('countLeadingOnes32JS', countLeadingZeroes32JS(0b11111100001000100010001000100010))
console.log('countLeadingOnes16JS', countLeadingOnes16JS(0b0100001000100010))
console.log('countLeadingOnes16JS', countLeadingOnes16JS(0b1111110000100010))
console.log('countLeadingOnes16JS', countLeadingOnes16JS(0b1111111111000010))
console.log('countLeadingOnes8JS', countLeadingOnes8JS(0b01000010))
console.log('countLeadingOnes8JS', countLeadingOnes8JS(0b11000010))
console.log('countLeadingOnes8JS', countLeadingOnes8JS(0b11111100))

但是 ~n >>> 0 似乎不适用于 32 位整数。如何让它正常工作？

Answer 1

How to implement unsigned right shift for BigInt in JavaScript?

无符号 right-shift 很难为 arbitrary-size 整数定义有意义的，所以在你（或任何人）可以实现它之前，你必须决定你希望它如何表现。
也就是说，考虑到这个问题的其余部分，我不明白你为什么需要这个。

I would expect for a to equal b in both cases

为什么会这样？无符号 right-shift 和位翻转是不同的操作，产生不同的结果。

I see that 1 << 32 === 0

不，1 << 32 === 1。 JavaScript（如 x86 CPU）对移位量执行隐式 &31，因此由于 32 & 31 === 0，... << 32 与 ... << 0.[=45= 相同]

How do you implement the equivalent of ~n >>> 0 on a BigInt?

~n 等价于 ~n。（这不是打字错误。实际上是同一件事。）
... >>> 0 等价于 BigInt.asUintN(32, ...)。（请注意，Number 版本和 BigInt 版本都不会改变任何内容，因此这不会回答您的标题问题“如何为 BigInt 实现 USR”。）

it appears that ~n >>> 0 doesn't work on 32-bit integers.

确实有效。事实上，它仅适用于 32 位整数。

>>> 0 部分完全没有必要，您可以将其删除。
这条线的原因：

console.log('countLeadingOnes32JS', countLeadingZeroes32JS(0b00100010001000100010001000100010))

没有产生前导数是因为它调用的函数是 ...Zeroes...；一个明显的 copy-paste 错误。
countLeadingOnes16JS 不能正常工作的原因是因为 JavaScript 中的 ~ 总是翻转 32 位。由于 16 位数字的 32 位表示有（至少）16 个前导零，因此翻转后它们都变成了 1，并且 countLeadingZeroes16JS 得到的输入远远大于它可以处理的输入：LEADING_ZERO_BIT_TABLE[n >>> 8] 查找table 中不存在的元素，因为在这种情况下 n >>> 8 的结果是 24 位数字，而不是 8 位数字。解决方法是翻转后使用遮罩； clo16 的有效实现可能是：

function countLeadingOnes16(n) {
  return countLeadingZeroes16(~n & 0xFFFF);
}

不需要 BigInts，也不需要 >>> 0。
countLeadingOnes8 类似。

您可能需要阅读 https://en.wikipedia.org/wiki/Two%27s_complement（或该概念的其他描述）以了解负数的按位运算是怎么回事。

您可能还想了解如何调试自己的代码。有多种技巧：例如，您可以：

为中间结果插入 console.log 个语句，
或在调试器中逐步执行，
或者只是在控制台中评估小片段，

其中任何一个都可以让您很容易地看到从输入数字到最终结果的路径上发生了什么。

对于阅读本文的任何其他人：Math.clz32 非常高效，因为它被编译为机器指令，因此手动实现 countLeadingZeros 是不必要且浪费的。对于较小的宽度，只需减去：function clz8(n) { return Math.clz32(n) - 24; }

JavaScript中BigInt如何实现无符号右移？

How to implement unsigned right shift for BigInt in JavaScript?

javascript

bit-manipulation

bit-shift

bigint