C++位运算

张乐凡 · 2024 年9 月 28 日 05:46

在我们第一次接触c++时，肯定做过这样的题
输入一个数，若这个数是奇数，则输出1，否则输出0

cout<<n%2;
//用时约0.3s

但也可以这样写：

cout<<(n&1);
//用时约0.2s

可以发现，第二种写法明显优于第一种，这就要提到位运算了。

什么是位运算

位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。

基本的位运算共6种，分别为按位与、按位或、按位异或、按位取反、左移和右移。

按位取反是最简单的位运算，将原数化为二进制，在将1变0，0变1，就可以得到最终结果.

与：只有两个值都为1时才为1.
或：只要两个值中有一个1时就为1
异或：只有两个值不同时才为 1
要求按位与，按位或，按位异或时可以使用转二进制+竖式的方法.
例：求7和11的按位与.
第一步：转二进制
7_{10}=111_2
11_{10}=1011_2
第二步：竖式计算

1011
0111
----
0011

第三步：转十进制
11_2=3_{10}
所以7按位与11为3

左移i表示将原数的二进制向左移动i位，再到末位补0所得的值。
右移i表示将原数的二进制向右移动位i所得的值。
例：求12左移2
12_10=1100_2
左移2，补0
1100_2<<2=110000_2
换回十进制
110000_2=18_{10}

int cheng(int n, int m) {  //计算n*(2^m)
    return n<<m;
}
int chu(int n, int m){  //计算n/(2^m)
    return n>>m;
}

int Abs(int n) {
    return (n^(n>>31))-(n>>31);
}

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

void swap(int &a,int &b){ a^=b^=a^= b; }