Chinaunix

标题: 请教一个算法 [打印本页]
作者: heavyrain44    时间: 2007-05-24 09:03
标题: 请教一个算法
我想请教一个算法，有一无符号32位整数，求其右边第一位数起到第一个位为‘1’的0的个数。
如0x21c534a8，则返回3；0x1b94a4c0，则返回6。
用循环好做，但时间复杂度不是常数。有时间复杂度为常数的算法吗，谢谢大家
作者: 疯长的野草    时间: 2007-05-24 09:39
时间复杂度不是常数？什么是实践复杂度啊
作者: cugb_cat    时间: 2007-05-24 09:51
原帖由 疯长的野草 于 2007-5-24 09:39 发表
时间复杂度不是常数？什么是实践复杂度啊

建议你碰到不知道概念先google或看书
作者: ypxing    时间: 2007-05-24 09:58
原帖由 heavyrain44 于 2007-5-24 09:03 发表
我想请教一个算法，有一无符号32位整数，求其右边第一位数起到第一个位为‘1’的0的个数。
如0x21c534a8，则返回3；0x1b94a4c0，则返回6。
用循环好做，但时间复杂度不是常数。有时间复杂度为常数的算法吗，谢谢 ...


不是常数是什么?
你最多需要检查32位
所以是O(1)

楼主是不是说要对n位的整数进行计算?

[ 本帖最后由 ypxing 于 2007-5-24 10:06 编辑 ]
作者: heavyrain44    时间: 2007-05-24 10:13
楼上的那位，您这样说也对，但显然检查0x21c534a8跟检查0x1b94a4c0所需要的时间是不一样的。您所说的时间是常数，只是说最坏的情况下所需要的时间是常数而已。
我希望检查所有数据所需要的时间都是一样的，而且越快越好

[ 本帖最后由 heavyrain44 于 2007-5-24 10:16 编辑 ]
作者: DraculaW    时间: 2007-05-24 10:25
-@- 孩子 好好看书  好好看书 了解下常数的意义

如果你要全部都一样的速度
那么就应该用一个表 然后查表
那肯定是一个常数
就是这个表比较恐怖的大了
作者: DraculaW    时间: 2007-05-24 10:26
一个表 查的话 他的时间就是访问数组里一个元素的时间 很快很快的 不能再快了
作者: cugb_cat    时间: 2007-05-24 10:31
原帖由 DraculaW 于 2007-5-24 10:25 发表
-@- 孩子 好好看书  好好看书 了解下常数的意义

如果你要全部都一样的速度
那么就应该用一个表 然后查表
那肯定是一个常数
就是这个表比较恐怖的大了

呵呵，是啊，哈希表，哈哈
作者: heavyrain44    时间: 2007-05-24 10:36
那个表大的够恐怖的。查表对8位还有意义。16位，32位还是算了吧。把存储单元浪费在这上面，不值得。明显不实用
作者: heavyrain44    时间: 2007-05-24 10:38
还可以把32位拆成4个8位再查表，但我对这个算法也不满意
作者: cugb_cat    时间: 2007-05-24 10:45
总共就那么几位，就算从最低位开始一位一位的扫描，用的时间也是很少的，如果这个是在别的系统中的话，我觉得提高效率应该考虑系统的其他部分。
作者: MMMIX    时间: 2007-05-24 11:41
原帖由 heavyrain44 于 2007-5-24 09:03 发表
我想请教一个算法，有一无符号32位整数，求其右边第一位数起到第一个位为‘1’的0的个数。
如0x21c534a8，则返回3；0x1b94a4c0，则返回6。
用循环好做，但时间复杂度不是常数。有时间复杂度为常数的算法吗，谢谢 ...

先考虑简单的实现，测试一下速度，如果不符合你的要求再考虑优化吧。要不也可以直接在网上搜索较快的算法。
作者: yuxh    时间: 2007-05-24 12:28
可以折半查找，但总共就32位，意义不大。
象这样：

  2.     unsigned int mask = 0x0000ffff;
  3.     for(i=16; i > 0; i >>= 1, mask >>= i)
  4.     {
  5.         if( (n&mask) == 0)
  6.         {
  7.             m += i;
  8.             n >>= i;
  9.         }
  10.     }
  11.     if(n == 0) m++;
  12.     return m;
复制代码

只在理论上成立，实际的效果我很怀疑还不如循环32次
作者: FreeGnu    时间: 2007-05-24 12:29

  2. unsigned int num = 0x12345678;
  3. unsigned int table[32] = {0x00000001, 0x00000002, .....};
  4. do{
  5. if(num & table[0]){
  6.    printf("0\n");
  7.    break;
  8. }
  9. if(num & table[1]){
  10.    printf("1\n");
  11.    break;
  12. }
  13. .......
  14. }while(0);
复制代码

[ 本帖最后由 FreeGnu 于 2007-5-24 12:41 编辑 ]
作者: zenglj    时间: 2007-05-24 15:40
unsigned int num = 0x12345678;
unsigned int count = 0;
while(1)
{
if(num & 0x00000001)
{
   printf("%d\n", count );
   break;
}
num = num>>1;
count++;
}

这样简洁些嘛

[ 本帖最后由 zenglj 于 2007-5-24 15:47 编辑 ]
作者: emacsnw    时间: 2007-05-24 15:48
二分：

  2. int ntz(unsigned x) {
  3.    int n;

  5.    if (x == 0) return(32);
  6.    n = 1;
  7.    if ((x & 0x0000FFFF) == 0) {n = n +16; x = x >>16;}
  8.    if ((x & 0x000000FF) == 0) {n = n + 8; x = x >> 8;}
  9.    if ((x & 0x0000000F) == 0) {n = n + 4; x = x >> 4;}
  10.    if ((x & 0x00000003) == 0) {n = n + 2; x = x >> 2;}
  11.    return n - (x & 1);
  12. }

复制代码
作者: lz_fine    时间: 2007-05-27 22:30
假设该数为x，那么x - (x & (x - 1))就是一个2的冥，然后就再进行处理，比如说取对数(但取对数时间复杂度是不是常数我就不知道了)或者查表(至于怎么设计表格你自己想想或者其他弟兄给个方法)。
作者: SuperZ    时间: 2007-05-27 23:48
这个就要看你在什么机器上跑了，有些机器比较怪异，直接就有这样的指令。
作者: jigloo    时间: 2007-05-28 00:51
考虑到《hackers delight》中的count_ones技巧， 有如下解决办法。


  2. int count_ones(unsigned int x)
  3. {
  4.     x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
  5.     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  6.     x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
  7.     x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
  8.     x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);

  10.     return x;       
  11. }

  13. #define rfind_zeros(x) ((x)?count_ones((x)^((x)-1))-1:32)

  15. int main(void)
  16. {
  17.         int n = 0x1;
  18.         printf("%d\n", rfind_zeros(n));
  19.         return 0;
  20. }
复制代码

[ 本帖最后由 jigloo 于 2007-5-28 01:01 编辑 ]
作者: MMMIX    时间: 2007-05-28 01:11
原帖由 SuperZ 于 2007-5-27 23:48 发表
这个就要看你在什么机器上跑了，有些机器比较怪异，直接就有这样的指令。

对头，直接用汇编实现。
作者: improgrammer    时间: 2007-05-28 11:26
回字有几种写法……
作者: MMMIX    时间: 2007-05-28 12:37
原帖由 improgrammer 于 2007-5-28 11:26 发表
回字有几种写法……

这位知道几种写法？
作者: tyc611    时间: 2007-05-28 22:29
原帖由 emacsnw 于 2007-5-24 15:48 发表
二分：
[code]
int ntz(unsigned x) {
   int n;

   if (x == 0) return(32);
   n = 1;
   if ((x & 0x0000FFFF) == 0) {n = n +16; x = x >>16;}
   if ((x & 0x000000FF) == 0) { ...

不错



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2