chapter 1

2.如何用位逻辑运算来实现位向量？##

把bitmap存在int中，一个int32位，可以存32个数。

//
//  main.cpp
//  pearls
//
//  Created by YangKi on 15/11/26.
//  Copyright © 2015年 YangKi. All rights reserved.


#include <stdio.h>
#include <stdlib.h>
using namespace std;

#define SHIFT 5
#define MASK 0x1F
#define N 1000

int storage[1+N/32];

void set(int i){        storage[i>>SHIFT] |=  (1<<(i & MASK));  }
void clr(int i){        storage[i>>SHIFT] &= ~(1<<(i & MASK));  }
int test(int i){ return storage[i>>SHIFT] &   (1<<(i & MASK));  }

int main()
{
    int i;
    scanf("%d", &i);
    
    set(i);
    
    if(test(i))
    {
        printf("exist\n");
    }
    else
    {
        printf("not exist\n");
    }
    
    return 0;
}

4.如何生成不重复的随机整数？##

先把数字按照顺序放上去，再互相交换，打乱顺序。

for(int i=0; i<n; i++)
    a[i]=i;
for(int i=0; i<n; i++)
{
    pos=rand()%(n-i)+i // i<= pos <=n-1
    swap(i, pos); // 交换数组两个数
}

9.如何处理一个很少访问的巨大数组的初始化?##

假设有一个很大的数组data[N], 只会随机访问其中的几个数，如此一来，如果按照往常策略对其全部元素顺序进行初始化便会花费巨大的时间。如果此时我们有足够的空间，则我们可以用下面的方法来进行部分初始化，可以大大节约时间。to[]数组来存储data[]中已经初始化的元素，from[]数组来存储初始化元素在to[]中的index。

举个例子，要取data[3]，to里面如果存着3这个值，表明已经初始化过，但如何快速的找到to里面的3。只要看from[3]中存储的值，该值就是to中存3的位置。

//
//  main.cpp
//  pearls
//
//  Created by YangKi on 15/11/26.
//  Copyright © 2015年 YangKi. All rights reserved.
//  常量时间初始化数组
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define ms 100
int data[ms]; //需要初始化的数组
int from[ms]; // from[i] 表示data[i]的i在to[]中的index
int to[ms]; //所有被初始化过的data元素的index都存在to[]中， 比如data[3]被初始化了，则3一定被存在to[]中
int top;

//判断是否被初始化过。
bool is_init(int i)
{
    return (from[i] < top && to[ from[i] ] == i);
}

int main(void)
{
    top = 0;
    //1. 这里生成一些随机数值。
    for (int i = 0; i < ms; ++i)
        data[i] = from[i] = to[i] = i;
    for (int i = 0; i < ms; ++i)
    {
        if (is_init(i))
        {
            printf("error");
        }
        int v = i + rand()%(ms - i );
        int t = data[i]; data[i] = data[v]; data[v] = t;
        
        v = i + rand()%(ms - i );
        t = from[i]; from[i] = from[v]; from[v] = t;
        
        v = i + rand()%(ms - i );
        t = to[i]; to[i] = to[v] ; to[v] = t;
    }  
    
    //2. 开始初始化
    for (int i = 0; i < ms; ++i)
    {
        if (is_init(i) == false)
        {
            data[i] = i;
            from[i] = top;
            to[top++] = i;
        }
    }
    
    for (int i = 0; i < ms; ++i)
    {
        if (!is_init(i))
        {
            printf("error: %d\n", i);
        }
    }
    return 0;
}