如何左旋转整数的位

Question

我需要在 Ruby 中将整数的 32 位左循环 n。我正在尝试规范实施：

class Integer
    def rotl32 n
        return (self << n) | (self >> (32 - n))
    end
end

使用大数时出现问题：结果溢出 32 位。我猜这是因为 Ruby.

中 Integer 的理论上无限大小

如何做到不溢出？

Answer 1

Ruby 将自动切换到不同的内部表示以适应更大的数字，因此您需要用掩码来限制它：

class Integer
  def rotl32(n)
    mask = (1 << (32 - n)) - 1

    ((self & mask) << n) | (self >> (32 - n))
  end
end

其中 mask 指示哪些位应左移，其余位在移位前有效地修剪掉。

Ruby 会很乐意做一些非常荒谬的事情，比如 1 << (1 << 16) 会产生一个 19,729 位长的数字。这也是一个整数。

请注意，如果您需要此方法的性能更高，您会希望使用查找 table 而不是每次都进行计算，尽管我一如既往地进行基准测试以确保该方法更快。

How to left rotate bits of an Integer