【编程珠矶】开篇 千万号码的排序问题

注：学习了《编程珠矶》第一章，将涉及的一些知识点整理如下

 

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

掩码

掩码在计算机学科及数字逻辑中指的是一串二进制数字，通过与目标数字的按位操作，达到屏蔽指定位而实现需求。
示例：创造一个掩码msk把一个指令cmd的第0~3位（右边第一位为0位）清零：

指令 cmd = 0110011011
创造掩码 msk = 0000001111

用掩码的反码~msk和指令cmd做按位与运算 cmd & ~msk = 0110011011 & 1111110000 = 0110010000则指定的第0~3位已被清零。

 

    #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);  
    }  

 

如果待排序数据都在内存中