unsigned int bit[N];

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
bool hasDuplicatedItem(int *a, int len)
{
  int length, max, i; 
  length = len;
  max = a[0];
  for(i = 1; i < length; i++){
    if(a[i] > max)
      max = a[i];
  }
  int *arr;
  arr = (int*)malloc(sizeof(int) * (max + 1));
  for(i = 0; i < length; i++){
    if(arr[a[i]])
      return true;
    else
      arr[a[i]] = 1;
  }
  return false;
}
int main()
{
  int length;
  int test[] = {0,1,2,3,45,12,13};
  length = (sizeof(test) / sizeof(test[0]));
  if(hasDuplicatedItem(test, length))
    printf("hasDuplicatedItem!\n");
  else
    printf("hasNoDuplicatedItem!\n");
  return 0;
}

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
void bitmapSort(int *a, int len)
{
  int length, max, min, i, index; 
  length = len;
  min = max = a[0];
  //找出数组最大值
  for(i = 1; i < length; i++){
    if(a[i] > max){
      max = a[i];
    }
    if(min > a[i]) {
      min = a[i];
    }
  }
  //得到位图数组
  int *arr;
  arr = (int*)malloc(sizeof(int) * (max - min + 1));
  for(i = 0; i < length; i++){
    index = a[i] - min;
    arr[index]++;
  }
  //重整a中的元素
  int arr_length;
  arr_length = max - min + 1;
  index = 0;
  for(i = 0; i < arr_length; i++){
    while(arr[i] > 0){
      a[index] = i + min;
      index++;
      arr[i]--;
    }
  }
}
void print(int *a, int n)
{
  int i;
  for(i = 0; i < n; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
}
int main()
{
  int length;
  int test[] = {50,1,26,3,45,12,13};
  length = sizeof(test) / sizeof(test[0]);
  print(test, length);
  bitmapSort(test, length);
  print(test, length);
  return 0;
}

#include<stdio.h>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];
/* a[i>>SHIFT]是第i位应该在第几个int上 */
/* (1<<(i & MASK))是第i位在该int上的第几个bit */
void set(int i)
{
  a[i>>SHIFT] |= (1<<(i & MASK));
}
void clr(int i)
{
  a[i>>SHIFT] &= ~(1<<(i & MASK));
}
int test(int i)
{
  return a[i>>SHIFT] & (1<<(i & MASK));
}
int main()
{
  int i;
  for(i = 0; i < N; i++)
    clr(i);
  while(scanf("%d", &i) != EOF)
    set(i);
  for(i = 0; i < N; i++)
    if(test(i))
      printf("%d\n", i);
  return 0;
}