再次从40亿中找到缺失的数字。
再次从40亿中找到缺失的数字。
一个经常被问到的问题似乎是如何在40亿个数字中检测到一个缺失的数字。
推荐的方法似乎是使用位集（当内存限制是问题的一部分时）。
一个示例帖子是：find-an-integer-not-among-four-billion-given-ones，我还可以在这里提供更多的链接。
我的问题是：位集方法似乎默认假设这些数字是非负的。例如，在我链接的帖子中，有这样的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
但在Java中，所有的整数都是有符号的。因此，这段代码会对负数出现错误。这个int n = in.nextInt();可能返回一个负数。
所以我想我对这种问题/练习存在两个困惑：
1）位集能够表示负数吗？怎样实现？
2）解决这个问题是否与特定的编程语言有关？例如，在C++中，存在无符号数字，我猜可以接受范围是非负的假设。
有人可以帮我理解吗？
这段代码是用来解决一个名为 "Find missing number from 4 billion (again)" 的问题。问题的具体原因和解决方法如下：
问题原因：
问题的起因是要在一个范围为0到4亿的连续整数中找到缺失的数字。为了解决这个问题，代码使用了一个位字段数组来表示整数的存在与否。位字段数组的大小取决于所使用的基数(radix)。
解决方法：
首先，代码使用了以下两种方法将输入的整数映射到位字段数组中的相应位置：
1. 使用位掩码将输入的整数n映射到位字段数组bitfield中：bitfield[(int) (n/radix)] |= (1 << (n%radix));
2. 使用位掩码和位移操作将输入的整数n映射到位字段数组bitfield中：bitfield[(int) (n >>> bits)] |= (1 << (n & ((1 << bits) -1)));
然后，代码使用以下方式输出缺失的数字：
System.out.print((int) (i*radix+j));
最后，代码讨论了一些与性能相关的问题：
1. 使用int[]或long[]数组比使用byte[]数组稍微更快一些。
2. 当将bitfield[(int) (n/radix)]的结果向下转型为int时，可能会得到负数。
3. 如果将范围为[0, 2^32)的整数除以8，得到的范围将为[0, 2^29)，最大值约为5.12亿。
4. 使用bits=3的方法是否计算的是第一种方法中的n？为什么int[]数组比byte[]数组更快？
- bits=3的方法计算的是相同的n，只是使用了不同的位掩码和位移操作。
- int[]数组比byte[]数组更快是因为在32/64位系统中，内存字大小为32/64位，要提取一个字节需要读取字，屏蔽掉要更改的字节，然后将该字节替换在字中，与在字节中更改一个位的操作相似。也就是说，移位和屏蔽操作比除法和取模操作更快。与从文件中读取文本或写入控制台相比，这是微不足道的差异，所以这只是为了个人的知识。
最后，代码中的in.nextInt() & 0xFFFFFFFFL;保证了将整数赋值给long时，符号位始终为零，从而得到了范围为[0, 2^32)的整数范围。
这个问题的出现是因为在给定的范围内查找缺失的数字。原文中提到的解决方法是将边界值添加到所有数字上，以确保它们都是正数。但是这种方法并不适用于任意长的数字。在Java中，由于没有无符号整数，需要使用更大的数据类型。通过将-2^31添加到整数范围中，就可以得到[0, 2^32)的范围。
对于“doesn't work for arbitrarily long numbers, but then that's usually not a problem”这句话的解释是，如果没有下限，就无法将下限添加到所有数字上。例如，假设范围是整数（数学意义上的整数），没有“最小的整数”可以添加，以确保所有数字都是正数。但是，如果范围不受限制，那么这个问题本身就没有意义，所以这个问题并不是一个问题。
通过将边界值添加到数字上，可以在给定范围内查找缺失的数字。但是这种方法对于任意长的数字不适用，因为需要使用更大的数据类型。如果范围没有下限，则无法使用这种方法。