本文主要是介绍《编程珠玑》之位图技术，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
编程珠玑，相当不错的一本书。其中很多金句需要在工作的过程当中，铭记于心：
chapter 1，书中的金典语句：
@1，明确问题（问对正确的问题），这场战役就成功了90%.
@2，几分钟的仔细研究可以大幅削减代码的长度、程序员的时间和程序系统运行的时间。
@3，设计者确定其设计已经达到了完美的标准，不是不能再增加任何东西，而是不能再减少任何东西。
@4，程序员的主要问题，与其说是技术问题，还不如说是心理问题：他不能解决问题，是因为他试图解决错误的问题。问题的最终解决，是通过打破他的概念壁垒，进而去解决一个较简单的问题而实现的。
明确问题：
解决实际的问题，首先是找到现实问题里面，包含的最本质的问题，然后加以提炼成更加清晰规范化的条件：
输入：文件包含最多10^7个正整数、每个正整数不大于10^7。并且数据均不重复，数据之间无关联。
输出：升序输出输入的列表
外部约束：约1MB的内存空间，目标是10秒钟运行完全。
作者讨论了该问题的几种解决方案，比较了几种方案的实现复杂度和性能。最终针对问题，选用了“结构简单、部件少、易于维护、非常坚固”的 位图方案 。
这里附加自己的代码实现，关键还是在于位图技术的有效应用。
#include<stdio.h>
#include<assert.h>
#define BITMAP_SIZE 6
typedef unsigned int MAP_TYPE;
unsigned int g_map_item_size = 8*sizeof(MAP_TYPE);
/** \brief 使用位图对数组进行排序
* \param arr：带排序数组，要求数组元素不重复，且为正整数。
* \param size: 数组大小
* \return 空
*/
void sort_unique_positive_integer(int *arr, unsigned int size)
{
MAP_TYPE bitMap[BITMAP_SIZE];
//step 1, bitMap init 0
for(int i=0;i<BITMAP_SIZE;++i)
{
bitMap[i]=0;
}
//step 2, set bitMap bit value according to input value
for(int i=0;i<size;++i)
{
int idx=arr[i]/g_map_item_size;
int idxBit=arr[i]%g_map_item_size;
assert(idx < BITMAP_SIZE);
bitMap[idx] = (bitMap[idx] | (1<<idxBit));
}
//step 3,output result according to bitMap bit value
for(int i=0;i<BITMAP_SIZE;++i)
{
for(int j=0;j<g_map_item_size;++j)
{
if(0 != ((bitMap[i])&(1<<j)))
{
printf("%d ",(g_map_item_size*i)+j);
}
}
}
printf("\n");
}
int main()
{
int a[30]={4,5,7,13,47,45,23,44,16,8,33,24,27,28,0};
sort_unique_positive_integer(a,30);
return 0;
}
编程珠玑提供的代码，果然简洁：
这篇关于《编程珠玑》之位图技术的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
