如何在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

。基本上我试图翻转 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

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

无符号右移很难对任意大小的整数进行有意义的定义，因此在您（或任何人）可以实现它之前，您必须决定您希望它如何表现。
也就是说，考虑到这个问题的其余部分，我不明白为什么你甚至需要这个。

我希望在这两种情况下

a

等于

b

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

我看到了

1 << 32 === 0

不，

1 << 32 === 1

。 JavaScript（如 x86 CPU）对移位量执行隐式

&31

，因此由于

32 & 31 === 0

，

... << 32

与

... << 0

相同。

如何在 BigInt 上实现

~n >>> 0

的等效功能？

~n

的等价物是

~n

。 （这不是拼写错误。这实际上是同一件事。）

... >>> 0

的等价物是

BigInt.asUintN(32, ...)

。 （请注意，Number 版本和 BigInt 版本都不会改变任何内容，因此这并不能回答您的标题问题“如何为 BigInt 实现 USR”。）

看起来

~n >>> 0

不适用于 32 位整数。

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

>>> 0

部分完全没有必要，你可以把它扔掉。
这条线的原因：

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

不产生前导的数量是因为它调用的函数是

...Zeroes...

；明显的复制粘贴错误。

countLeadingOnes16JS

无法正常工作的原因是 JavaScript 中的

~

始终翻转 32 位。由于 16 位数字的 32 位表示有（至少）16 个前导零，因此翻转后这些都变成了 1，并且

countLeadingZeroes16JS

得到的输入远远大于它可以处理的输入：

LEADING_ZERO_BIT_TABLE[n >>> 8]

查找一个不存在的元素表中不存在，因为在本例中

n >>> 8

的结果是 24 位数字，而不是 8 位数字。解决办法是翻转后使用面膜； clo16 的有效实现可能是：

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

不需要 BigInt，也不需要

>>> 0

。

countLeadingOnes8

类似。

---

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

您可能还想学习如何调试自己的代码。有一系列技术：例如，您可以：

• 插入了

  console.log

  中间结果语句，
• 或在调试器中单步执行，
• 或者只是在控制台中评估小片段，

其中任何一个都可以让您轻松查看从输入数字到最终结果的路径上发生的情况。

---

对于阅读本文的其他人：有

Math.clz32

，它非常高效，因为它被编译为机器指令，因此手动实现

countLeadingZeros

是不必要且浪费的。对于较小的宽度，只需减去：

function clz8(n) { return Math.clz32(n) - 24; }

Answer 2

Here 是 64 位整数（Java Long）的愚蠢实现。请注意，当右移位大于 64 时，它不会处理极端情况。

它用作 demo，生成与 Java 相同的 UUID 字符串。