• 位运算是把数字用二进制表示之后，对每一位上0 或者1 的运算。
    • image.png
    • 右移时处理最左边位的情形要稍微复杂一点。如果数字是一个无符号数值，则用0填补最左边的n位。如果数字是一个有符号数值，则用数字的符号位填补最左边的n位。也就是说如果数字原先是一个正数，则右移之后在最左边补n个0；如果数字原先是负数，则右移之后在最左边补n个1。
    • image.png

    请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如把9表示成二进制是1001，有2位是1。因此如果输入9，该函数输出2。

    • 可能引起死循环的解法

    右移判断最右一位是否为1

    1. int NumberOf1(int n)
    2. {
    3.     int count = 0;
    4.     while(n)
    5.     {
    6.         if(n&1)
    7.             count++;
    8.         n = n>>1;
    10.         return count;
    11.     }
    12. }
    • 右移来说，对于是有符号的数，将会不断循环下去

    把整数右移一位和把整数除以 2 在数学上是等价的，那上面的代码中可以把右移运算换成除以 2 吗？答案是否定的。因为除法的效率比移位运算要低得多，在实际编程中应尽可能地用移位运算符代替乘除法。

    • 为了避免死循环，我们可以不右移输入的数字i。首先把i和1做与运算，判断i的最低位是不是为1。接着把1左移一位得到2，再和i做与运算，就能判断i的次低位是不是1……这样反复左移，每次都能判断i的其中一位是不是1。

      1. int NumberOf1(int n)
      2. {
      3.   int count = 0;
      4.   unsigned int flag = 1;        //这样要保证flag和输入数据的bit数是一致的(>=关系)
      5.   while(flag){
      6.       if(n & flag)
      7.           count++;
      8.       flag = flag<<1;
      9.   }
      10.   return count;
      11. }

    • 把一个整数减去1，都是把最右边的1变成0。如果它的右边还有0的话，所有的0都变成1，而它左边所有位都保持不变。接下来我们把一个整数和它减去 1 的结果做位与运算，相当于把它最右边的1变成0。

    • 把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0。那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。

      1. int NumberOf1(int n)
      2. {
      3.   int count = 0;
      5.   while(n)
      6.   {
      7.       ++count;
      8.       n = n & (n-1);
      9.   }
      10.   return count;
      11. }

    用一条语句判断一个整数是不是2的整数次方。一个整数如果是2的整数次方，那么它的二进制表示中有且只有一位是1，而其他所有位都是0。根据前面的分析，把这个整数减去1之后再和它自己做与运算，这个整数中唯一的1就会变成0。

    1. if(n & (n-1))
    2.     printf("n:%d 是2的整数次方",n);

    输入两个整数m和n，计算需要改变m的二进制表示中的多少位才能得到 n。比如 10 的二进制表示为 1010，13 的二进制表示为1101，需要改变1010中的3位才能得到1101。我们可以分为两步解决这个问题：第一步求这两个数的异或，第二步统计异或结果中1的位数。

    1. int ChangeBitNumber(int m, int n)
    2. {
    3.     unsigned int iXor = 0;
    4.     int iNum = 0;
    6.     iXor = m ^ n;        //异或：不相同bit为1
    7.     while(iXor){
    8.         ++iNum;
    9.         iXor = iXor & (iXor -1);
    10.     }
    11.     return iNum;
    12. }

    把一个整数减去 1 之后再和原来的整数做位与运算，得到的结果相当于是把整数的二进制表示中的最右边一个1变成0。
    **

    • 数据结构题目一直是面试官考查的重点。数组和字符串是两种最基本的数据结构。链表应该是面试题中使用频率最高的一种数据结构。
    • 算法是面试官喜欢考查的另外一个重点。查找（特别是二分查找）和排序（特别是快速排序和归并排序）是面试中最经常考查的算法，应聘者一定要熟练掌握。
    • 熟练掌握了二进制的与、或、异或运算及左移、右移操作，就能解决与位运算相关的面试题（& | ^ << >>）