前言
今天正式走入,位运算这个章节,关于这一部分我会先介绍几个重要的知识点,然后再根据几个力扣上的题来讲解。
了解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;}
};
这几道题较为基础,是深入学习的前提,希望大家好好掌握。