自学内容网 自学内容网

初识算法 · 位运算常见总结(1)

目录

前言:

位运算基本总结

部分题目代码


前言:

​本文的主题是位运算,通过常见的知识点讲解,并且会附上5道简单的题目,5道题目的链接分别为:
191. 位1的个数 - 力扣(LeetCode) 136. 只出现一次的数字 - 力扣(LeetCode)

338. 比特位计数 - 力扣(LeetCode)260. 只出现一次的数字 III - 力扣(LeetCode)

461. 汉明距离 - 力扣(LeetCode)
因为主要是知识点总结,所以题目介绍的不是那么详细,请见谅~

那么,进入主题咯。


位运算基本总结

在C++部分我们其实已经介绍过了位图,对于位图来说,基础自然是位运算了,那么常见的位运算是:

& | ^ >> << ~

有以上六种运算,>>右移运算符<<左移运算符以及~按位取反我们这里不过多介绍了。主要是介绍& | ^。

对于&这个二元运算符来说,两边都为真,那么运算结果为真,也就是全1则1,也可以记忆为有0则0。

对于|这个二元运算发来说,有一边为真,那么运算结果为真,也就是全0则0,也可以记忆为有1则1。

以上的两种记忆方式看同学们自己的理解,没有什么太大的区别。

对于^来说,这个推荐两种记忆方式,两种方式都记住是最好的,一种是相同为0,相异为1,一种是进位相加。

比如1 + 1等于2,但是进位相加之和就是10,所以该位上为0,也可以使用相同为0的这种记法,个人认为进位相加是比较容易理解的一种记法。

基础题目一:给定一个数n,确定它的二进制表示中的第x位是0还是1.

这道题目的思想就是将该x位上的数&上一个1,如果是0,结果就是0,如果是1,结果就是1,如果是用|运算,结果都是1,就没有办法鉴别了。

基础题目二:将一个数的二进制表示的第x位修改成1.

这道题目的思想就是将该x位上的数|上一个1,这样无论是1 还是 0,最后的结果都是1,那么想要
|上这个数字非常简单,只需要将1<<x位即可,我们默认规定一下,一个数字的二进制从右到左的下标是0,和数组下标一样,这样方便表示1 >> x。

基础题目三:将一个数的二进制表示的第x位修改成0.

那这个和2就基本上一样的了,只需要&0就可以了,那么0可以有1<<x之后取反得来,整个结果就有了:

有了上面三道基础题目的基础,我们就可以实现位图了,

位图其实就是一个哈希表,不过之前我们实现哈希表的时候使用的是数组实现的,不过这里我们使用的是int的二进制表示来实现的,我们的操作无非就是0变成1,1变成0,这些基本操作组成了位图。

基本题目四:提取一个数n二进制表示的最右侧的1.

这个题目的别名其实是low bit,也就是低位bit的意思,这道题目没有基本的规律还是比较难思考的,基础做法是n & -n,对于获取-n的基础操作我们是将n全部按位取反之后 + 1即可,那么就可以将n的二进制表示的左边全部变成0,这样右边的1就提取出来了:

基本题目五:干掉一个数n二进制表示的最右侧的1.

这道题目的基础做法是n & n - 1,比如110 & 101,最后的结果就是100,也就将110中最右侧的1干掉了,综上可得,以上两个基础题目是一个类型,这个类型可以衍生出三个题目,分别是191,338,461。

那么有了上面5道题目的基础,我们现在就知道了位的基本运算,可是!位运算的优先级我们知道吗?害,不用知道,库库加括号就对了!

对于异或运算的基本规律我们介绍3点:

1. a ^ a = 0

2. a ^ 0 = 0

3. a ^ b ^ c = a ^ ( b ^ c)

 由这个异或规律,我们可以介绍两个基础题目,136 260。


部分题目代码

class Solution 
{
public:
    int singleNumber(vector<int>& nums) 
    {
        int cur = 0;
        for(int i = 0; i < nums.size(); i++)
            cur ^= nums[i];
        return cur;
    }
};
class Solution {
public:
    int hammingWeight(int n) 
    {
        int ret = 0;
        while(n)
        {
            n &= (n - 1);
            ret++;
        }    
        return ret;
    }
};

干掉了多少个1,就代表有多少个1,所以ret++即可。

class Solution 
{
public:
    int hammingDistance(int x, int y) 
    {
        x ^= y;
        int ret = 0;
        while(x)
        {
            x &= (x - 1);
            ret++;
        }    
        return ret;
    }
};

两个不同的异或之后是1,那么问题可以转换为1的个数有多少个。


感谢阅读!


原文地址:https://blog.csdn.net/2301_79697943/article/details/143723444

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!