高效的位运算

位运算是基于整数的二进制运算，由于计算机内以二进制存储数据，所以按位运算的速度是很快的。

按位运算主要有6种，按位与&、按位或|、按位异或^、按位取反~、按位左移<<、按位右移>>。

按位与

static void Main(){
    int a = 10;//1010
    int b = 7; //0111
    Console.WriteLine(a&b);//0010 = 2
}

按位或

static void Main(){
    int a = 10;//1010
    int b = 7; //0111
    Console.WriteLine(a|b);//1111 = 15
}

按位异或

static void Main(){
    int a = 10;//1010
    int b = 7; //0111
    Console.WriteLine(a^b);//1101 = 13
}

按位取反

static void Main(){
    byte a = 10;//0000 1010
    Console.WriteLine((byte)~a);//1111 0101 = 225-10 = 245
}

按位左移或右移

static void Main(){
    byte a = 10;//0000 1010
    Console.WriteLine(a>>2);//0000 0010 = 2 
    Console.WriteLine(a<<2);//0010 1000 = 40 
}

在C#中，如果按位运算的双目（按位取反为单目）长度小于32位，运算结果为32位。如byte、sbyte、short、ushort任意组合运算结果都是int类型，int和uint运算结果为long类型。而long和ulong不能够直接按位运算。

通过上面的计算我们可以发现，

a^b + a&b = a|b，

a = a^b^b = a|(b^b)

按位运算的应用

1. 乘以或者除以2的非负整数次幂

   static int MulPowerOfTwo(int n,int m){
       return n<<m;
   }
   static int DivPowerOfTwo(int n,int m){
       return n>>m;
   }

2. 判断一个数是不是能被2整除

   static bool IsPowerOfTwo(int n){
   	return n > 0 && (n & (n - 1)) == 0;
   }

3. 对 2 的非负整数次幂取模

   static int ModPowerOfTwo(int n,int mod){
       return n & (mod-1);
   }

4. 取绝对值

   static int Abs(int n) {
     return (n ^ (n >> 31)) - (n >> 31);
     /* n>>31 取得 n 的符号，若 n 为正数，n>>31 等于 0，若 n 为负数，n>>31 等于 -1
        若 n 为正数 n^0=n, 数不变，若 n 为负数有 n^(-1)
        需要计算 n 和 -1 的补码，然后进行异或运算，
        结果 n 变号并且为 n 的绝对值减 1，再减去 -1 就是绝对值 */
   }

5. 取两个数的最大/最小值

   static int Max(int a, int b) { 
       return b & ((a - b) >> 31) | a & (~(a - b) >> 31); 
   }
   static int Min(int a, int b) { 
       return a & ((a - b) >> 31) | b & (~(a - b) >> 31); 
   }

6. 判断符号是否相同

   static bool IsSameSign(int x, int y) {  // 有 0 的情况例外
     return (x ^ y) >= 0;
   }

7. 交换两个数

   static void Swap(ref int a, ref int b) 
   {
       a = a^b;
       b = a^b;
       a = a^b;
   }

8. 获取一个数二进制的某一位

   static int GetBit(int a, int b) 
   { 
       return (a >> b) & 1; 
   }

9. 将一个数二进制的某一位设置为 0

   static int UnsetBit(int a, int b) 
   { 
       return a & ~(1 << b); 
   }

10. 将一个数二进制的某一位设置为 1

    static int SetBit(int a, int b) 
    { 
        return a | (1 << b); 
    }

11. 将一个数二进制的某一位取反

    static int FlapBit(int a, int b) 
    { 
        return a ^ (1 << b); 
    }