学步园

Problem 3.

    This problem let us write all the solutions, and run, then based on the results we can get the most effective solution.

Now I don't want to compare these solutions including last file has given.

C++ bitset solution:

#include <iostream>
#include <bitset>

#define MAX_LENGTH 10000000

int main (int argc, char *argv[]) {
    std::bitset<MAX_LENGTH> array;

    int32_t i;
    for (i = 0; i < MAX_LENGTH; i++) {
        array[i] = 0;
    }

    i = 0;
    while (std::cin >> i) {
        array[i] = 1;
    }

    for (i = 0; i < MAX_LENGTH; i++ ) {
        if (array[i]) {
            std::cout << i << " is set" << std::endl;
        }
    }

    return 0;
}

C using the last file functions:

#include <stdlib.h>
#include <stdio.h>

#define MAX_LENGTH 10000000
#define INT_LENGTH 32
#define SHIFT 5
#define MASK 0X1F

int32_t integerArray[1 + MAX_LENGTH >> SHIFT];

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

void clear(int32_t i) {
    integerArray[i >> SHIFT] &= ~(1 << (i & MASK));
}

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

int main (void) {
    int32_t i;
    for (i = 0; i < 10000000; i++) {
        clear(i);
    }

    while (scanf("%d", &i) != EOF) {
        set(i);
        if (test(i)) {
            printf ("%d is set\n", i);
        }
    }

    return 0;
}