java - 从 40 亿中找出缺失的数字(再次)

Question

似乎一个被问过很多次的问题是要在40亿个数字中检测一个缺失的数字。
推荐的方法似乎是使用位集(当内存限制是问题的一部分时)。
一个示例帖子是这样的:find-an-integer-not-among-four-billion-given-ones我还可以在 SO 中链接到更多内容。

我的问题如下:bitset 方法似乎隐含地假设数字是非负数。作为我链接到的帖子中的示例，Java 中有这个代码片段:

int radix = 8; 
byte[] bitfield = new byte[0xffffffff/radix]; 
void F() throws FileNotFoundException{ 
    Scanner in = new Scanner(new FileReader("a.txt")); 
    while(in.hasNextInt()){ 
        int n = in.nextInt(); 
        bitfield[n/radix] |= (1 << (n%radix)); 
    } 

    for(int i = 0; i< bitfield.lenght; i++){ 
        for(int j =0; j<radix; j++){ 
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j); 
        } 
    } 
} 

但是在 Java 中所有的整数都是有符号的。结果，发布的代码将因负数而中断。此 int n = in.nextInt(); 可以返回负数。

所以我猜我对这类问题/练习的困惑大约有 2 个部分:
1)bitset可以用来表示负数吗？怎么样？
2) 问题的解决方案是否与特定的编程语言有某种关联？例如。在有无符号数的 C++ 中，我想人们可以接受范围是非负数的假设。

有人能帮我理解一下吗？

Answer 1

尝试

long n = in.nextInt() & 0xFFFFFFFFL; 
bitfield[(int) (n/radix)] |= (1 << (n%radix));

或使用

final int bits = 3; 

bitfield[(int) (n >>> bits)] |= (1 << (n & ((1 << bits) -1)));

稍后

System.out.print((int) (i*radix+j)); 

您可能会发现使用 and int[] 或 long[] 比使用 byte[]

稍快