0

我正在尝试创建一个由int[].
所以我有以下代码： 

public class BitVector {  

  int[] vector = new int[1 << 16];  

  public void setBit(int nextInt) {  
    nextInt = nextInt & 0xFFFF;  
    int pos = nextInt / 32;  
    int offset = nextInt % 32;  
    vector[pos] |= (1 << offset);    
  }

  public int findClearedBit() {  

    for(int i = 0;  i < vector.length; i++){              
            for(int j = 0; j < 8; j++){  
                if((vector[i] & (1 << j)) == 0)   
            return i * 32 +  j;  
        }  
    }  

    return -1;  
   }  

}

我知道也许我应该使用byte[]等，但我想知道为什么这种方式不起作用。
这个想法是我int从一个流中传入并保留低 16 位并将相应的位标记为设置。因此，当我遍历向量时，我会发现缺少数字（由低 16 位表示）。
但我得到错误的结果。所以我相信我的处理是错误的。
有任何想法吗？

更新：
我有一个 32 位整数流。当我阅读它们时，我尝试通过使用低 16 位并设置位向量（发布的代码）来标记缺失的数字。
我还尝试找到第二次读取流的高 16 位丢失。
因此，虽然缺少的数字是： 231719592= ( 1101110011111100001010101000) = ( 3535- 49832) 当我读取流时，我没有得到49832缺少的低位，但是65536

更新2： 

public int findMissingInt(File f)throws Exception{  
    Scanner sc = new Scanner(f);  
    int SIZE = 1 << 16; 
    int[] occurences = new int[SIZE];  
    while(sc.hasNext()){  
    occurences[getIdx(sc.nextInt())]++;  
    }  

    int missingUpper = -1;  
    for(int i = 0; i < occurences.length; i++){  
    if(occurences[i] < SIZE){  
        System.out.println("Found upper bits:"+i);  
        missingUpper = i;  
        break;  
    }  
    }
    if(missingUpper == -1){   
    return -1;  
    }  
    //Arrays.fill(occurences, 0);  //I reused this. Bellow changed after answer of Peter de Rivaz 
    BitVector v = new BitVector(new int[1 << (16-5)]);  
    sc = new Scanner(f);
    while(sc.hasNext()){  
    v.setBit(sc.nextInt());  
    }  

    int missingLower = v.findClearedBit();
    System.out.println("Lower bits:"+missingLower);   
    return createNumber(missingUpper, missingLower);  

}   


private int createNumber(int missingUpper, int missingLower) {  
        int result = missingUpper;  
        result = result << 16;  

        return result | missingLower;  
}  



public int getIdx(int nextInt) {          
    return (nextInt >>> 16);        
}

我得到： 

Missing number=231719592  
Found upper bits:3535 //CORRECT  
Lower bits:-1  //WRONG
Actual missing number=-1  //WRONG
4

1 回答 1

5

我认为有两个问题：

  1. 您的数组有 65536 个条目，但您在每个条目中存储 32 位，因此您只需要 65536/32 个条目。

  2. 您在每个 int 中存储 32 位，但在查找间隙时仅检查 j 从 0 到 7

第一个错误意味着您的程序将 65536 报告为缺少的 16 位数字。第二个错误意味着您的程序没有发现丢失的数字。

即改变

int[] vector = new int[1 << 16];

到

int[] vector = new int[1 << (16-5)];

和改变

for(int j = 0; j < 8; j++)

到

for(int j = 0; j < 32; j++)

编辑

从评论来看，问题实际上是如何在 RAM 有限的情况下找到丢失的数字。这个问题的答案可以在 stackoverflow上找到。

更高级别的代码中还有一个额外的错误。

在填充位集的第二遍期间，您应该只包括具有匹配高位的数字。

即改变

v.setBit(sc.nextInt());

类似于

int nx = sc.nextInt();
if (getIdx(nx)==missingUpper)
  v.setBit(nx);
于 2012-11-25T18:39:32.510 回答