免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 6016 | 回复: 10

[C] 求一个整数是2的多少次方的算法 [复制链接]

论坛徽章:
0
发表于 2015-08-28 13:03 |显示全部楼层
  1. #include <stdio.h>
  2. #include <time.h>

  3. #ifdef __BBO

  4. #define BIT_1_POS(__value, __ret) { \
  5.   unsigned long __n = __value; \
  6.   unsigned __lg = 0; \
  7.   if (__n > 0x80000000) { __lg += 32; __n >>= 32; } \
  8.   if (__n > 0x8000) { __lg += 16; __n >>= 16; } \
  9.   if (__n > 0x80) { __lg += 8; __n >>= 8; } \
  10.   if (__n > 8) { __lg += 4; __n >>= 4; } \
  11.   if (__n == 8) __lg += 4; \
  12.   else if (__n == 4) __lg += 3; \
  13.   else if (__n == 2) __lg += 2; \
  14.   else if (__n == 1) __lg += 1; \
  15.   __ret = __lg; \
  16. }

  17. #else

  18. #define BIT_1_POS(__value, __ret) { \
  19.   int __i = 0; \
  20.   for (unsigned long __n = __value; __n != 0; ++__i) __n >>= 1; \
  21.   __ret = __i; \
  22. }

  23. #endif // 0

  24. int main() {
  25.   unsigned pos;
  26.   struct timespec tp0, tp1;
  27.   clock_gettime(CLOCK_REALTIME, &tp0);
  28.   for (int i = 0; i < 1000000; ++i) {
  29.     unsigned long n = (1L<<63);
  30.     while (n) {
  31.       BIT_1_POS(n, pos);
  32.       // BIT_1_POS(1<<4, pos);
  33.       n >>= 1;
  34.     }
  35.     BIT_1_POS(n, pos);
  36.   }
  37.   clock_gettime(CLOCK_REALTIME, &tp1);

  38.   tp1.tv_sec -= tp0.tv_sec;
  39.   if (tp1.tv_nsec >= tp0.tv_nsec) {
  40.     tp1.tv_nsec -= tp0.tv_nsec;
  41.   } else {
  42.     tp1.tv_sec--;
  43.     tp1.tv_nsec += 1000000000 - tp0.tv_nsec;
  44.   }
  45.   printf("elsp. time: %li.%09li\n", (long)tp1.tv_sec, (long)tp1.tv_nsec);
  46. }
复制代码

论坛徽章:
0
发表于 2015-08-28 13:05 |显示全部楼层
本帖最后由 changsha 于 2015-08-28 13:06 编辑

二分算法比简单for循环效率高不少

论坛徽章:
6
酉鸡
日期:2013-11-04 15:30:02巳蛇
日期:2014-01-23 10:36:23双鱼座
日期:2014-01-23 13:08:332015亚冠之鹿岛鹿角
日期:2015-09-03 14:36:002015亚冠之武里南联
日期:2015-09-18 10:48:1315-16赛季CBA联赛之山西
日期:2016-05-05 00:05:33
发表于 2015-08-28 14:44 |显示全部楼层
本帖最后由 Dannysd 于 2015-08-28 16:10 编辑
  1. #include<stdio.h>
  2. #include<stdlib.h>

  3. int log_2(int value);

  4. int log_2(int value)
  5. {
  6.         if (value == 1)  {
  7.                 return 0;  
  8.         }
  9.         else {
  10.                 return 1+log_2(value>>1);
  11.         }
  12. }  

  13. int main(int argc, char **argv)
  14. {  
  15.         int num;

  16.         printf("输入一个整数:");

  17.         scanf("%d", &num);

  18.         if(num <= 0) {  //补充
  19.                 printf("%d,输入非法\n", num);
  20.                 return -1;
  21.         }

  22.         if(num & (num-1)) {
  23.                 printf("%d不是2的幂次方!\n", num);
  24.         }
  25.         else {
  26.                 printf("%d是2的%d次方!\n", num, log_2(num));
  27.         }

  28.         return 0;
  29. }
复制代码

论坛徽章:
14
巨蟹座
日期:2013-11-19 14:09:4615-16赛季CBA联赛之青岛
日期:2016-07-05 12:36:0515-16赛季CBA联赛之广东
日期:2016-06-29 11:45:542015亚冠之全北现代
日期:2015-07-22 08:09:472015年辞旧岁徽章
日期:2015-03-03 16:54:15巨蟹座
日期:2014-12-29 08:22:29射手座
日期:2014-12-05 08:20:39狮子座
日期:2014-11-05 12:33:52寅虎
日期:2014-08-13 09:01:31巳蛇
日期:2014-06-16 16:29:52技术图书徽章
日期:2014-04-15 08:44:01天蝎座
日期:2014-03-11 13:06:45
发表于 2015-08-28 15:16 |显示全部楼层
为什么不直接用 bsr 函数(bit scan reverse)?
虽然 C/C++ 中没有,但 汇编、gcc、vc 中都有

论坛徽章:
0
发表于 2015-08-28 15:17 |显示全部楼层
回复 3# Dannysd


    you missed 0.
    given 0, you program will crash.
soul11201 该用户已被删除
发表于 2015-08-28 16:02 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

论坛徽章:
6
酉鸡
日期:2013-11-04 15:30:02巳蛇
日期:2014-01-23 10:36:23双鱼座
日期:2014-01-23 13:08:332015亚冠之鹿岛鹿角
日期:2015-09-03 14:36:002015亚冠之武里南联
日期:2015-09-18 10:48:1315-16赛季CBA联赛之山西
日期:2016-05-05 00:05:33
发表于 2015-08-28 16:07 |显示全部楼层
回复 5# serenemoon


    谢谢serenemoon提醒,哈哈,真是忘记做判断了

论坛徽章:
5
金牛座
日期:2015-07-03 13:32:00卯兔
日期:2015-07-03 13:32:17程序设计版块每日发帖之星
日期:2015-11-29 06:20:0015-16赛季CBA联赛之同曦
日期:2015-12-15 09:36:06CU十四周年纪念徽章
日期:2016-07-06 17:18:48
发表于 2015-08-28 17:12 |显示全部楼层
还是看三楼的代码舒服些

论坛徽章:
1
2015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2015-08-28 17:57 |显示全部楼层
  1. uint32_t v; // find the log base 2 of 32-bit v
  2. int r;      // result goes here

  3. static const int MultiplyDeBruijnBitPosition[32] =
  4. {
  5.   0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
  6.   8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
  7. };

  8. v |= v >> 1; // first round down to one less than a power of 2
  9. v |= v >> 2;
  10. v |= v >> 4;
  11. v |= v >> 8;
  12. v |= v >> 16;

  13. r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];
复制代码
这么老的代码,网上到处都是
soul11201 该用户已被删除
发表于 2015-08-28 19:42 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP