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

私は2つの問題があると思います：

  1. 配列には65536エントリがありますが、各エントリに32ビットを格納するため、65536/32エントリのみが必要です。

  2. 各intに32ビットを格納しますが、ギャップを見つけるときは0から7までのjのみをチェックします

最初のバグは、プログラムが65536を16ビット数の欠落として報告することを意味します。2番目のバグは、プログラムが欠落している番号を検出しないことを意味します。

すなわち変更

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で見つけることができます。

上位レベルのコードには追加のバグがあります。

ビットセットを設定する2番目のパスでは、上位ビットが一致する数値のみを含める必要があります。

すなわち変更

v.setBit(sc.nextInt());

のようなものに

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