Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1676887
  • 博文数量: 184
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2388
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(184)

文章存档

2021年(26)

2020年(56)

2019年(54)

2018年(47)

2017年(1)

我的朋友

分类: C/C++

2021-06-26 09:54:12

之前看极课时间的公开课,其中有几个函数个人觉得比较牛,在这里分享一波
1. 一次牛顿迭代求平方根
这个不想多谈,神奇的常数,存储转换都用到了。。。

点击(此处)折叠或打开

  1. float Q_rsqrt( float number )

  2. {

  3. long i;

  4. float x2, y;

  5. const float threehalfs = 1.5F;

  6. x2 = number * 0.5F;

  7. y = number;

  8. i = * ( long * ) &y; // evil floating point bit level hacking

  9. i = 0x5f3759df - ( i >> 1 ); // what the fuck?

  10. y = * ( float * ) &i;

  11. y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration

  12. // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

  13. #ifndef Q3_VM

  14. #ifdef __linux__

  15. assert( !isnan(y) ); // bk010122 - FPE?

  16. #endif

  17. #endif

  18. return y;

  19. }

2. 常数时间复杂度求整数二进制表示当中1的个数
这个可以简单说下,相当于从左到右依次2、4、8、16分割,然后每组求和,最终的出结果

点击(此处)折叠或打开

  1. int count_ones(int x){
  2.     x = (x & 0x55555555) + ((x & 0xAAAAAAAA) >> 1);
  3.     x = (x & 0x33333333) + ((x & 0xCCCCCCCC) >> 2);
  4.     x = (x & 0x0F0F0F0F) + ((x & 0xF0F0F0F0) >> 4);
  5.     x = (x & 0x00FF00FF) + ((x & 0xFF00FF00) >> 8);
  6.     x = (x & 0x0000FFFF) + ((x & 0xFFFF0000) >> 16);
  7.     return x;
  8. }




3. 求一个整数,二进制表示当中,是1的最低有效位(也就是末尾连续0的数量)
这个我是只能想到(x-1)^x&x,然后查表即可,这里利用了取反(负数二进制补码表示)然后用到了De Bruijn序列、汉密尔顿回路、欧拉回路。。。。

点击(此处)折叠或打开

  1. unsigned int v; // find the number of trailing zeros in 32-bit v
  2. int r; // result goes here
  3. static const int MultiplyDeBruijnBitPosition[32] =
  4. {
  5. 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
  6. 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  7. };
  8. r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];


路还很长,各位公勉~
阅读(462) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~