专栏首页小浩算法漫画:位运算技巧整理汇总+一道被嫌弃的题目

漫画:位运算技巧整理汇总+一道被嫌弃的题目

今天是小浩算法“365刷题计划”第65天。这两天总有人来问我,做公众号赚了多少钱,或者就是怎么能和你一样,2个月就做到7000粉丝。说实话,至少到目前为止,我一分钱都没赚(打赏的百十块也都红包发出去了),以后赚不赚不好说,毕竟人要吃喝,我也不例外。但是至少目前我认为还没准备好,也不是没有广告商来找,我都委婉拒掉了。另外细心的读者会发现,我连文末的广告都没有开。另外,关于粉丝的增长,我觉得就是单纯的创作,坚持写好文章而已。可能和别的博主不一样,他们有的内容和运营的时间比,在5:5,我大概只有9:1,毕竟我还得上班。而且我不太会弄一些浮夸的标题(太笨编不来),也不会引流,那就只能每天把一个题解写对再写好,争取大家能看懂。不会写得太长,让你们觉得枯燥,不会写的特别短,让你们厌烦。这就是目前我所有能做的想做的了,其他的,以后再说。好了,废话就到这里,今天将分享一道很简单,并且总被Diss的题目:

01 PART

两数之和

这个题很老了,拿出来给不会的同学看一看,会的直接跳过。(值得一说的是,这个题目在国外上,有2000个dislike,可以看到大家的嫌弃!)

第268题:不使用运算符 + 和 - ,计算两整数 a 、b 之和。

02 PART

位运算求解

位运算的题,大部分都有一些特别的技巧,只要能掌握这些技巧,对其拼装组合,就可以破解一道道的题目。很多人说那些技巧想不到,我觉得是因为没有认真的去学习和记忆。你要相信,基本上所有人最开始都是不会的,只是后来他们通过努力学会了记住了,而你因为没努力一直停留在不会而已。不要觉得那些一眼看到题就能想到解法的人有多么了不起。“无他,唯手熟尔!”

下面这两个技巧大家需要记住,这也是讲解本题的目的:

“异或”是一个无进位加法,说白了就是把进位砍掉。比如01^01=00。

“与”可以用来获取进位,比如01&01=01,然后再把结果左移一位,就可以获取进位结果。

根据上面两个技巧,假设有 12+7:

根据分析,完成题解:

//JAVA
class Solution {
    public int getSum(int a, int b){
        while(b != 0){
            int temp = a ^ b;
            b = (a & b) << 1;
            a = temp;
        }
        return a;
    }
}
  • 本系列所有教程都不会用到复杂的语言特性,不需要担心没有学过相关语法,使用各语言纯属本人爱好。
  • 作为学术文章,虽然风格可以风趣,但严谨,我是认真的。本文所有代码均在leetcode上进行过测试运行。
  • 算法思想才是最重要的。

03 PART

位运算技巧总结

为了大家方便学习,我对位运算的常见面试题技巧进行了总结。

首先,常见的位运算包括:

Operators

Meaning of operators

&

Bitwise AND,按位与

|

Bitwise OR,按位或

^

Bitwise XOR,按位异或

~

Bitwise complement,按位取反

<<

Shift left,左移

>>

Shift right,右移

基本的操作我就直接略过了。下面是我认为必须掌握的技巧:(注意,我把一些生僻的技巧都已经砍掉了,留下来的,就是我认为应该会的)

1、使用 x & 1 == 1 判断奇偶数。(注意,一些编辑器底层会把用%判断奇偶数的代码,自动优化成位运算)

2、不使用第三个数,交换两个数。x = x ^ y , y = x ^ y , x = x ^ y。(早些年喜欢问到,现在如果谁再问,大家会觉得很low)

3、两个相同的数异或的结果是 0,一个数和 0 异或的结果是它本身。(对于找数这块,异或往往有一些别样的用处。)

4、x & (x - 1) ,可以将最右边的 1 设置为 0。(这个技巧可以用来检测 2的幂,或者检测一个整数二进制中 1 的个数,又或者别人问你一个数变成另一个数其中改变了多少个bit位,统统都是它)

5、i+(~i)=-1,i 取反再与 i 相加,相当于把所有二进制位设为1,其十进制结果为-1。

6、对于int32而言,使用 n >> 31取得 n 的正负号。并且可以通过 (n ^ (n >> 31)) - (n >> 31) 来得到绝对值。(n为正,n >> 31 的所有位等于0。若n为负数,n >> 31 的所有位等于1,其值等于-1)

7、使用 (x ^ y) >= 0 来判断符号是否相同。(如果两个数都是正数,则二进制的第一位均为0,x^y=0;如果两个数都是负数,则二进制的第一位均为1;x^y=0 如果两个数符号相反,则二进制的第一位相反,x^y=1。有0的情况例外,^相同得0,不同得1)

第一版先整理这些吧,后续再逐步补充。想复习一下其他位运算题目的,可以看:

漫画:位运算系列篇(缺失数字)

漫画:位运算系列篇(只出现一次的数字)

漫画:位运算系列篇(只出现一次的数字 - 进阶版)

漫画:三分钟学习一道位运算的面试题,万一遇到了呢?

漫画:位运算技巧助你俘获offer

所以,今天的问题你学会了吗?评论区留下你的想法!

小浩算法,每日一题

关注领取《图解算法》高清版

进群的小伙伴请加右侧私人微信(备注:进群)

第一版先整理这些吧,后续再逐步补充。

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员浩哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:神奇的找出只出现一次的数字!

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

    程序员小浩
  • 漫画:三分钟学习一道位运算的面试题,万一遇到了呢?

    这道题是通过位运算来进行求解的非常典型的题目。当然,其他的题解也有很多:比如暴力求解,又或者是不停除以2通过递归的方式求解,等等。但是并不是今天我想说的。

    程序员小浩
  • 《剑指offer》第九天:斐波那契数列

    大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第 n 项(从 0 开始,第 0 项为 0)。n<=39

    程序员小浩
  • psacct

    psacct或ACCT都是在系统上监控用户活动的开源应用程序。 这些应用程序在后台运行,并跟踪系统上的每个用户活动以及正在使用的资源。

    胡齐
  • 拉链表是什么

    木东居士
  • pytorch基础知识-维度变换-(上)

    维度变换是pytorch中的重要操作,尤其是在图片处理中。本文对pytorch中的维度变换进行讲解。

    用户6719124
  • 一个有趣的时间段重叠问题

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1148526
  • pytorch基础知识:张量(下)

    其中一维标量主要用于Bias(偏差)中,如在构建神经元中多组数据导入到一个神经元中,由激活函数激活输出一个数值,则该神经元主要使用bias功能。线性层输入(Li...

    用户6719124
  • 丢给你个环形队列玩玩

    假设我需要处理10000个字节的数据,就是串口一次性会发过来10000个字节,然后单片机每次取10个字节处理,然后处理1000次就处理完了

    杨奉武
  • MySQL中InnoDB引擎对索引的扩展

    MySQL中,使用InnoDB引擎的每个表,创建的普通索引(即非主键索引),都会同时保存主键的值。

    数据和云

扫码关注云+社区

领取腾讯云代金券