高效的位运算

高效的位运算

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

按位运算主要有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位。如bytesbyteshortushort任意组合运算结果都是int类型,intuint运算结果为long类型。而longulong不能够直接按位运算。

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

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); 
    }

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!