如何左旋转整数位

Question

我需要在 Ruby 中将整数的 32 位左旋转n。我正在尝试规范实现：

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

使用大数字时出现问题：结果溢出 32 位。我想这是因为 Ruby 中整数的理论大小不受限制。

如何做到不溢出？

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 位数字。这也是一个整数。

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