尺寸大于2147483647的BooleanArray

Question

我正试图在科特林实现阿特金的筛子。我希望它支持最多2^32-1的数字，所以筛子必须是一个UInt-indexed数组。

我试着像这样初始化筛子：

var sieve = BooleanArray(limit + 1u)

然后，我得到了错误：

error: type mismatch: inferred type is UInt but Int was expected

那么，是否有任何方法可以使BooleanArray (或等效)存储至少有4294967295个值？

Answer 1

最容易的方法可能是使用UInt作为大小，然后在内部映射2种常见的BooleanArray，后者使用Int进行寻址，尽管从来不可能有负的索引值(这似乎是设计上的错误--或者至少缺少优化)。这意味着，我们还可以使用签名的Int来解决所有问题。我的意思是，在内部将负值映射到一个BooleanArray，将正值映射到另一个BooleanArray。实际的问题似乎是，正在传递一个签名的Int，但是只能使用正的范围(50%)来处理数据。我们可以使用absoluteValue，因为在哪个方向填充数组并不重要。