Chinaunix

标题: 如何使用位操作得到大于N且为2的次方的最小的数 [打印本页]
作者: converse    时间: 2008-06-12 15:27
标题: 如何使用位操作得到大于N且为2的次方的最小的数
RT,比如输入10返回16, 输入24返回32,等等.


注意,是使用位操作且没有循环,也不用表驱动等等.
作者: emacsnw    时间: 2008-06-12 15:27
还有一个比较邪恶的：

  2. float f = (float)(v - 1);  
  3. return 1 << ((*(unsigned int*)(&f) >> 23) - 126);
复制代码
作者: seraphsky    时间: 2008-06-12 15:36
#include <iostream.h>
int main()
{   int count ;
    int a;
    cin>>a;
    count =0;
    while(a>=1)
    {
      a/=2;         
      count++;
      }
   
    cout<<(1<<count)<<endl;
    system("pause");
   
    }
作者: converse    时间: 2008-06-12 15:38
标题: 回复 #2 seraphsky 的帖子
我说了 不用循环....否则我不用费力发这个帖子了.
作者: jigloo    时间: 2008-06-12 15:38
汇编吧， bsf/bsr
作者: seraphsky    时间: 2008-06-12 15:45
你确定不用循环可以做么
32->2进制的100000还要循环看下后几位是全为0呢
作者: 5毛党党员    时间: 2008-06-12 15:46
感觉位操作也需要循环。。。。
作者: jigloo    时间: 2008-06-12 16:02
google搜出来了一个


  2.         // Next Largest Power of 2
  3.         // Given a binary integer value x, the next largest power of 2 can be computed by a SWAR algorithm
  4.         // that recursively "folds" the upper bits into the lower bits. This process yields a bit vector with
  5.         // the same most significant 1 as x, but all 1's below it. Adding 1 to that value yields the next
  6.         // largest power of 2. For a 32-bit value:
  7.         inline_ udword        nlpo2(udword x)
  8.         {
  9.                 x |= (x >> 1);
  10.                 x |= (x >> 2);
  11.                 x |= (x >> 4);
  12.                 x |= (x >> 8);
  13.                 x |= (x >> 16);
  14.                 return x+1;
  15.         }
复制代码
作者: dpsuffix    时间: 2008-06-12 16:10
.。。。。。。。。。。。。。。。

[ 本帖最后由 dpsuffix 于 2008-6-12 16:19 编辑 ]
作者: cugb_cat    时间: 2008-06-12 16:17
原帖由 jigloo 于 2008-6-12 16:02 发表
google搜出来了一个


        // Next Largest Power of 2
        // Given a binary integer value x, the next largest power of 2 can be computed by a SWAR algorithm
        // that recursively "folds" the upper bi ...

这也算是查表了吧？
如果这样可以，那我用几个if-else也解决了。
作者: jigloo    时间: 2008-06-12 16:18
毕竟是顺序语句，还是比分支要快点的啊。
当然，最快的还是汇编里的位扫描指令。
作者: 5毛党党员    时间: 2008-06-12 16:25
原帖由 cugb_cat 于 2008-6-12 16:17 发表

这也算是查表了吧？
如果这样可以，那我用几个if-else也解决了。



没错，那个方法和直接和 2，4，8，16比较没什么区别了
作者: W.Z.T    时间: 2008-06-12 16:25
偶这个也行吧：

(int)ldexp(1, (log(x) / log(2)) + 1));
作者: aibyfaku    时间: 2008-06-12 16:26
1<<[n个进制位]，这个n有公式求得吗？
作者: converse    时间: 2008-06-12 16:32
标题: 回复 #7 jigloo 的帖子
你搜索的关键字是?
作者: converse    时间: 2008-06-12 16:33
标题: 回复 #2 emacsnw 的帖子
说说原理吧 看不太懂...
作者: jigloo    时间: 2008-06-12 16:36
一开始我是觉得楼主你的需求跟conutbits那个函数有点像
然后我就在google codesearch搜了一下
然后有Soya的IceUtils.h有这个函数，还带了其他的一些函数。
作者: converse    时间: 2008-06-12 16:38
原帖由 converse 于 2008-6-12 16:33 发表
说说原理吧 看不太懂...


另外,有数字的限制吗?我的意思是,对于>0的数,无论多大都可以返回正确的结果吗?
作者: jigloo    时间: 2008-06-12 16:39
emacsnw那个方法用了浮点，这是邪道啊~~~~
作者: chzht001    时间: 2008-06-12 16:42
原帖由 jigloo 于 2008-6-12 16:02 发表
google搜出来了一个


        // Next Largest Power of 2
        // Given a binary integer value x, the next largest power of 2 can be computed by a SWAR algorithm
        // that recursively "folds" the upper bi ...


我也想到了这个方法：
将最高位1右边的位全部变为1再加1，不过还没想好算法
还没有您快啊已经给出算法了， 赞一个

[ 本帖最后由 chzht001 于 2008-6-12 16:43 编辑 ]
作者: yecheng_110    时间: 2008-06-12 16:54
原帖由 emacsnw 于 2008-6-12 15:27 发表
还有一个比较邪恶的：

float f = (float)(v - 1);  
return 1 > 23) - 126);

这应该是用了float存储格式
作者: emacsnw    时间: 2008-06-12 16:55
嗯，IEEE浮点数格式，大致是取（2的）指数部位处理一下。
作者: chzht001    时间: 2008-06-12 17:10
原帖由 emacsnw 于 2008-6-12 15:27 发表
还有一个比较邪恶的：

float f = (float)(v - 1);  
return 1 > 23) - 126);


神奇， 不用v-1直接用v就好了，要不1就不好算了

请教23和126怎么选出来的？
作者: nbaloverme    时间: 2008-06-12 17:12
不错
用v-1的目的是什么呢？
作者: chzht001    时间: 2008-06-12 17:18
原帖由 emacsnw 于 2008-6-12 16:55 发表
嗯，IEEE浮点数格式，大致是取（2的）指数部位处理一下。


呵呵，明白了，为什么取23和126，呵呵， 能想到这个方法真奇才也， 佩服  
作者: nbaloverme    时间: 2008-06-12 17:25
23表示移去尾数部份
126表示（127-1），具体127表示什么意思察看浮点数的存储格式
作者: emacsnw    时间: 2008-06-12 17:26
原帖由 chzht001 于 2008-6-12 01:18 发表


呵呵，明白了，为什么取23和126，呵呵， 能想到这个方法真奇才也， 佩服  


不是我想出来的。。。网上有。
作者: 拉东    时间: 2008-06-12 17:49
偶的方法是通过递归取到数据的最高位的1所在的offset，然后给出1<<(offset+1)。

代码就不贴了.
作者: converse    时间: 2008-06-12 18:48
标题: 回复 #28 拉东 的帖子
递归和循环是一个本质.
作者: nicozhou    时间: 2008-06-12 19:41
做个记号。
作者: flw    时间: 2008-06-12 19:42
原帖由 jigloo 于 2008-6-12 15:38 发表
汇编吧， bsf/bsr

同意这个答案。
  1. flw@debian:~/study$ cat ttt.c
  2. # include <stdio.h>

  4. # define foo(a,b)           \
  5. __asm__(                    \
  6.     "bsr %%eax, %%ecx\n\t"  \
  7.     "inc %%ecx\n\t"         \
  8.     "mov $1, %%ebx\n\t"     \
  9.     "shll %%cl, %%ebx"      \
  10. :"=b"(b):"a"(a),"c"(0) )

  12. int main( void )
  13. {
  14.     int i, a, b;

  16.     a = 3;
  17.     for( i=0; i<20; i++ ){
  18.         foo( a, b );
  19.         printf( "a: [%d] b: [%d]\n", a, b );
  20.         a <<= 1;
  21.     }

  23.     return 0;
  24. }
  25. flw@debian:~/study$ cc -Wall -o ttt ttt.c
  26. flw@debian:~/study$ ./ttt
  27. a: [3] b: [4]
  28. a: [6] b: [8]
  29. a: [12] b: [16]
  30. a: [24] b: [32]
  31. a: [48] b: [64]
  32. a: [96] b: [128]
  33. a: [192] b: [256]
  34. a: [384] b: [512]
  35. a: [768] b: [1024]
  36. a: [1536] b: [2048]
  37. a: [3072] b: [4096]
  38. a: [6144] b: [8192]
  39. a: [12288] b: [16384]
  40. a: [24576] b: [32768]
  41. a: [49152] b: [65536]
  42. a: [98304] b: [131072]
  43. a: [196608] b: [262144]
  44. a: [393216] b: [524288]
  45. a: [786432] b: [1048576]
  46. a: [1572864] b: [2097152]
  47. flw@debian:~/study$
复制代码

用浮点数那个，还不如用循环呢。

[ 本帖最后由 flw 于 2008-6-12 19:44 编辑 ]
作者: UnixStudier    时间: 2008-06-12 21:05
好，收藏了。
作者: wolfkin    时间: 2008-06-12 22:56
a=a|(a>>1);
a=a|(a>>2);
a=a|(a>>4);
a=a|(a>>;
a=a|(a>>16);
a=a|(a>>32);
it can do for 64-bit data.
作者: yuanchuang    时间: 2008-06-17 10:27
原帖由 jigloo 于 6-12-2008 16:02 发表
google搜出来了一个


        // Next Largest Power of 2
        // Given a binary integer value x, the next largest power of 2 can be computed by a SWAR algorithm
        // that recursively "folds" the upper bi ...

顶这一种。
用内联汇编，感觉效率也不高多少，不过不可移植，如果是产品中，还可能会遭到大部分人反对。
这个题目是个很有用的功能，vector就是这样增长的。
作者: yanjun1    时间: 2008-06-27 13:52
这个可能对lz没什么帮助，这个是用来做对齐的

#define MEM_MINI_CHUNK_SIZE 64

#define MEM_CHUNK(x) \
        (MEM_MINI_CHUNK_SIZE - ( ( x ) % MEM_MINI_CHUNK_SIZE )



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