32ビット整数がでたらめな順に入っているファイルに入っていない32ビット整数を一つ見つけてください。


> Q.最大で40億個の32ビット整数がでたらめな順に入っているファイルがあるとします。このファイルに入っていない32ビット整数を一つ見つけてください。  
>  『珠玉のプログラミングー本質を見抜いたアルゴリズムとデータ構造』 column2.1.A より

と言う問題です。

本に載っている解き方としては、

>
> 40億個の整数を最初のビットが0のものと1のものにわけて、2つのファイルに書き込んでいきます。それぞれのファイルに20億個の整数が書かれているはずです。次に、出力されたファイルで整数の個数の少ない方を新しい入力ファイルとし、今度は2番目のビットをみてこれを2つのファイルに分けます。そしてこれを次々と繰り返していくと出力させる。

と言うものです。

この方法をPythonでコード化することができません。調べ方が悪いのかこの方法でやっている人も見つけられませんでした。

Pythonでコード化する方法もしくは答えをご提示していただけないでしょうか？




## 特定の位置のビットが 0 か 1 か判定する方法

このアルゴリズムを使う場合、与えられた 32 bit 整数 `n` の `i` 番目のビットが `0` か `1`
か判定する必要があります。今回のアルゴリズムでは「`i`
番目のビット」は上位ビットから数えることも下位ビットから数えることもできます。ここでは下位ビットから数えることにします。またプログラムの分かりやすさのため、解説文と異なり「最初のビット」を「0
番目のビット」と数えることにします。

`n` の `i` 番目のビットが `0` か `1` か判定するためには、ビット演算を使うと簡単にできます。`i` 番目のビットだけ `1`
で後のビットは `0` の数 `mask` を用意し、`n` と `mask` をビットごとに AND 演算し、`i` 回右シフトすると良いです。

具体例を使って考えてみます。`n = 42`, `i = 3` とします。

[code]

                  n = 0b_0010_1010
               mask = 0b_0000_1000
           n & mask = 0b_0000_1000
    (n & mask) >> i = 0b_0000_0001
    
[/code]

このように、`(n & mask) >> i` の計算結果が `0` か `1` かを見れば、`i` 番目のビットが `0` か `1`
かを判定することができます。

なお、細かいことを書いておくと今回のアルゴリズムでは単にビットのパターンだけ見ているので、ビッグエンディアン／リトルエンディアンの違いや、符号付き整数における
1 の補数／2 の補数の違いを気にする必要はありません。ビットが 1
つでも異なれば整数としても異なるということだけが保証されていれば良いです。たとえば逆に浮動小数点数だと `+0` と `-0`
は最上位ビットが異なるものの等しい数なので、今回のアルゴリズムをそのまま使うことができません。

## 入力用のファイルを生成する方法

でたらめな整数を重複を許して 40 億個生成するなら、単にランダムな整数の生成を 40 億回行いつつ、ファイルに追記していけば良いです。Python では
[`random.randint(a,
b)`](https://docs.python.org/ja/3/library/random.html#functions-for-integers)
を使うとランダムな整数を作れます。ファイルへ追記するには、`open()` する際のオプションを [`'a'`
にすると良いです](https://docs.python.org/ja/3/library/functions.html#open)。

以下がサンプルプログラムです。

[code]

    import random
    
    filename = 'input.txt'
    input_num = 40_0000_0000  # この数はもっと小さめにすることをオススメします。
    
    # Python 3 の整数は勝手に多倍長にされるので、以下の式は 32 bit 環境でも問題ないです。
    # 問題文には「32 bit 整数」が符号付きなのか符号無しなのか指定がありません。ここでは符号付きにしていますがどちらでも良さそうです。
    int32_min = - (1 << 31)
    int32_max = (1 << 31) - 1
    
    if __name__ == '__main__':
        random.seed()
    
        # もしファイルが存在していたら、中身を削除する。
        open(filename, 'w').close()
    
        # append モードでファイルを開き、乱数をたくさん書きこむ。
        with open(filename, 'a') as f:
            for i in range(input_num):
                n = random.randint(int32_min, int32_max)
                f.write(str(n) + '\n')
    
[/code]

実際には、40 億行のファイルを作るには時間がかかりますし、ファイルサイズも膨大になります（30 GB くらい？）。小さめの数で試すのが良いでしょう。

