高效的位运算
高效的位运算
位运算是基于整数的二进制运算,由于计算机内以二进制存储数据,所以按位运算的速度是很快的。
按位运算主要有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)
按位运算的应用
乘以或者除以2的非负整数次幂
static int MulPowerOfTwo(int n,int m){ return n<<m; } static int DivPowerOfTwo(int n,int m){ return n>>m; }
判断一个数是不是能被2整除
static bool IsPowerOfTwo(int n){ return n > 0 && (n & (n - 1)) == 0; }
对 2 的非负整数次幂取模
static int ModPowerOfTwo(int n,int mod){ return n & (mod-1); }
取绝对值
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 就是绝对值 */ }
取两个数的最大/最小值
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); }
判断符号是否相同
static bool IsSameSign(int x, int y) { // 有 0 的情况例外 return (x ^ y) >= 0; }
交换两个数
static void Swap(ref int a, ref int b) { a = a^b; b = a^b; a = a^b; }
获取一个数二进制的某一位
static int GetBit(int a, int b) { return (a >> b) & 1; }
将一个数二进制的某一位设置为 0
static int UnsetBit(int a, int b) { return a & ~(1 << b); }
将一个数二进制的某一位设置为 1
static int SetBit(int a, int b) { return a | (1 << b); }
将一个数二进制的某一位取反
static int FlapBit(int a, int b) { return a ^ (1 << b); }
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!