寻找失踪数从4十亿（再次） [英] Find missing number from 4 billion (again)

问题描述

似乎已经问了一个问题的很多次即将检测缺失的数量在4个十亿的数字。
该recomended方法似乎是使用一个bitset（当内存约束是问题的一部分）。
一个例子文章是这样的：<一href="http://stackoverflow.com/questions/7153659/find-an-integer-not-among-four-billion-given-ones">find-an-integer-not-among-four-billion-given-ones而我也可以在这里SO链接到更多。

It seems that a question that has been asked a lot of times is about to detect a missing number among 4 billion numbers.
The recomended approach appears to be to use a bitset (when memory constraints are part of the problem).
An example post is this:find-an-integer-not-among-four-billion-given-ones and I could also link to more here in SO.

我的问题是：该位集合的方法似乎隐含asume的数字是非阴性。由于在后我联系到一个例子，有在Java中，这code片断：

My problem is the following: The bitset approach seems to implicitely asume that the numbers are non-negative. As an example in the post I linked to, there is this code snippet in 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中所​​有的整数签名。其结果是，code以公布将打破为负数。这 INT N = in.nextInt（）; 可以返回一个负数。

But in Java all the integers are signed. As a result the code as posted will break for negative numbers. This int n = in.nextInt(); can return a negative.

所以我想在某种程度上我的困惑是这样那样的问题/运动约2部分：
1）可以一个bitset用于重新present负数？怎么样？
2）是解决主题相关的特定的编程语言的问题？例如。在C ++中，那里有无符号数我想人们可以接受的假设范围内非负。

So I guess somehow my confusion is about 2 parts on this kind of problem/exercise:
1) Can a bitset be used to represent negative numbers? How?
2) Is the solution to the problem somehow related to a specific programming language? E.g. in C++ where there are unsigned numbers I guess one could accept the assumption that the range is non-negative.

可能有人请帮助我理解？

Could someone please help me understand this?

推荐答案

尝试

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)); 

您可能会发现，使用和 INT [] 或长[] 是速度稍快比使用字节[]

You may find that using and int[] or long[] is slightly faster than using a byte[]

这篇关于寻找失踪数从4十亿（再次）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！