用户名: 密码: 忘记密码? 注册

位图排序

作者:  时间: 2011-01-06
位图排序:
任意个(MAX_NUMBERS个) 0到固定值(MAX_VALUE)之间的数排序

时间复杂度O(n), 空间几乎是O(1),空间需求很低

假定int的长度是32位,即一个int可以编码32个数字(简单起见,一个bit代表一个数字,实际可以编码的范围就是unsigned int的最大值,但计算比较复杂), 那么0到n之间的数字就可以用最多n/32+1个整形表示,每个int的每个bit代表一个数。。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_VALUE (800000000)
#define MAX_NUMBERS (100) 

int main(void){
    int size = MAX_VALUE/32+1;
    int* bits_array = (int *)calloc(size,sizeof(int));
    printf("Input numbers:\n");
    int i,p = 0;
    int array_index = 0;
    int bit_index = 0;
    srand((unsigned)time(0));
    for(i=0;i<MAX_NUMBERS;i++){
        int v = (int)(MAX_VALUE * (rand()/(RAND_MAX+1.0)));
        if(p){
           printf(",");
        }
        printf("%d",v);
        p=1;
        array_index = v/32;
        bit_index = v % 32;
        bits_array[array_index] |= 1 << bit_index;
    }

    printf("\nSorted Numbers:\n");
    int bits;
    int b;
    p=0;
    for(i=0;i<size;i++){
        bits = bits_array[i];
        int j;
        for(j=0;j<32;j++){
            b = bits & (1 << j);
            if(b != 0){
                if(p){
                    printf(",");
                }

                printf("%d",i*32+j);
                p = 1;
            }
        }
    }

    free(bits_array);
    return 0;
}



常用bit操作:
第n位置1:

value &= ~(1 << n);


第n位清0:

value &= ~(<< n);


第n位反转:

value ^= 1 << n;


检查第n位是否为1:

bit = value & (1 << n);