算法小练之 位运算基础
前言
今天正式走入，位运算这个章节，关于这一部分我会先介绍几个重要的知识点，然后再根据几个力扣上的题来讲解。
了解6种位操作
总所周知，变量在计算机中都是二进制存储的，比如一个变量int a = 1；
它的存储方式就是：
>>（右移）：
用法：a>>x 含义：将a的二进制位数整体右移x位
举例：
<<（左移）：
用法：x<<a 含义：将a的二进制位数整体左移x位
举例：
~（按位取反）：
用法：~a 含义：将a的所有二进制位进行取反，1改为0，0改为1
举例：
&（按位与）：
用法：a&b 含义：有0为0，无0为1
举例：
二级结论：
x为任何数 x & 1 = x
|（按位或）：
用法：a|b 含义：有1为1，无1为0
举例：
二级结论：
x为任何数 x | 0 = x
^(按位异或) ：
用法：a^b 含义：相同为0，相异为1
举例：
二级结论：
x为任何数 x ^ 0 = x x ^ x = 0 a ^ b ^ c = a ^ c ^ b = a ^ (b ^ c)
现在可以学习一些基本的位操作了
1.确定数n二进制第x位是0还是1
注意：x为用右往左从0开始计数的下标
结论：
(n>>x) & 1
原理很简单，自己随便模拟一下即可。
2.将数n二进制的第x位改成1
结论：
n = n | （1 << x）
3.将数n二进制的第x位改成0
结论：
n = n & (~ (1 << x))
4.提取一个数n最右侧的1
结论：
n & （-n）
5.干掉一个数n最右侧的1
结论：
n & (n - 1)
题目实战：
位1的个数：
题目很简单，就是给一个数n，求它的二进制中有多少个1。
思路：
借助结论1：确定数n二进制第x位是0还是1，从右往左遍历所有二进制位，发现1就计数器++：
class Solution {
public:
int hammingWeight(int n) {
int ret = 0;
for(int i = 0;i<32;i++)//从右往左遍历整个二进制
{
if(((n>>i)&1)==1)//检查第i位是否为 1
{
ret++;
}
}
return ret;
}
};比特位计数：
本题和上一题相差不大，只需加一层for遍历0 -- n即可：
class Solution {
public:
vector<int> countBits(int n) {
vector<int> ret;
for(int i = 0;i<=n;i++)
{
int count = 0;
for(int j = 0;j<32;j++)
{
if(((i>>j)&1) == 1)
{
count++;
}
}
ret.push_back(count);
}
return ret;
}
};汉明距离：
思路：
做了上面两道题后，再看这道题就会发现很简单，我们只需先将x^y，因为^操作相同为0，相异为1，我们只需统计x^y后二进制位中有多少个1即可：
class Solution {
public:
int hammingDistance(int x, int y) {
int ret = 0;
int n = x ^ y;
for(int i = 0; i<32 ;i++)
{
if(((n>>i)&1) == 1)
{
ret++;
}
}
return ret;
}
};这几道题较为基础，是深入学习的前提，希望大家好好掌握。
腾讯云开发者
