精华内容
下载资源
问答
  • 【技巧总结】位运算装逼指南

    万次阅读 多人点赞 2019-11-18 13:34:09
    算法的效率有多快我就不说,不信你可以去用 10 亿个数据模拟一下,今天给大家讲一讲位运算的一些经典例子。不过,最重要的不是看懂了这些例子就好,而是要在以后多去运用位运算这些技巧,当然,采用位运算,也是...

    位算法的效率有多快我就不说,不信你可以去用 10 亿个数据模拟一下,今天给大家讲一讲位运算的一些经典例子。不过,最重要的不是看懂了这些例子就好,而是要在以后多去运用位运算这些技巧,当然,采用位运算,也是可以装逼的,不信,你往下看。我会从最简单的讲起,一道比一道难度递增,不过居然是讲技巧,那么也不会太难,相信你分分钟看懂。

    判断奇偶数

    判断一个数是基于还是偶数,相信很多人都做过,一般的做法的代码如下

    if( n % 2) == 01
        // n 是个奇数
    }
    

    如果把 n 以二进制的形式展示的话,其实我们只需要判断最后一个二进制位是 1 还是 0 就行了,如果是 1 的话,代表是奇数,如果是 0 则代表是偶数,所以采用位运算的方式的话,代码如下:

    if(n & 1 == 1){
        // n 是个奇数。
    }
    

    有人可能会说,我们写成 n % 2 的形式,编译器也会自动帮我们优化成位运算啊,这个确实,有些编译器确实会自动帮我们优化。但是,我们自己能够采用位运算的形式写出来,当然更好了。别人看到你的代码,我靠,牛逼啊。无形中还能装下逼,是不是。当然,时间效率也快很多,不信你去测试测试。

    2、交换两个数

    交换两个数相信很多人天天写过,我也相信你每次都会使用一个额外来变量来辅助交换,例如,我们要交换 x 与 y 值,传统代码如下:

    int tmp = x;
    x = y;
    y = tmp;
    

    这样写有问题吗?没问题,通俗易懂,万一哪天有人要为难你,**不允许你使用额外的辅助变量来完成交换呢?**你还别说,有人面试确实被问过,这个时候,位运算大法就来了。代码如下:

    x = x ^ y   // (1)
    y = x ^ y   // (2)
    x = x ^ y   // (3)
    

    我靠,牛逼!三个都是 x ^ y,就莫名交换成功了。在此我解释下吧,我们知道,两个相同的数异或之后结果会等于 0,即 n ^ n = 0。并且任何数与 0 异或等于它本身,即 n ^ 0 = n。所以,解释如下:

    把(1)中的 x 带入 (2)中的 x,有

    y = x^y = (xy)y = x(yy) = x^0 = x。 x 的值成功赋给了 y。

    对于(3),推导如下:

    x = x^y = (xy)x = (xx)y = 0^y = y。

    这里解释一下,异或运算支持运算的交换律和结合律哦。

    以后你要是别人看不懂你的代码,逼格装高点,就可以在代码里面采用这样的公式来交换两个变量的值了,被打了不要找我。

    讲这个呢,是想告诉你位运算的强大,让你以后能够更多着去利用位运算去解决一些问题,一时之间学不会也没事,看多了就学会了,不信?继续往下看,下面的这几道题,也是非常常见的,可能你之前也都做过。

    3、找出没有重复的数

    给你一组整型数据,这些数据中,其中有一个数只出现了一次,其他的数都出现了两次,让你来找出一个数 。

    这道题可能很多人会用一个哈希表来存储,每次存储的时候,记录 某个数出现的次数,最后再遍历哈希表,看看哪个数只出现了一次。这种方法的时间复杂度为 O(n),空间复杂度也为 O(n)了。

    然而我想告诉你的是,采用位运算来做,绝对高逼格!

    我们刚才说过,两个相同的数异或的结果是 0,一个数和 0 异或的结果是它本身,所以我们把这一组整型全部异或一下,例如这组数据是:1, 2, 3, 4, 5, 1, 2, 3, 4。其中 5 只出现了一次,其他都出现了两次,把他们全部异或一下,结果如下:

    由于异或支持交换律和结合律,所以:

    123451234 = (11)(22)(33)(44)5= 00005 = 5。

    也就是说,那些出现了两次的数异或之后会变成0,那个出现一次的数,和 0 异或之后就等于它本身。就问这个解法牛不牛逼?所以代码如下

    int find(int[] arr){
        int tmp = arr[0];
        for(int i = 1;i < arr.length; i++){
            tmp = tmp ^ arr[i];
        }
        return tmp;
    }
    

    时间复杂度为 O(n),空间复杂度为 O(1),而且看起来很牛逼。

    4、m的n次方

    如果让你求解 m 的 n 次方,并且不能使用系统自带的 pow 函数,你会怎么做呢?这还不简单,连续让 n 个 m 相乘就行了,代码如下:

    int pow(int n){
        int tmp = 1;
        for(int i = 1; i <= n; i++) {
            tmp = tmp * m;
        }
        return tmp;
    }
    

    不过你要是这样做的话,我只能呵呵,时间复杂度为 O(n) 了,怕是小学生都会!如果让你用位运算来做,你会怎么做呢?

    我举个例子吧,例如 n = 13,则 n 的二进制表示为 1101, 那么 m 的 13 次方可以拆解为:

    m^1101 = m^0001 * m^0100 * m^1000。

    我们可以通过 & 1和 >>1 来逐位读取 1101,为1时将该位代表的乘数累乘到最终结果。直接看代码吧,反而容易理解:

    int pow(int n){
        int sum = 1;
        int tmp = m;
        while(n != 0){
            if(n & 1 == 1){
                sum *= tmp;
            }
            tmp *= tmp;
            n = n >> 1;
        }
        
        return sum;
    }
    

    时间复杂度近为 O(logn),而且看起来很牛逼。

    这里说一下,位运算很多情况下都是很二进制扯上关系的,所以我们要判断是否是否位运算,很多情况下都会把他们拆分成二进制,然后观察特性,或者就是利用与,或,异或的特性来观察,总之,我觉得多看一些例子,加上自己多动手,就比较容易上手了。所以呢,继续往下看,注意,先别看答案,先看看自己会不会做。

    5、找出不大于N的最大的2的幂指数

    传统的做法就是让 1 不断着乘以 2,代码如下:

    int findN(int N){
        int sum = 1;
       while(true){
            if(sum * 2 > N){
                return sum;
            }
            sum = sum * 2;
       }
    }
    

    这样做的话,时间复杂度是 O(logn),那如果改成位运算,该怎么做呢?我刚才说了,如果要弄成位运算的方式,很多时候我们把某个数拆成二进制,然后看看有哪些发现。这里我举个例子吧。

    例如 N = 19,那么转换成二进制就是 00010011(这里为了方便,我采用8位的二进制来表示)。那么我们要找的数就是,把二进制中最左边的 1 保留,后面的 1 全部变为 0。即我们的目标数是 00010000。那么如何获得这个数呢?相应解法如下:

    1、找到最左边的 1,然后把它右边的所有 0 变成 1

    2、把得到的数值加 1,可以得到 00100000即 00011111 + 1 = 00100000。

    3、把 得到的 00100000 向右移动一位,即可得到 00010000,即 00100000 >> 1 = 00010000。

    那么问题来了,第一步中把最左边 1 中后面的 0 转化为 1 该怎么弄呢?我先给出代码再解释吧。下面这段代码就可以把最左边 1 中后面的 0 全部转化为 1,

    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    

    就是通过把 n 右移并且做运算即可得到。我解释下吧,我们假设最左边的 1 处于二进制位中的第 k 位(从左往右数),那么把 n 右移一位之后,那么得到的结果中第 k+1 位也必定为 1,然后把 n 与右移后的结果做或运算,那么得到的结果中第 k 和 第 k + 1 位必定是 1;同样的道理,再次把 n 右移两位,那么得到的结果中第 k+2和第 k+3 位必定是 1,然后再次做或运算,那么就能得到第 k, k+1, k+2, k+3 都是 1,如此往复下去…

    最终的代码如下

    int findN(int n){
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8 // 整型一般是 32 位,上面我是假设 8 位。
        return (n + 1) >> 1;
    }
    

    这种做法的时间复杂度近似 O(1),重点是,高逼格。

    总结

    上面讲了 5 道题,本来想写十道的,发现五道就已经写了好久了,,,,十道的话,怕你们也没耐心写完,而且一道比一道难的那种,,,,。

    不过呢,我给出的这些例子中,并不是让你们学会了这些题就 Ok,而且让你们有一个意识:很多时候,位运算是个不错的选择,至少时间效率会快很多,而且高逼格,装逼必备。所以呢,以后可以多尝试去使用位运算哦,以后我会再给大家找些题来讲讲,遇到高逼格的,感觉很不错的,就会拿来供大家学习了。

    兄dei,如果觉得我写的不错,不妨帮个忙

    1、关注我的原创微信公众号「帅地玩编程」,每天准时推送干货技术文章,专注于写算法 + 计算机基础知识(计算机网络+ 操作系统+数据库+Linux),听说关注了的不优秀也会变得优秀哦。

    2、给俺点个赞呗,可以让更多的人看到这篇文章,顺便激励下我,嘻嘻。

    在这里插入图片描述

    作者简洁

    作者:大家好,我是帅地,从大学、自学一路走来,深知算法计算机基础知识的重要性,所以申请了一个微星公众号『帅地玩编程』,专业于写这些底层知识,提升我们的内功,帅地期待你的关注,和我一起学习。 转载说明:未获得授权,禁止转载

    展开全文
  • 位运算判断奇偶

    2017-09-06 21:11:57
    普通方法 public static boolean isOdd(int i){  return i % 2 != 0; } 位运算方法 ...public static boolean isOdd...位运算可以提高程序的运行效率: 计算机中的数字通常用二进制补码表示—— 如果为正数,补码


    普通方法

    public static boolean isOdd(int i){

            return i % 2 != 0;

    }

    位运算方法

    public static boolean isOdd(int i){

            return (i & 1) != 0;

    }

     

    位运算可以提高程序的运行效率:

    计算机中的数字通常用二进制补码表示——

    如果为正数,补码与原码相同,直接看最后一位(因为数字1的前面N位均为0,跟它做与运算,前面肯定为0),奇数为1,偶数为0,与1相与,结果不变。

    如果为负数,补码转原码:保持符号位不动,其它各位取反+1,即为负数的绝对值原码全部取反+1。还是看最后1位,先取反,再+1,结果还是和原来相同。进行与运算时还是原来的末位,所以用跟1做与运算还是保持原来的结果。

    展开全文
  • 位运算效率至上

    2013-02-23 14:59:22
    表达式 x &= ( x - 1 ) 有很大用处,删除x最右边值为1的一个二进制,在判断一个整数二进制中含有多少个1时,效率比逐循环判断效率要高。 比如,x = 10000000 时,前者只用循环1次,后者循环8次。

    本文不定期更新

    表达式 x &= ( x - 1 )  有很大用处,删除x最右边值为1的一个二进制位,在判断一个整数二进制中含有多少个1时,效率比逐位循环判断效率要高。

    比如,x = 10000000 时,前者只用循环1次,后者循环8次。


    展开全文
  • 位运算判断奇偶性

    千次阅读 2014-04-11 16:27:01
    同样一个问题,位运算可以提高程序的运行效率。 下面讲一下关于奇偶性的判断。   常规方法 public static boolean isOdd(int i){  return i % 2 != 0; }   位运算方法 public static boolean isOdd(int i){  ...

    同样一个问题,位运算可以提高程序的运行效率。

    下面讲一下关于奇偶性的判断。

     

    常规方法

    public static boolean isOdd(int i){

            return i % 2 != 0;

    }

     

    位运算方法

    public static boolean isOdd(int i){

            return (i & 1) != 0;

    }

     

    说明:

    我们知道计算机中的数字通常用二进制补码表示。

    如果为正数,补码与原码相同,直接看最后一位(因为数字1的前面N位均为0,跟它做与运算,前面肯定为0),奇数为1,偶数为0,与1相与,结果不变。

    如果为负数,补码转原码:保持符号位不动,其它各位取反+1,即为负数的绝对值原码全部取反+1。还是看最后1位,先取反,再+1,结果还是和原来相同。进行与运算时还是原来的末位,所以用跟1做与运算还是保持原来的结果。

    展开全文
  • 由于位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快。 https://blog.csdn.net/weixin_33700350/article/details/85782769?depth_1-utm_source=distribute.pc_relevant.none-task&utm_...
  • C++ 使用位运算判断整数的奇偶性

    千次阅读 2020-08-13 10:52:49
    另外有一种方法,可以通过位与运算判断整数的奇偶性 如下面代码: #include <iostream> using namespace std; int main() { int a = 5; if ((a & 1) == 1) cout << "jishu" << endl; ...
  • 位运算

    千次阅读 2018-12-18 23:34:50
    * 按位与运算 * 两个操作数对应位数都是1结果才是0,否则是0 */ System.out.println(a & b); /** * 按运算 * 两个操作数对应位数都是0结果才是0,否则是1 */ System.out.println(a | b); /** * ...
  • 使用位运算判断奇偶性

    千次阅读 2019-02-28 16:47:28
    平时在做奇偶数判定时,往往采用对2取余看结果是0和1的方式来判断,但这种方法不仅慢,而且有局限性,因为奇偶数的定义是: 整数中,能被2整除的数是偶数,不能被2整除的数是奇数 整数不仅包括0和整数,而且也包括...
  • 【Spark2运算效率】第六节 影响生产集群运算效率的原因之网络IO前言问题概述案例结语跳转 前言 在磁盘IO速率和网络接口IO传输速率匹配的情况下,更快的网络IO能够极大提升Spark程序Shuffle过程中Executor交换数据的...
  • 常见位运算,提高算法效率(c)

    千次阅读 2018-03-07 14:53:29
    第一条:利用位运算判断一个整数是奇数还是偶数。 经常用到一个for循环,当索引i是奇数时执行语句A,偶数时执行语句B。判断i是奇数还是偶数,可用如下方法: if(i &amp;1){ //i是奇数情况执行的代码 } else{ /...
  • 位运算与应用

    千次阅读 2016-01-08 11:34:26
    位运算(包括,或,取反,异或,左移,右移等)是程序设计中的一个重要的领域。尤其是安全和底层开发中,除了指针的频繁使用之外,位运算是另一个非常频繁使用的领域。 因此,在求职面试中,位运算也是每年重点...
  • 简记位运算

    千次阅读 2020-10-27 18:04:30
    Key Words:位运算、或、异或、取反、位移运算 Beijing, 2020 作者:RaySue Code: Agile Pioneer   位运算   计算机内存中都是以二进制形式存储的。位运算就是直接对整数在内存中的二进制进行...
  • Java位运算总结:位运算用途广泛

    千次阅读 2016-01-29 18:13:40
    前天几天研究了下JDK的Collection接口,本来准备接着研究Map接口,可是一查看HashMap类源码傻眼咯,到处是位运算实现,所以我觉得还是...主要包括位与或、非,有符号左移、有符号右移,无符号右移等等。需要注意
  • 位运算 - 初见

    千次阅读 多人点赞 2020-07-10 14:48:59
    以前也多多少少接触过一点位运算,课本上,LeetCode上,但是就是没有动手...负数的二进制表示投机异或的几条性质位运算实现乘除位运算实现swap操作判断奇偶数操作交换符号交换符号操作统计二进制中 1 的个数用 ..
  • 数字的位运算

    万次阅读 2020-02-14 19:07:18
      在做算法题的时候,如果涉及到数字的判断问题,通常来讲,如果能有效利用数字的操作特征,就会大大的简便运算,甚至有重见天日的功效。   从底层来看,计算机的数据表示是二进制的,在存储上本来就是一个个...
  • 有许多种方法可以提升你的代码运算效率,但或许你更想了解运算效率能得到多大的提升。本文将介绍几种适用于大数据领域的方法,包括简单的逻辑调整设计、并行处理和Rcpp的运用,利用这些方法你可以轻松地处理1亿行...
  • 位与运算与取余

    千次阅读 2019-02-20 23:51:30
    偶数的二进制表示中最后一是0,奇数的二进制表示中最后一是1,所以一个整数0x1做按位与运算得到的结果是0或者1就可以判断出这个整数是偶数还是奇数。 二、使用运算符代替求余运算符的技巧 1.性能对比: ...
  • 位运算总结

    2017-03-20 10:58:05
    位与运算位与运算符”&”是双目运算符。其功能是参与运算的两数各对应的二进位相与。只有对应的两个二进位均为1时,结果才为1,否则为0。参与运算的数以补码方式出现。 例如:9&5可写算式如下: 00001001 ...
  • 位运算的应用技巧:

    千次阅读 2016-10-15 21:24:49
    位运算的应用: ...&(按位与)、|(按或)、^(按异或)、~ (按取反)。 其中,按取反运算符是单目运算符,其余均为双目运算符。 运算符的优先级从高到低,依次为~、&、^、|, 其中~的结合方
  • 位运算实例(一):判断奇偶性

    千次阅读 2013-07-27 11:57:39
    同样一个问题,位运算可以提高程序的运行效率。 下面讲一下关于奇偶性的判断。   常规方法 public static boolean isOdd(int i){  return i % 2 != 0; }   位运算方法 public static boolean isOdd(int ...
  • 平时的数值运算,其实是要先转换成二进制再进行运算的,而位运算就是直接进行二进制运算,所以位运算的执行效率肯定是更高的。下面通过一些实例来加深对位运算的理解。 按位与(&) &&运算符我们都知道,只有两个都为...
  • 二进制位运算

    千次阅读 2017-12-03 20:00:01
    位运算(包括,或,取反,异或,左移,右移等)是程序设计中的一个重要的领域。尤其是安全和底层开发中,除了指针的频繁使用之外,位运算是另一个非常频繁使用的领域。 因此,在求职面试中,位运算也是每年重点...
  • 原创公众号:bigsai 原创不易,如果有收获请不要吝啬你的...本篇的内容为位运算的介绍和一些比较经典的位运算问题进行介绍分析,当然,位运算这么牛,后面肯定还是要归纳总结的。 认识位运算 什么是位运算? 程序中的.
  • java位运算20个位运算技巧【转】

    千次阅读 2013-07-17 16:16:53
    一提起位运算,人们往往想到它的高效性,无论是嵌入式编程还是优化系统的核心代码,适当的运用位运算总是一种迷人的手段,或者当您求职的时候,在代码中写入适当的位运算也会让您的程序增加一丝亮点,最初当我读...
  • 位运算常用的运算符包括&(按位与), | (按或),~(按非),^(按异或),<< (有符号左移位) ,>>(有符号右移位)。 下面用几个例子说明其应用,希望对你有所启发。 1、判断奇数还是偶数 通常判断...
  • C++描述的位运算总结

    万次阅读 2019-04-20 12:10:12
    之前大一上课的时候,老师说位运算不考,当时就没有认真去学习。后来学算法的时候,发现大佬的代码中总会掺杂着一些位运算操作,为了理解那些代码,前前后后也看了几次位运算操作,但是没有很好地记录下来。现在又...
  • 位运算实现加减乘除运算

    万次阅读 多人点赞 2017-10-16 10:20:46
    我们知道,计算机最基本的操作单元是字节(byte),一个字节由8个(bit)组成,一个只能存储一个0或1,其实也就是高低电平。无论多么复杂的逻辑、庞大的...因此,了解位运算有助于提升我们对计算机底层操作原理的理解。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 177,818
精华内容 71,127
关键字:

判断与位运算效率