数学研发论坛

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

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

[复制链接]
 楼主| 发表于 2009-2-3 15:21:43 | 显示全部楼层

回复 36# 无心人 的帖子

看起来不错,
若能将部分访问内存的语句改成访问寄存器的就更好了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 15:22:05 | 显示全部楼层


当然, 这么小的范围
Cache整个表才是王道
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 15:23:10 | 显示全部楼层
我想
  xor edx, edx
  setne dl
应该不阻塞
不是说了么
全0的寄存器不存在部分寄存器阻塞
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 15:25:30 | 显示全部楼层
原帖由 无心人 于 2009-2-3 15:20 发表


  汇编大概在20个时钟周期内就能完成
  hash光一个除法就至少20周期

谁让你用除法了,说是Cache表可能比较合适
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 15:31:11 | 显示全部楼层


你来实现下
看最后翻译成汇编
20条内能实现么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 15:32:08 | 显示全部楼层
好吧,好久不编程了,试试看
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 15:34:47 | 显示全部楼层
http://www.codingnow.com/mmx/mmx2.htm#4

这里有部分寄存器阻塞的详细说明
我们这里的代码应该属于这种例外
即首先xor大寄存器,再setne,则应该不影响稍后的指令
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 17:01:31 | 显示全部楼层
记得原先写的代码求大于等于n的2的方幂, 当时写的不好
如果现在写,应该这么做
    mov eax, 1
    bsr  ecx, n
    bsf  edx, n
    sub edx, ecx
    adc  eax, 0
    mov edx, 0
    cmp n, 0
    cmove eax, edx
    shl eax, cl
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 17:05:37 | 显示全部楼层
大概写了一下,就算示意吧,那个表的数据我就不算了,太麻烦了
  1. #include <stdio.h>

  2. typedef unsigned int UINT32;

  3. typedef struct data {
  4.         UINT32 retvalue;
  5.         UINT32 halfdata;
  6.         int type; //0 : directly return ; 1: need to go on  
  7. } ITEM_DATA;

  8. ITEM_DATA  hash  [256] = {
  9.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  10.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  11.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  12.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  13.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  14.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  15.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  16.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  17.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  18.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  19.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  20.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  21.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  22.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  23.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  24.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  25.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  26.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  27.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  28.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  29.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  30.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  31.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  32.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  33.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  34.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  35.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  36.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  37.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  38.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  39.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
  40.         {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0}
  41. };


  42. UINT32  GreaterEqualBit2(UINT32 n)
  43. {
  44.         int t1=0,t2=0;
  45.         unsigned char *v= (unsigned char *)&n;
  46.     //find first 2 v that large than zero
  47.         if (v[3]>0) {
  48.                 if( hash[v[3]].type == 0 ) {
  49.                         //3
  50.                         return ( hash[v[3]].retvalue )<<24;
  51.                 } else {
  52.                         if (v[2]>0) {
  53.                                 //3,2
  54.                                 return ((hash[v[3]].halfdata)<<24)+((hash[v[2]].halfdata)<<16);
  55.                         }
  56.                         else {
  57.                                 if(v[1]>0) {
  58.                                         //3,1
  59.                                         return ((hash[v[3]].halfdata)<<24)+((hash[v[1]].halfdata)<<8);
  60.                                 }
  61.                         }
  62.                         //3,0
  63.                         return ((hash[v[3]].halfdata)<<24)+((hash[v[0]].halfdata));
  64.                 }
  65.         }
  66.         else {
  67.                 if(v[2]>0)        {
  68.                         if( hash[v[2]].type == 0 ) {
  69.                                 //2
  70.                                 return ( hash[v[2]].retvalue )<<16;
  71.                         } else {
  72.                                 if (v[1]>0)  
  73.                                         //2,1
  74.                                         return ((hash[v[2]].halfdata)<<16)+((hash[v[1]].halfdata)<<8);
  75.                                 else
  76.                                         //2,0
  77.                                         return ((hash[v[2]].halfdata)<<16)+((hash[v[1]].halfdata) );
  78.                         }
  79.                 }
  80.                 else
  81.                         if(v[1]>0) {
  82.                                 if( hash[v[1]].type == 0 )
  83.                                         //1
  84.                                         return ( hash[v[1]].retvalue )<<8;
  85.                                 else
  86.                                         //1,0
  87.                                         return ((hash[v[1]].halfdata)<<8)+((hash[v[1]].halfdata) );
  88.                         }
  89.         }
  90.         //0
  91.         return  hash[v[0]].retvalue ;
  92. }

  93. int  main(int argc, char * argv[]){   
  94.         int i;
  95.         for (i=0x11 ; i<0x111121 ; i++)
  96.                 printf(" input %d , output %X \n",i,GreaterEqualBit2(i));
  97.        
  98.     return 0;
  99. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 17:08:45 | 显示全部楼层


   你认为这么复杂的代码比我的汇编要高效么?
   况且,最终的代码的适用范围要比GxQ题目要求的大
   只要是1-(2^31+2^30)就可以
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-12-14 15:14 , Processed in 0.057683 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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