一些奇技淫巧

最近在看 Hacker's delight ，把一些觉得有用的小技巧记一下来。

/******/ /******/ /******/ /******/ /******/ /******/

• 把二进制数x的最右边一位1变成0:

  x = x & (x - 1)
  

其中的一个应用是，判断一个正整数是不是2的n次方或者0。

#include <stdio.h>

int
main()
{
  int i = 0;
  for (i = 0; i < 1000; ++i) {
    if ((i & (i - 1)) == 0) {
      printf("%d\n", i);
    }
  }
  return 0;
}

会输出:

0
1
2
4
8
16
32
64
128
256
512

• 求绝对值

假设是32位的整数a，先左移一位,结果记为b，去掉符号位，最右一位是0。再右移31位 ，结果记为d,使得最后一位是符号位，如果a是正数或0，则前面补0，所以c是全0,如果a是 负数，前面补1,所以c是全1。b和c作与运算，结果记为d，这样就使c中的最后一位（a的 符号位）变成了0, 如果c是全0,则d为0,如果c为全1,则d等于b。最后，用a减去d，如果 d是0,则结果是a，因为a是正数或0；如果d是b，因为b是a左移1位得到的，所以b = 2a， 所以a - 2a = -a，因为a是负数，所以-a就是a的绝对值。

#include <stdio.h>
#include <math.h>

inline int 
my_abs(int x)
{
  return x - ((x << 1) & (x >> 31));
}

int
main()
{
  long long i = 0;
  for (i = -2147483647; i < 2147483648; ++i) {
    if (my_abs(i) != abs(i)) {
      printf("%d\n", i);
    }
  }
  return 0;
}

这里没有测试32位整数的最小值，因为-2147483648的绝对值超过了整数的范围。

用系统内置的abs函数比较了一下性能，发现测试完所有的整数，这个函数用了33秒，而 系统函数只用了20秒。加上gcc的-O2优化选项，这个函数用了7秒，而系统函数只用了 0.001秒。