位运算的一些总结和技巧

引子：《程序员面试宝典》2C的P37的面试例题中有这样一道题：

unsigned char a = oxA5;
unsigned char b=~a>>4;
printf("%d",b);

书上给的答案是正确的，但是讲解是错误的：“>>”的优先级高于“~”。这个题作者之所以能够歪打正着的作对最后的结果，是因为在位运算中，不存8位的位运算，（X86，VC9以及GCC的编译环境中）编译器会把这个8位的字符提升为32位进行运算(实验结果，未找到文献)。

先给出一些位运算的一些应用：

1.补齐至某个数的倍数

stl里面的二级空间配置器里，对于小内存的分配是有独特的策略的(详见侯捷：《STL源码剖析》)，当申请的内存小于128字节的时候，会将这个内存大小提升为8的倍数，例如申请的内存是7个字节，那么配置器会把这个内存提升为8个字节。那么你将会怎么写这个简单的补齐至某个数的倍数函数呢？

enum {_ALLGN=8};

static size_t ROUND_UP(size_t BYTES)
{
      return (BYTES+_ALLGN-1) & ~(_ALLGN-1);
}

仔细想想，这是为什么？

2.计算一个二进制串中“1”的个数(详见《编程之美》P119)

int Count_1(unsigned char i){
   int count=0;
   while(i!=0)
   {
        count+=i & 0x01;
        i>>=1; 
   }
   return count;
}

将二进制数与1进行&操作，能判断出最后一位是否为1。用这个方法也能判断出这个数的奇偶性，不再详述。

这个题在编程之美上还有更好的解法,算法复杂度只与1的个数相关:

想法引导：n如果只剩下一个“1” <--> n是2的m(m=0,1,2...ln n)次幂 <-->n&(n-1)==1

int count_1(unsigned char a)
{
     int count=0;
     while(a!=0)
     {
          a&=(a-1);
          count++;
     }
     return count;
}