1

似乎一个被问了很多次的问题就是要在 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();可能会返回负数。

所以我想不知何故我的困惑是关于这种问题/练习的两个部分：
1）可以使用位集来表示负数吗？如何？
2）问题的解决方案是否与特定的编程语言有关？例如，在有无符号数字的 C++ 中，我想人们可以接受范围是非负数的假设。

有人可以帮我理解这一点吗？

4

2 回答 2

4

尝试

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[]orlong[]比使用 a 稍快byte[]

于 2012-04-16T09:35:21.797 回答
3

那么有一个明显的解决方案：由于我们知道每个数字都有一个特定的范围 [a, b) 您可以将下边界添加到所有数字以获得有保证的正数。

现在这不适用于任意长的数字，但这通常不是问题

于 2012-04-16T09:30:53.863 回答