位运算的奇技淫巧

这篇具有很好参考价值的文章主要介绍了位运算的奇技淫巧。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

常见位运算总结:

1、基础位运算

左移<<运算

将二进制数向左移位操作,高位溢出则丢弃,低位补0。

右移>>运算

右移位运算中,无符号数和有符号数的运算并不相同。对于无符号数,右移之后高位补0;对于有符号数,符号位一起移动,正数高位补0,负数高位补1

按位与&运算

有0就是0,巧计:&这个符号像是有两个0组合而成。

按位或 | 运算

有1就是1,巧计:|本身就像一个1

按位异或^运算(两种解释方法)

相同为0,相异为1,或者解释成无进位相加

2、给一个数n,确定它的二进制表示中的第x位是0还是1

(n >> x) & 1

&1后的结果就是0/1,因为1的二进制位除了最后一位,其他都是0,&0就是0

3、将一个数n的二进制位的第x位改成1

n =(1 << x)|  n

位运算的奇技淫巧,C语言/C++练习题,算法

4、将一个数n的二进制位的第x位改成0

n = n & (~(1 << x))

位运算的奇技淫巧,C语言/C++练习题,算法

5、位图的思想

本质上就是一个哈希表

6、提取一个数(n)二进制表示中最右侧的1(lowbit)

n & -n

解释:-n的操作就是先取反,然后再+1,这样造成的影响是最右边的1前面都是n的相反数,这样再跟原先的n&,因为是相反数,所以有一方肯定是0,这样最右边的1前面的数字都变成了0,最右边1右边本身就是0。

位运算的奇技淫巧,C语言/C++练习题,算法

7、干掉一个数(n)最右边的1

n &(n - 1)

位运算的奇技淫巧,C语言/C++练习题,算法

8、位运算的优先级

为了避免记住闲杂的公式,我们只需要记住能加括号就加括号。

9、异或运算的运算规律

  • a ^ 0 = a
  • a ^ a = 0(消消乐)
  • a ^ b ^ c = a ^ (b ^ c)

上面的指示是位运算的基础知识,下面就带着上面的指示开始实操啦

第一题:191. 位1的个数

编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 '1' 的个数(也被称为汉明重量)。

解析:

只需要每次右移&1判断是否为1。

原码:

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int sum = 0;
        int ret = n;
        for(int i = 0;i<32;i++)
        {
            if(ret & 1 == 1) sum++;
            ret = ret >> 1;
        }
        return sum;
    }
};

第二题、461. 汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y,计算并返回它们之间的汉明距离。

解析:

根据题目来看,可能最先想到的就是异或操作,相同为 0,不同为 1。异或操作后结果为 0101,然后我们只需要统计出来二进制结果中 1 的个数就可以计算出来汉明距离啦。

原码:

class Solution {
public:
    int hammingDistance(int x, int y) {
        int ret = x ^ y;
        int sum = 0;
        //计算1的个数
        for(int i = 0;i<32;i++)
        {
            if(ret & 1 == 1) sum++;
            ret = ret >> 1;
        } 
        return sum;
    }
};

第三题、136. 只出现一次的数字

给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。

解析:

这是一道很典型的运用^的题目,我们只需要理解异或运算符,这题就迎刃而解啦。

原码:

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

第四题、260. 只出现一次的数字 III

给你一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

解析:

本题是上一题的升级版,

把nums中的元素全部异或起来的结果eor就是那两个只出现一次的数字的异或结果。而这两个数不相同,意味着eor至少有一位是1,我们可以用lowbit运算拿到最低位的1,然后遍历nums数组,将所有数nums[i]按照这一位是不是1分成两类,初始化num1=num2=0

  1. 如果当前位是1,就将nums[i]异或到num1​上。

  2. 如果当前位是0,就将nums[i]异或到num2​上。

这样一来,两个只出现一次的数就会被分别异或到num1​和num2​上,而其他数也会被分别异或到这两个数上。而由于其他数都出现了两次,所以最终它们就会被异或成0,num1​和num2​就是那两个只出现一次的数。

注意进行位运算的优先级,直接加上括号就好!!!

原码:

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int a = 0, b = 0;//记录两个不同的数
        int ret = 0;
        for(int i = 0;i<nums.size();i++)
            ret ^= nums[i];
        //进行lowbit运算,两者不同,二进制肯定有1
        int tmp = ret & (-(long long)ret);//防止数据溢出
        for(int i = 0;i<nums.size();i++)
        {
            if((tmp & nums[i]) == 0)//注意优先级! 
                a ^= nums[i];
            else b ^= nums[i];
        }
        return {a,b};
    }
};

第五题、面试题 01.01. 判定字符是否唯一

解析:

本题第一思想直接用哈希表解决,但题目中用说尽量不用数据结构,我们可以尝试用位图解决!

用位图解决,需要熟练掌握位运算技巧,对巩固位运算有很大帮助!

原码:

class Solution {
public:
    bool isUnique(string astr) {
        int bitmap = 0;//用位图思想解决
        int tmp = 0;
        int n = astr.size();
        //利用鸽巢原理优化
        if(n > 26) return false;
        for(int i = 0;i<astr.size();i++)
        {
            tmp = astr[i] - 'a';
            //判断字符是否已经出现过
            if(((bitmap >> tmp) & 1) == 1) return false;
            //把当前字符加入位图中
            bitmap = bitmap | (1 << tmp);
        }
        return true;
    }
};

第六题、371. 两整数之和

给你两个整数 a 和 b ,不使用 运算符 + 和 - ,计算并返回两整数之和。

思路:

我们前面介绍了^运算的另一个功能是不进位相加,因此我们可以利用这个特性去解决这道题。

因为是不进位,所以我们要想办法去解决进位的问题,^运算是相同为0,相异为1,相异不可能进位,只有相同并且都是1的情况下,才会进位,因此我们直接&,查找出都是1,因为是进位,所以还要左移一位,(a & b)<< 1,然后分别重制a,b的值。位运算的奇技淫巧,C语言/C++练习题,算法

原码:

class Solution {
public:
    int getSum(int a, int b) {
        while(b)
        {
            int tmp = a;
            a = a ^ b;
            b = ((tmp&b) << 1);
        }
        return a;
    }
};

第七题、137. 只出现一次的数字 II

给你一个整数数组 nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

解析:

本题有点难度,两层嵌套循环,根据32位int,把每个数位相加再对3取的余数即可,将每个数想象成32位的二进制,对于每一位的二进制的1和0累加起来必然是3N或者3N+1, 为3N代表目标值在这一位没贡献,3N+1代表目标值在这一位有贡献(=1),然后将所有有贡献的位|起来就是结果。这样做的好处是如果题目改成K个一样,只需要把代码改成cnt%k,很通用~

位运算的奇技淫巧,C语言/C++练习题,算法

原码:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        for(int i = 0;i<32;i++)//依次去修改ans的每一位
        {
            int sum = 0;
            for(int j = 0;j<n;j++)
            {
                //计算nums中所有数的第i位的和
                sum += (nums[j] >> i) & 1;
            }
            //把第i位修改
            if(sum % 3)   
                ans ^= (1 << i); 
        }
        return ans;
    }
};

第八题、面试题 17.19. 消失的两个数字

给定一个数组,包含从 1 到 N 所有的整数,但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗?

以任意顺序返回这两个数字均可。

解析:

本题是两道题的融合版。

  • 将所有的数异或在一起,记为tmp
  • 找到tmp中,比特位上为1的那一位
  • 根据不同的那一位,划分为两类异或

原码文章来源地址https://www.toymoban.com/news/detail-811269.html

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int a = 0,b = 0;
        int n = nums.size();
        int ret = 0;
        //先将所有数异或
        for(int i = 1;i<=n+2;i++)
            ret ^= i;
        for(int i = 0;i<n;i++)
            ret ^= nums[i];
        //lowbit运算找到最右边的1
        int tmp = ret & (-(long long)ret);//防止溢出
        for(int i = 0;i<n;i++)
        {
            if((nums[i] & tmp) == 0) a ^= nums[i];
            else b ^= nums[i];
        }
        for(int i = 1;i<=n+2;i++)
        {
            if((i & tmp) == 0) a ^= i;
            else b ^= i; 
        }
        return {a,b};
    }
};

到了这里,关于位运算的奇技淫巧的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Sql奇技淫巧之ROWNUM伪列

    ROWNUM 是一个伪列,它是根据每次查询的结果动态生成的一列递增编号,表示 Oracle 从表中选择该行的顺序,选择的第一行 ROWNUM 为1,第二行 ROWNUM 为2,以此类推。 ROWNUM 伪列是在 WHERE 子句之前生成的,就是说它并不是在执行了 WHERE 子句过滤之后再对数据编号 比如在执行 WHE

    2024年02月13日
    浏览(37)
  • SQL奇技淫巧之pipeline管道

    这里创建了一个名为 test_type 的类型, AS OBJECT 表示这个类型是一个对象类型, 包含了两个字段(也可以说是列),数字类型的 colum1 和字符串类型的 colum2 ; 这里创建了一个名为 test_type_table 的类型, AS TABLE 表示这个类型是一个表(集合)类型, OF test_type 表示这个类型是基于 t

    2024年02月13日
    浏览(34)
  • Intellij IDEA有什么奇技淫巧?

    IDEA全称 IntelliJIDEA,是java语言开发的集成环境,IntelliJ在业界被公认为最好的java开发工具之一,尤其在 智能代码助手、代码自动提示、重构、J2EE支持、Ant、JUnit、CVS整合、代码审查、创新的GUI设计 等方面的功能可以说是超常的。 idea下载地址:jetbrains.com/idea 下面来说几个I

    2024年02月15日
    浏览(38)
  • Oracle/PL/SQL奇技淫巧之ROWNUM伪列

    ROWNUM 是一个伪列,它是根据每次查询的结果动态生成的一列递增编号,表示 Oracle 从表中选择该行的顺序,选择的第一行 ROWNUM 为1,第二行 ROWNUM 为2,以此类推。 ROWNUM 伪列是在 WHERE 子句之前生成的,就是说它并不是在执行了 WHERE 子句过滤之后再对数据编号 比如在执行 WHE

    2024年02月12日
    浏览(41)
  • Oracle/PL/SQL奇技淫巧之Json转表

    在Oracle中,有些时候我们需要在一个json文档中查数据 这个时候我们可以通过 JSON_TABLE 函数来把 json文档 提取成一张可以执行正常查询操作的表 先看 JSON_TABLE 函数的基础用法: 其中: json_data :要从中提取数据的 JSON文档 或 JSON列 $.json_path :JSON路径表达式,该表达式指定要提

    2024年02月12日
    浏览(40)
  • 一看就懂的OpenGL ES教程——仿抖音滤镜的各种奇技淫巧(一)_opengl es添加视频

    上一篇文章一看就懂的OpenGL ES教程——渲染宫崎骏动漫重拾童年 已经详细阐述了如何用OpenGL es将原始的YUV数据组成的视频渲染到屏幕上,想必有很多童鞋在阅读了它之后依然觉得回味无穷,学习的胃口也越来越大了,因为你们知道仅仅渲染视频是不够的,我们要的是,能够在

    2024年04月25日
    浏览(42)
  • 一看就懂的OpenGL ES教程——仿抖音滤镜的各种奇技淫巧(一)_opengl es添加视频(1)

    自我介绍一下,小编13年上海交大毕业,曾经在小公司待过,也去过华为、OPPO等大厂,18年进入阿里一直到现在。 深知大多数HarmonyOS鸿蒙开发工程师,想要提升技能,往往是自己摸索成长或者是报班学习,但对于培训机构动则几千的学费,着实压力不小。自己不成体系的自学

    2024年04月16日
    浏览(42)
  • C# 类class、继承、多态性、运算符重载,相关练习题

    34.函数重载 35.几个相同的函数  print() ,用于打印不同的数据类型。   36.基类和派生类   37.基类的初始化   38.多重继承   39.动态多态性   40.抽象性和虚方法   41.通过虚方法 area() 来计算不同形状图像的面积   42.运算符重载的实现   @www.runoob.com 

    2024年02月09日
    浏览(43)
  • C语言之练习题

    欢迎来到我的: 世界 希望作者的文章对你有所帮助,有不足的地方还请指正,大家一起学习交流 ! 这期文章由:两题问答题+四道编程题;小孩在文章中写有详细解题思路,感谢大家支持支持。 思路: 首先我们要知道 x=x(x-1) 的含义; 假设x=3;也就是 011 ; 而x-1=2;是 010 ;

    2024年02月10日
    浏览(54)
  • C 语言练习题更新

    目录(先不要看答案,首先自己做才能更好的领悟,做不来没关系) 题目一:有 1、2、3、4 四个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? 程序分析:可填在百位、十位、个位的数字都是 1、2、3、4,组成所有的排列后再去掉不满足条件的排列。 题目

    2024年02月14日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包