【编程珠矶】开篇 千万号码的排序问题
注：学习了《编程珠矶》第一章，将涉及的一些知识点整理如下
?
value-->index 将某个数转化为位图的索引，如要表示value=2,即将位图index=2上的value赋为1（00100000.。。）
?
位图数据结构
～位反
<< 位左移
>> 位右移
& 位与 ： 同为1（真）为1
| 位或 ：只要有一个为1（真）则为1
^ 位异或 ：1 和 0为1
?
0,1 | 1 = 1,1??? ==> 或1，都成1
0,1 | 0 = 0,1
0,1 & 1 = 0,1
0,1 & 0 = 0,0? ==> 与0，都成0
0,1 ^ 1 = 1,0? ==> 异或1，变反
0,1 ^ 0 = 0,1
#define BITS_PER_BYTE 8 #define BITS_PER_INT (BITS_PER_BYTE * 4) // set the bit of the int specified by index to 1. // the index is zero-based, counting from the left(the higher end) inline void pearl_int_set(int* data, int index) { int mask = 1 << (BITS_PER_INT - 1 - index); *data |= mask; } // test whether a bit of the int specified by index is 1. // the index is zero-based, counting from the left(the higher end) inline int pearl_int_test(int* data, int index) { int mask = 1 << (BITS_PER_INT - 1 - index); return (*data) & mask; } // set a bit of the int specified by bit_index to 0. // the index is zero-based, counting from the left(the higher end) inline void pearl_int_clear(int *data, int bit_index) { int mask = ~(1 << (BITS_PER_INT - 1 - bit_index)); *data &= mask; } // get the right(lower) part of the int. inline int pearl_int_right(int *data, int count) { int mask = 1; while(count > 0) { mask = mask << 1 + 1; } return *data & mask; } // get the left(upper) part of the int value inline int pearl_int_left(int *data, int count) { int mask = 1; count = BITS_PER_BYTE - count; while (count > 0) { mask = mask << 1 + 1; } mask = ~mask; return *data & mask; } // set a bit of the speicified memory area to 1. // @warning this function does NOT perform error checking. inline void pearl_set(int *bitplane, int index) { int offset = index / BITS_PER_INT; int pos = index - offset * BITS_PER_INT; pearl_int_set(bitplane + offset, pos); } // set a bit of the specified memory area to 0. // @warning this function does NOT perform error checking. inline void pearl_clear(int *bitplane, int index) { int offset = index / BITS_PER_INT; int pos = index - offset * BITS_PER_INT; pearl_int_clear(bitplane + offset, pos); } // test if a bit of the specified memory area is 1. // @warning this function does NOT perform error checking. inline int pearl_test(int *bitplane, int index) { int offset = index / BITS_PER_INT; int pos = index - offset * BITS_PER_INT; return pearl_int_test(bitplane + offset, pos); } ?如果待排序数据都在内存中
?
