Blog·Tanky WooABOUTRSS

Programming Pearls --- Reading Notes

17 Jan 2012
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

This is my reading notes of the Programming Pearls(second Edition).

Start: 2012.1.18

End:  2012. ??.??

Column 1: CRACKING THE OYSTER

use the bitmap to solve the problem.

Code:

/**
 * Programming Perls 2
 * Column 1
 * Tanky Woo @ www.WuTianQi.com
 */
#include <iostream>
#include <fstream>
using namespace std;

const int N = 10000000;
const int SHIFT = 5;
const int MASK = 0x1F;

int bitmap[N>>SHIFT + 1];

void clr(int i){
    bitmap[i>>SHIFT] &= ~(1 << (i & MASK));
}

void set(int i){
    bitmap[i>>SHIFT] |= 1 << (i & MASK);
}

bool test(int i){
    return (bitmap[i>>SHIFT] & (1 << (i & MASK)));
}

int main()
{
    ifstream fin("F:\\in.txt");
    ofstream fout("F:\\out.txt");
    if((!fin) || (!fout))
    {
        cout << "Can't open the file\n";
        exit(1);
    }

    for(int i=0; i<=N; ++ i)
        clr(i);

    int num;
    while(!fin.eof())
    {
        fin >> num;
        set(num);
    }

    for(int i=0; i<=N; ++i)
        if(test(i))
            fout << i << " ";


}