论坛 › 编程擂台 › 求bit位为1数目不超出2的正整数

gxqcn 发表于 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的寄存器不存在部分寄存器阻塞

shshsh_0510 发表于 2009-2-3 15:25:30

原帖由 无心人 于 2009-2-3 15:20 发表 http://bbs.emath.ac.cn/images/common/back.gif
:lol

汇编大概在20个时钟周期内就能完成
hash光一个除法就至少20周期
谁让你用除法了，说是Cache表可能比较合适:)

无心人 发表于 2009-2-3 15:31:11

:)

你来实现下
看最后翻译成汇编
20条内能实现么？

shshsh_0510 发表于 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
    bsrecx, n
    bsfedx, n
    sub edx, ecx
    adceax, 0
    mov edx, 0
    cmp n, 0
    cmove eax, edx
    shl eax, cl

shshsh_0510 发表于 2009-2-3 17:05:37

大概写了一下，就算示意吧，那个表的数据我就不算了，太麻烦了#include <stdio.h>

typedef unsigned int UINT32;

typedef struct data {
        UINT32 retvalue;
        UINT32 halfdata;
        int type; //0 : directly return ; 1: need to go on
} ITEM_DATA;

ITEM_DATAhash = {
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
        {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0}
};


UINT32GreaterEqualBit2(UINT32 n)
{
        int t1=0,t2=0;
        unsigned char *v= (unsigned char *)&n;
    //find first 2 v that large than zero
        if (v>0) {
                if( hash].type == 0 ) {
                        //3
                        return ( hash].retvalue )<<24;
                } else {
                        if (v>0) {
                                //3,2
                                return ((hash].halfdata)<<24)+((hash].halfdata)<<16);
                        }
                        else {
                                if(v>0) {
                                        //3,1
                                        return ((hash].halfdata)<<24)+((hash].halfdata)<<8);
                                }
                        }
                        //3,0
                        return ((hash].halfdata)<<24)+((hash].halfdata));
                }
        }
        else {
                if(v>0)        {
                        if( hash].type == 0 ) {
                                //2
                                return ( hash].retvalue )<<16;
                        } else {
                                if (v>0)
                                        //2,1
                                        return ((hash].halfdata)<<16)+((hash].halfdata)<<8);
                                else
                                        //2,0
                                        return ((hash].halfdata)<<16)+((hash].halfdata) );
                        }
                }
                else
                        if(v>0) {
                                if( hash].type == 0 )
                                        //1
                                        return ( hash].retvalue )<<8;
                                else
                                        //1,0
                                        return ((hash].halfdata)<<8)+((hash].halfdata) );
                        }
        }
        //0
        returnhash].retvalue ;
}

intmain(int argc, char * argv[]){   
        int i;
        for (i=0x11 ; i<0x111121 ; i++)
                printf(" input %d , output %X \n",i,GreaterEqualBit2(i));
       
    return 0;
}

无心人 发表于 2009-2-3 17:08:45

:lol

   你认为这么复杂的代码比我的汇编要高效么？
   况且，最终的代码的适用范围要比GxQ题目要求的大
   只要是1-(2^31+2^30）就可以

查看完整版本: 求bit位为1数目不超出2的正整数