Chinaunix

标题: 求一个整数是2的多少次方的算法 [打印本页]
作者: changsha    时间: 2015-08-28 13:03
标题: 求一个整数是2的多少次方的算法
  1. #include <stdio.h>
  2. #include <time.h>

  4. #ifdef __BBO

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

  20. #else

  22. #define BIT_1_POS(__value, __ret) { \
  23.   int __i = 0; \
  24.   for (unsigned long __n = __value; __n != 0; ++__i) __n >>= 1; \
  25.   __ret = __i; \
  26. }

  28. #endif // 0

  30. int main() {
  31.   unsigned pos;
  32.   struct timespec tp0, tp1;
  33.   clock_gettime(CLOCK_REALTIME, &tp0);
  34.   for (int i = 0; i < 1000000; ++i) {
  35.     unsigned long n = (1L<<63);
  36.     while (n) {
  37.       BIT_1_POS(n, pos);
  38.       // BIT_1_POS(1<<4, pos);
  39.       n >>= 1;
  40.     }
  41.     BIT_1_POS(n, pos);
  42.   }
  43.   clock_gettime(CLOCK_REALTIME, &tp1);

  45.   tp1.tv_sec -= tp0.tv_sec;
  46.   if (tp1.tv_nsec >= tp0.tv_nsec) {
  47.     tp1.tv_nsec -= tp0.tv_nsec;
  48.   } else {
  49.     tp1.tv_sec--;
  50.     tp1.tv_nsec += 1000000000 - tp0.tv_nsec;
  51.   }
  52.   printf("elsp. time: %li.%09li\n", (long)tp1.tv_sec, (long)tp1.tv_nsec);
  53. }
复制代码
作者: changsha    时间: 2015-08-28 13:05
本帖最后由 changsha 于 2015-08-28 13:06 编辑

二分算法比简单for循环效率高不少
作者: Dannysd    时间: 2015-08-28 14:44
本帖最后由 Dannysd 于 2015-08-28 16:10 编辑
  1. #include<stdio.h>
  2. #include<stdlib.h>

  4. int log_2(int value);

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

  16. int main(int argc, char **argv)
  17. {  
  18.         int num;

  20.         printf("输入一个整数：");

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

  24.         if(num <= 0) {  //补充
  25.                 printf("%d，输入非法\n", num);
  26.                 return -1;
  27.         }

  29.         if(num & (num-1)) {
  30.                 printf("%d不是2的幂次方！\n", num);
  31.         }
  32.         else {
  33.                 printf("%d是2的%d次方！\n", num, log_2(num));
  34.         }

  36.         return 0;
  37. }
复制代码
作者: bruceteen    时间: 2015-08-28 15:16
为什么不直接用 bsr 函数（bit scan reverse）?
虽然 C/C++ 中没有，但 汇编、gcc、vc 中都有
作者: serenemoon    时间: 2015-08-28 15:17
回复 3# Dannysd


    you missed 0.
    given 0, you program will crash.
作者: soul11201    时间: 2015-08-28 16:02
提示: 作者被禁止或删除 内容自动屏蔽
作者: Dannysd    时间: 2015-08-28 16:07
回复 5# serenemoon


    谢谢serenemoon提醒，哈哈，真是忘记做判断了
作者: seanking1987    时间: 2015-08-28 17:12
还是看三楼的代码舒服些
作者: lost_templar    时间: 2015-08-28 17:57
  1. uint32_t v; // find the log base 2 of 32-bit v
  2. int r;      // result goes here

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

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

  16. r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];
复制代码
这么老的代码，网上到处都是
作者: soul11201    时间: 2015-08-28 19:42
提示: 作者被禁止或删除 内容自动屏蔽
作者: changsha    时间: 2015-08-28 21:16
还是汇编最快



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