FilesExpand file tree

 master

/

bitmapSort.c

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

59 lines (51 loc) · 1.03 KB

 master

/

bitmapSort.c

Copy path

Top

File metadata and controls

• Code
• Blame

59 lines (51 loc) · 1.03 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

#include <stdio.h>

#include <stdlib.h>

#define BITSPERWORD 32

#define SHIFT 5

#define MASK 0x1F

#define NN 100000000

#define MM 100000000

int a[1 + NN/BITSPERWORD];

//右移5位相当于除2^5也就是32，i & 0x1F 保留了低五位，相当于模32. ### x%n == x&(n-1) n为2的整数次幂

/*

void set(int i) { a[i/32] |= (1<<(i%32)); }

void clr(int i) { a[i/32] &= ~(1<<(i %32)); }

int test(int i){ return a[i/32] & (1<<(i %32)); }

*/

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 argc,char **argv)

{

int i;

int j;

int *arr = (int*)malloc(sizeof(int)*MM);

int count=0;

for (i = 0; i < NN; i++) {

clr(i);

}

for (j = 0; j < MM; j++)

{

arr[j]=rand()%NN;

}

for (j = 0; j < MM; j++)

{

set(arr[j]);

}

printf("\nAfter Sorted:\n");

for (i = 0; i < NN; i++)

{

if (test(i))

{

count++;

}

}

printf("\nAfter sorted count is %d\n",count);

return 0;

}