Chinaunix

标题: 如何求解一个无符号整形数是2的多少次方？ [打印本页]
作者: zbhddt6    时间: 2010-07-31 21:36
标题: 如何求解一个无符号整形数是2的多少次方？
就是一个unsigned整形数据只有一个bit位为1；求这个bit的位置；

问题背景，我用一个无符号整形数映射一个32个key值的使用情况；
现在需要求从后向前数，第一个0的bit位，用此bit生成一个特定的键值，键值本身有序；
所以我必须知道0bit位最低的那个字节，而且一定存在这个bit；

if (0xffffffff == unsignedi) return;

unsignedi = ~unsignedi;  转化为求从后向前数最低的一个为1的bit位；
unsignedj = unsignedi - (unsignedi & (unsignedi -1));
//如何继续进行计算unsignedj 对应bit的位置；------我不想一个一个bit找或者二分查找~~~
否则一开始就从后向前一个一个bit查找好的了~~~~~
作者: bruceteen    时间: 2010-08-01 10:45
本帖最后由 bruceteen 于 2010-08-01 11:41 编辑

你觉得 bsf bsr 这两个汇编指令怎么样？

假如你必须用C的话，可以折半查找，比如
((a&0xFFFF0000!=0) ? 16 : 0)
| ((a&0xFF00FF00!=0) ? 8 : 0)
| ((a&0xF0F0F0F0!=0) ? 4 : 0)
| ((a&0xCCCCCCC!=0) ? 2 : 0)
| ((a&0xAAAAAAAA!=0) ? 1 : 0)
作者: sep    时间: 2010-08-01 11:18
你觉得 bsf bsr 这两个汇编指令怎么样？

假如你必须用C的话，可以折半查找，比如
((a&0xFFFF0000!=0) ? ...
bruceteen 发表于 2010-08-01 10:45



    Mark
作者: daybreakcx    时间: 2010-08-01 11:23
  1. #include <string.h>
  2. int ffs(unsigned int i);
复制代码
这个可以不
作者: bruceteen    时间: 2010-08-01 11:51
这个可以不
daybreakcx 发表于 2010-08-01 11:23

类似于 _BitScanForward, _BitScanForward64 等其实就是 bsf 汇编指令，加上某个编译指令时，直接就用bsf替代了
作者: zbhddt6    时间: 2010-08-01 15:34
[quote]你觉得 bsf bsr 这两个汇编指令怎么样？

假如你必须用C的话，可以折半查找，比如
((a&0xFFFF0000!=0) ? ...
bruceteen 发表于 2010-08-01 10:45 [/quote]

蛮不错的，谢谢你；只是我不打算二分，也不打算一个一个找，就想看看有没有什么特殊的指令或者运算能达到此目的~~~~
作者: zbhddt6    时间: 2010-08-01 15:39
这个可以不
daybreakcx 发表于 2010-08-01 11:23



    就是为了效率，不会调用函数的，看来也只有汇编的效率要高的了，否则只能使用二分法~~~~~~~
作者: daybreakcx    时间: 2010-08-01 15:57
就是为了效率，不会调用函数的，看来也只有汇编的效率要高的了，否则只能使用二分法~~~~~~~
zbhddt6 发表于 2010-08-01 15:39
  1. #ifndef _FFS_H_
  2. #define _FFS_H_

  4. /*
  5. * A really hacky implementation copied from asm/bitops.h
  6. * to make it compile
  7. */
  8. inline int ffs(int x)
  9. {
  10.         int r = 1;

  12.         if (!x)
  13.                 return 0;
  14.         if (!(x & 0xffff)) {
  15.                 x >>= 16;
  16.                 r += 16;
  17.         }
  18.         if (!(x & 0xff)) {
  19.                 x >>= 8;
  20.                 r += 8;
  21.         }
  22.         if (!(x & 0xf)) {
  23.                 x >>= 4;
  24.                 r += 4;
  25.         }
  26.         if (!(x & 3)) {
  27.                 x >>= 2;
  28.                 r += 2;
  29.         }
  30.         if (!(x & 1)) {
  31.                 x >>= 1;
  32.                 r += 1;
  33.         }
  34.         return r;
  35. }

  37. #endif
复制代码
网上找的ffs的实现，个人觉得方法很巧，效率不错…………
作者: zbhddt6    时间: 2010-08-01 21:34
网上找的ffs的实现，个人觉得方法很巧，效率不错…………
daybreakcx 发表于 2010-08-01 15:57



    此二分法写的不错~~~~~~
作者: davelv    时间: 2010-08-02 09:46
你觉得 bsf bsr 这两个汇编指令怎么样？

假如你必须用C的话，可以折半查找，比如
((a&0xFFFF0000!=0) ? ...
bruceteen 发表于 2010-08-01 10:45


果真好指令
作者: ahui886    时间: 2010-08-02 10:26
glibc 的一个ffs实现
  1. int ffs ( int i)
  2. {
  3.   static const unsigned char table[] =
  4.     {
  5.       0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
  6.       6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  7.       7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  8.       7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  9.       8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  10.       8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  11.       8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  12.       8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
  13.     };
  14.   unsigned int a;
  15.   unsigned int x = i & -i;

  17.   a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ?  16 : 24);

  19.   return table[x >> a] + a;
  20. }
复制代码
作者: zylthinking    时间: 2010-08-02 10:39
mark
作者: zhangsuozhu    时间: 2010-08-02 14:49
如果只有一个bit位为1可以省一步运算 unsigned int x = i & -i;

  2. unsigned int ffs(unsigned i)
  3. {
  4.   static const unsigned char table[] =
  5.     {
  6.       0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
  7.       6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  8.       7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  9.       7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  10.       8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  11.       8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  12.       8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  13.       8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
  14.     };

  16.   int x = i <= 0xffff ? (i <= 0xff ? 0 : 8) : (i <= 0xffffff ?  16 : 24);
  17.   return table[i>>x]+x;
  18. }
复制代码
作者: davelv    时间: 2010-08-02 16:08
如果只有一个bit位为1可以省一步运算 unsigned int x = i & -i;
zhangsuozhu 发表于 2010-08-02 14:49

这个的结果是 x==i

看错了，抱歉。



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