位运算（更新中）
一、基础知识
1.基础位运算
<< 左移操作符 &按位与 有0就是0
>>右移操作符 | 按位或 有1就是1
~按位取反 ^异或 相同为1，相异为0 / 无进位相加
例如 1 0 1 1 0 1 ^
1 1 0 1 1 0
结果为 0 1 1 0 1 1，无进位相加就是1 + 0 = 0，1+1 = 0，但是不会向高位进位
2.给一个数n，确定它的二进制表示中的第x位是0还是1
我们规定从右往左，的位数为第0，1，2，3，4，5.....31位
这样右移动的距离等于它的位数
(n >> x) & 1 -> 0 ------ 0
1 ------ 1
3.将一个数n的二进制表示的第x位修改成1
n = n | (1 << x)
4.将一个数n的二进制表示的第n位修改成0
n = n &(~(1 << x))
5.位图的思想
每个比特位0或者1的数值表示一种状态
6.提取一个数n，二进制表示中最右侧的1
lowbit = n & -n(取反加一即变为负)
7.将一个数n二进制表示中最右侧的1抹去
n = n & (n - 1)
8.位运算的优先级
能加括号就加括号
9.异或 ^,运算的运算律
1.a ^ a = 0
2.a ^ 0 = a
3.a ^ b ^ c = a ^ (b ^ c)
二、基础题目示例
1.位1的个数
. - 力扣（LeetCode）
class Solution {
public:int hammingWeight(int i) {int ret = 0;int n = 32;while(n > 0){if((i & 1) == 1)ret++;i = i >> 1;n--;}return ret;}
};将要判断的数每次按位与1，若为1则此位为1，然后再右移一位
2.比特位计数
. - 力扣（LeetCode）
class Solution {
public:int Add(int i){int ret = 0;int n = 32;while(n > 0){if((i & 1) == 1)ret++;i = i >> 1;n--;}return ret;}vector<int> countBits(int n) {vector<int>ret(n+1,0);for(int i = 0; i <= n;i++){ret[i] = Add(i);}return ret;}
};原理同上，只是多了一个循环
3.汉明距离
. - 力扣（LeetCode）
class Solution {
public:int hammingDistance(int x, int y) {int n = 32;int ret = 0;while(n>0){if((x & 1) != (y & 1))ret++;x = x >> 1;y = y >> 1;n--;}return ret;}
};分别用 &1 来判断两个数最低位是0还是1，对两个数进行比较，然后分别不断右移这两个数
4.只出现一次的数字
. - 力扣（LeetCode）
利用异或的性质即可
class Solution {
public:int singleNumber(vector<int>& nums) {int val = 0;for(auto ch:nums){val ^= ch;}return val;}};5.只出现一次的数字3
. - 力扣（LeetCode）
class Solution {
public:vector<int> singleNumber(vector<int>& nums) {long long n = 0;for(auto ch: nums){n ^= ch;}long long mask = n &(-n);mask = (int)mask;vector<int>ret(2,0);for(auto ch: nums){if((ch & mask) == mask)ret[0] ^= ch;else ret[1] ^= ch;}return ret;}
};我们先将所有值异或，这个过程会将相同的数都消去，最后得到两个不同的数a，b异或的结果。
这个数为1的位置，是两个数上值不同的位置。为了方便，我们取出最右侧的1。
a，b两个数中，一个数的该位置为1，一个数为0.
而待分开的数的该位置也一定为1或0.因此我们将全部数分为两组
a，xx yy zz b，mm，nn，oo
这样即可分别取出单独的数