这篇博客是从旧博客 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 << " ";
}