数学研发论坛

 找回密码
 欢迎注册
楼主: gxqcn

[擂台] 求bit位为1数目不超出2的正整数

[复制链接]
发表于 2009-2-4 22:00:12 | 显示全部楼层
明白你的意思了

    考虑 斐波那契 数列 方式也不错啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-4 22:16:26 | 显示全部楼层
那与用 ${ 1, 2, 3, 4, 6, 8, 12, 16, ..., 2^k, 3xx2^(k-1), 2^(k+1), ... }$ 系列的哪个更好?(至少容易四字节或16字节对齐)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-5 08:20:49 | 显示全部楼层

    都不理想
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-5 08:42:48 | 显示全部楼层
早上来了测试了一下,那个程序结果好像还对 ,测试代码:
  1.         UINT32 i,b,e;
  2.         for (i=1 ; i<0xFFFFFFFF ; i++) {
  3.                 b=GreaterEqualBit2_58F(i);
  4.                 e=GreaterEqualBit2_SHSHSH(i);
  5.                 if (b!=e) {
  6.                         printf( "i=%d,G=0x%X,L=0x%X \n",i,b,e);
  7.                         break;
  8.                 }
  9.         }
复制代码
生成数据代码:
  1. ///////////////////////////////////////////////////////////////////////////////////////////////////////////////
  2. //m 1-2 ,2 bits :mark
  3. //           0: at least 3 ones
  4. //           1: 2 ones
  5. //           2: 1 one
  6. //           3: 0 one
  7. //x 3-12 ,10 bits:
  8. //          when contains at least 2 ones ,then x= upper-one
  9. //          eg : 11001 - 100000 ,1001 - 10000 ,0011-0100
  10. //y 13-22 ,10 bits:
  11. //          when contains  2 ones, y= GreaterEqualBit2(first byte+1)
  12. //          eg   :  1010-1100 ,0011 -0100
  13. //z 23-32 ,10 bits:
  14. //          when contains at least 3 ones , it is y =GreaterEqualBit2(first byte) ,so just return z<<24
  15. //          eg  :  0110010 -1000000,101011 -110000
  16. ///////////////////////////////////////////////////////////////////////////////////////////////////////////////
  17. int onescount(UINT32 n){
  18.         int i,r=0;
  19.         for (i=0;i<8;i++){
  20.                 if (n & (1<<i)) {
  21.                         r++;
  22.                 }
  23.         }
  24.         return r;
  25. }
  26. int getmark(UINT32 n)
  27. {
  28.         int t= onescount(n);
  29.         switch(t) {
  30.         case 0:
  31.                 return 3;
  32.         case 1:
  33.                 return 2;
  34.         case 2:
  35.                 return 1;
  36.         default:
  37.                 return 0;
  38.         }
  39. }
  40. int getx(UINT32 n){
  41. //x 3-12 ,10 bits:
  42. //          when contains at least 2 ones ,then x= upper-one
  43. //          eg : 11001 - 100000 ,1001 - 10000 ,0011-0100
  44.         int i,ret=0;
  45.         int t =onescount(n);
  46.         if(t>1){
  47.                 for(i=31;i>=0;i--){
  48.                         if ( n & (1<<i) ) {
  49.                                 ret = 1<<(i+1);
  50.                                 break;
  51.                         }
  52.                 }
  53.         }
  54.         return ret;
  55. }
  56. int gety(UINT32 n){
  57. //y 13-22 ,10 bits:
  58. //          when contains  2 ones, y= GreaterEqualBit2(first byte+1)
  59. //          eg   :  1010-1100 ,0011 -0100
  60.         int ret=0;
  61.         int t =onescount(n);
  62.         if(t==2){
  63.                 ret=GreaterEqualBit2_58F(n+1);
  64.         }
  65.         return ret;
  66. }
  67. int getz(UINT32 n){
  68. //z 23-32 ,10 bits:
  69. //          when contains at least 3 ones , it is y =GreaterEqualBit2(first byte) ,so just return z<<24
  70. //          eg  :  0110010 -1000000,101011 -110000
  71.         int ret=0;
  72.         int t =onescount(n);
  73.         if(t>2){
  74.                 ret=GreaterEqualBit2_58F(n);
  75.         }
  76.         return ret;
  77. }
  78. void gendata(){
  79.         UINT32 i,m,x,y,z;
  80.         printf( "\n---------------------------------------------------------------------\n");
  81.         for (i=0 ; i<256 ; i++){
  82.                 m=getmark(i);
  83.                 x=getx(i);
  84.                 y=gety(i);
  85.                 z=getz(i);
  86.                 printf( "0x%08X,",(m<<30)+(x<<20)+(y<<10)+z);
  87.                 if (! ((i+1)%8)) {
  88.                         printf( "\n");
  89.                 }
  90.         }
  91.        
  92. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-5 09:04:04 | 显示全部楼层


    呵呵, 难为你写这么多数据的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-8-19 22:24 , Processed in 0.046268 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表