编程珠玑第一章第六题

假设用数组array来进行存储数值及其出现的次数 因为int有32比特，而每个数至多出现10次，又2^3-1<10<24-1; 又32/4=8，所有说每个int可以存8个数值及其出现的次数；

一.先说set的实现方法，目的是将数值进行存储且每做一次set个数加一

(1).下面第一件事就是对每个数值进行分组，由上面可知 0~7用array[0]存储及记录次数;

8~15用array[1]存储及记录次数,后面的以此类推；也就是给定一个数number，可以通过 number/8(即number>>3)进行分组

(2)分组之后就是要保存存储数值的个数，并且能够在每次

set之后加1 假设已经存了8个8，9个9；9个10； 由（1）知 8,9,10均用array[1]进行存储和记录 下面我们画出array[1]此时的前12位，从右向左为从低位到高位； 因为每个数需要四位进行存储，所有我们对array[1]的32位由低到高进行 四位一组划分，分别以0~7表明组号，显然组号可以通过数值number对8取余得到 （注：由于只用了8,9,10只用了前12位，另外的后20位没有画出） 10 9 8 //要存储的数值number 2 1 0 //用哪四位进行存储，number%8得到 1001 1001 1000 //要存储数组number的个数 如果此时想要再存1个10，该怎么办呢？ 10 9 8 2 1 0 1001 1001 1000 +0001 0000 0000 =1010 1001 1000 我们对加上的数0001 0000 0000进行观察可知，它是由1向左移8位（2（组号）*4（每组有几位））获得； 从而可以得出一般的结论，即再存一个数是在原有的基础上加上1<<((number%8)*4) ； 至此set部分浮现了

void set (int number){ array[number/8] += 1<<((number%8)*4); //array[number/8]计算出用哪一个数组元素进行存储 //1<<((number%8)*4)将对应存储数值个数的四位加1 //或者表示 成array[number>>3]+=1<<((number&0x7)*4); }

二.再说clr方法的实现，目的是将数值的个数置零

接着一，此时我们有8个8，9个9；10个10； 假如我们想将9的个数清0该怎办？还是画个图进行理解 10 9 8 //要存储的数值number 2 1 0 //用哪四位进行存储，number%8得到 1010 1001 1000 //要存储数组number的个数 此时只要将9对应存储个数的四位清0即可，当然不能影响其他位； 此时只要和(前20位都为1，此处省略不写)1111 0000 1111进行&运算即可 10 9 8 要存储的数值number 2 1 0 用哪四位进行存储，number%8得到 1010 1001 1000 &1111 0000 1111 而1111 0000 1111 可以通过0000 1111 0000取反得到（因为左右移位可以自动补0，所以会利用取反） 而0000 1111 0000可以1111<<4(每组有几位)1(组号)得到 更一般的可以得到1111<<4((number%8))即 0xf<<4*(number%8) 所以最终clr的实现也就明了了

void clr (int number){ array[number/8]=array[number/8]&(~(0xF<<4*((number%8)))); }

三就剩一个test了,目的是测试数值存在的个数并返回（0也可以看成一种特别的存在） 接着二，此时我们有8个8，0个9；10个10 ； 10 9 8 要存储的数值number 2 1 0 用哪四位进行存储，number%8得到 1010 0000 1000 要存储数组number的个数 如果我们要测试10存在的个数，就只需要返回对应存储的四位即1010 要想获得1010，有两种方法 （1）先将者四位移到最右边，然后将高位的都置零 即array[number/8]>>(4*(number%8))&(0xF) (2) 先将其他所有位置0，然后将这四位移到最右边 即( array[number/8]& (0xF<<(4*(number%8))) ) >> (4*(number%8)

int test(int number){ return array[number/8]>>(4*(number%8))&(0xF); }

**下面再贴一下源码，方便扩展和更改 */ 下面再贴一下源码，方便扩展和更改 / 下面再贴一下源码，方便扩展和更改 / （重要的事情说三遍）

#include<iostream> using namespace std; #define HMVTS 8 //一个int要存数值的个数 ,how many values to save in each int #define HMBTSN 4 //每个数值需要多少位来保存数值的个数,how many bits to save the number of the specific value #define MASK 0X0F//1111方便得到最后结果 unsigned int array[30]; void set (int number){ array[number/HMVTS] += (1<<((number%HMVTS)*HMBTSN)); } void clr (int number){ array[number/HMVTS]=array[number/HMVTS]&(~(MASK <<HMBTSN*(number%HMVTS))); } int test(int number){ return array[number/HMVTS]>>(HMBTSN*(number%HMVTS))&(MASK); } int main(){ int index; cout<<"未排序的数组为：\n"; unsigned int testArr[20]={ 11,44,56,56,45, 56,56,56,78,49, 60,71,90,117,148, 199,56,56,56,70}; for(index=0;index<20;index++){ set(testArr[index]); cout<<testArr[index]<<" "; } cout<<endl; cout<<"排序结果为：\n"; for(int i=0;i<200;i++){ if(test(i)>0){ for(int j=test(i);j>0;j--){ cout<<i<<" " ; } }} cout<<endl; clr(56); cout<<"清除56后的排序结果为：\n "; for(int i=0;i<200;i++){ if(test(i)>0){ for(int j=test(i);j>0;j--){ cout<<i<<" " ; } }} cout<<endl; }