位运算 订阅
程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。比如,and运算本来是一个逻辑运算符,但整数与整数之间也可以进行and运算。举个例子,6的二进制是110,11的二进制是1011,那么6 and 11的结果就是2,它是二进制对应位进行逻辑运算的结果(0表示False,1表示True,空位都当0处理)。110AND 1011---------------0010 --> 2 展开全文
程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。比如,and运算本来是一个逻辑运算符,但整数与整数之间也可以进行and运算。举个例子,6的二进制是110,11的二进制是1011,那么6 and 11的结果就是2,它是二进制对应位进行逻辑运算的结果(0表示False,1表示True,空位都当0处理)。110AND 1011---------------0010 --> 2
信息
外文名
bitwise operation
方    法
对整数进行操作
用    途
优化程序
中文名
位运算
位运算运算符号
下面的a和b都是整数类型,则:
收起全文
精华内容
参与话题
问答
  • 位运算

    千次阅读 多人点赞 2019-03-30 21:45:46
    位运算首先补码按位与(&)按位或(|)按位异或(^)左移(<<)右移(>>)取反(~) 首先 要明白位运算是在二进制中的运算方式,所有其他进制的数在进行位运算时都要先转化成二进制数再进行运算。 ...

    Update:

    右移例子中右移符号(>>)打错,现已更正,感谢tabula rasa的提醒
    11.18更正两个错字,感谢weixin_39025439的提醒

    首先

    要明白位运算是在二进制中的运算方式,所有其他进制的数在进行位运算时都要先转化成二进制数再进行运算。
    位运算主要包括按位与(&)、按位或(|)、按位异或(^)、取反( ~ )、左移(<<)、右移(>>)这几种。
    其中除了取反( ~ )以外,其他的都是二目运算符,即要求运算符左右两侧均有一个运算量。

    补码

    补码是为了表示一个负数的二进制形式。
    其转化方式是,先将负数当成正数,转化成二进制的形式,再将二进制正数的各个位上取反,再加上一。

    例如-5
    先求出5的二进制数 : 0000 0000 0101
    然后将各个位上0变1,1变0 : 1111 1111 1010
    最后再加1 : 1111 1111 1011
    这里5二进制下是101表示时前面全是0,这里省略就只写了几个意思一下^ _ ^

    按位与(&)

    运算的两个数,转换算为二进制后,进行与(&)运算。
    当相应位上的数都是1时,该位取1,否则该为0。

    例如5 & -5
    5 : 0000 0000 0101
    -5 :1111 1111 1011
    答案 : 0000 0000 0001

    按位或(|)

    运算的两个数,转换为二进制后,进行或(|)运算。
    只要相应位上存在1,那么该位就取1,如果都不为1,就为0。

    还是5 | -5
    0000 0000 0101
    1111 1111 1011
    可以看到每一位中其中一个都有1
    答案 :1111 1111 1111

    按位异或(^)

    运算的两个数,转换成二进制数后,进行异或(^)运算
    如果相应位置上的数相同,该位取0,如果不同改位取1。

    5 ^ -5
    0000 0000 0101
    1111 1111 1011
    答案: 1111 1111 1110

    同时任何数异或0都是其本身,一个数如果异或自己则等于0
    这样我们可以用异或来交换两个数的值

    比如交换x,y的值
    x ^= y; x = x ^ y
    y ^= x; y = y ^ x ^ y
    x ^= y; x = ( x ^ y ) ^ (y ^ x ^ y) ; --------- //最后一步 x ^= y 时 x = x ^ y; y = y ^ x ^ y

    左移(<<)

    将一个数二进制下的数向左移若干位,
    比如 x << y 就是将二进制下的x 向左移 y 位

    例 : 5 << 5
    5 : 0000 0000 0101
    5 << 5 : 0000 1010 0000
    在10进制下就等于160

    我们可以思考一下,在十进制中,一个数每乘一次10就向左进一位。
    那么在二进制中,同10进制一样,二进制中每乘一次2就向左进一位,
    那么一个数左移x 就等价于一个数乘 2x

    右移(>>)

    将一个数在二进制下右移若干位
    与左移用法相同

    例 5 >> 2
    5:0000 0000 0101
    5 >> 2 : 0000 0000 0001
    十进制下等于1

    这里与左移类似,十进制下每除10整数位就退一位
    那么右移就等价于除了几次2
    同时右移运算是向下取整

    取反(~)

    其实在说补码的时候,取反就已经说了,就是将取反的数在二进制下的每一位取相反的数

    5 : 0000 0000 0101
    ~5 : 1111 1111 1010

    补充

    位运算可用于状态压缩,用0,1来表示物品的状态。
    例如:现有n个物品,我们就可以用一个n位的二进制数来表示每一个物品的选取,若第i为1,表示选取第i个物品,若第i位为0,则表示不选取第i个物品。
    状态压缩常用于搜索和DP,是一种很暴力的方法,只有在N比较小的时候适用long long类型能存下1018的数,大概是240即N>40时,我们很可能不能直接用二进制枚举出状态并储存。

    展开全文
  • 【技巧总结】位运算装逼指南

    万次阅读 多人点赞 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、给俺点个赞呗,可以让更多的人看到这篇文章,顺便激励下我,嘻嘻。

    在这里插入图片描述

    作者简洁

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

    展开全文
  • 在《java程序性能优化》中写到,位运算是运算中最高效的,而我依照书上的代码运行了一遍 发现并不是这样。 补上代码: public class BitOperate { public static void main(String[] args) { nomal(); bit...
  • 关于if和位运算比较的测试代码

    万次阅读 2020-08-18 22:49:19
    本着学习严谨的态度,非常疑惑因此自己动手写了一下,进行测试 改编于沉默王二的一篇博客点我传送原文地址 如果进行Arrays.sort(data);排序 /** * @author 沉默王二,一枚有趣的程序员 */ // 声明数组 ...

    本着学习严谨的态度,非常疑惑因此自己动手写了一下,进行测试

    改编于沉默王二的一篇博客点我传送原文地址

    如果进行Arrays.sort(data);排序

            /**
             * @author 沉默王二,一枚有趣的程序员
             */
            // 声明数组
            int arraySize = 32768;
            int data[] = new int[arraySize];
    
            Random rnd = new Random();
            for (int c = 0; c < arraySize; ++c) {
                data[c] = rnd.nextInt() % 256;
            }
            Arrays.sort(data);
            for (int i = 0; i < 10; i++) {
                // 测试
                long sum = 0;
                long start = System.nanoTime();
                for (int c = 0; c < arraySize; ++c) {
                    if (data[c] >= 128) {
                        sum += data[c];
                    }
                }
                long end = System.nanoTime();
                System.out.println(end - start);
                System.out.println("sum = " + sum);
                // 测试
                long sum1 = 0;
                long start1 = System.nanoTime();
    
                // 循环
                for (int c = 0; c < arraySize; ++c) {
                    int t = (data[c] - 128) >> 31;//留下了符号位,用于判断 data[c] 是否 > 128
                    sum1 += ~t & data[c];//
                }
                long end1 = System.nanoTime();
                System.out.println((end1 - start1));
                System.out.println("sum1 = " + sum1);
                System.out.println();
    
            }
    

    得到的数据结果

    474300
    sum = 1568712
    801300
    sum1 = 1568712
    
    212900
    sum = 1568712
    106100
    sum1 = 1568712
    
    246200
    sum = 1568712
    257100
    sum1 = 1568712
    
    194200
    sum = 1568712
    278200
    sum1 = 1568712
    
    209000
    sum = 1568712
    235600
    sum1 = 1568712
    
    192500
    sum = 1568712
    256500
    sum1 = 1568712
    
    213500
    sum = 1568712
    234900
    sum1 = 1568712
    
    189600
    sum = 1568712
    365200
    sum1 = 1568712
    
    196300
    sum = 1568712
    234400
    sum1 = 1568712
    
    227300
    sum = 1568712
    403100
    sum1 = 1568712
    

    如果不经过Arrays.sort(data);

    将上面的这行代码注释即可
    得到的结果:

    539400
    sum = 1539769
    880300
    sum1 = 1539769
    
    568200
    sum = 1539769
    100600
    sum1 = 1539769
    
    2216100
    sum = 1539769
    227200
    sum1 = 1539769
    
    356900
    sum = 1539769
    260600
    sum1 = 1539769
    
    272000
    sum = 1539769
    223000
    sum1 = 1539769
    
    262700
    sum = 1539769
    222300
    sum1 = 1539769
    
    295300
    sum = 1539769
    223600
    sum1 = 1539769
    
    326300
    sum = 1539769
    232100
    sum1 = 1539769
    
    264700
    sum = 1539769
    217200
    sum1 = 1539769
    
    381000
    sum = 1539769
    234800
    
    

    从这两种测试数据来看,经过排序后的数组通过if判断消耗的时间会更少
    如果不经过排序,则直接位运算效率效率更高
    之所以排序后的数组会更快是因为它进行if判断,而if判断的效率非常的高,也就省去了前面不符合条件的sum+=data[i]
    而位操作,则每一个数据都需要进行位操作,也就是说所有数据都需要进行位操作。

    两者的时间差在于排序后的数据 if省去了不符合条件的时间
    位操作应该比+=效率更高,但是每一个数都进行位操作运算就相当于n个数* 位运算t1
    大于
    k个数(k<n)符合<128的数)进行时间就是(n-k)if判断时间t2+k*加法的时间t3


    总结

    位运算的确比+法效率高,但并不能说位操作就能替代if判断作用,得根据场景选择适合得算法。

    展开全文
  • C语言中位运算异或“∧”的作用

    万次阅读 多人点赞 2017-10-20 08:57:54
    它的规则是若参加运算的两个二进位同号,则结果为0(假);异号则为1(真)。即 0∧0=0,0∧1=1, 1^0=1,1∧1=0。 运算 说明 0^0=0,0^1=1 0异或任何数,其结果=任何数 1^0=1,1^1=0 1异或任何数,其...

    前言:

    为了方便查看博客,特意申请了一个公众号,附上二维码,有兴趣的朋友可以关注,和我一起讨论学习,一起享受技术,一起成长。

    在这里插入图片描述


    1.概念

    异或运算符"∧"也称XOR运算符。它的规则是若参加运算的两个二进位同号,则结果为0(假);异号则为1(真)。即 0∧0=0,0∧1=1, 1^0=1,1∧1=0。

    运算 说明
    0 ^ 0=0,0 ^ 1=1 0异或任何数,其结果=任何数
    1 ^ 0=1,1 ^ 1=0 1异或任何数,其结果=任何数取反
    x ^ x=0 任何数异或自己,等于把自己置0

    2.应用

    (1)使特定位翻转

    比如:01111010,想使其低4位翻转,即1变为0,0变为1。可以将它与00001111进行∧运算,即

    这里写图片描述

    结果值的低4位正好是原数低4位的翻转。要使哪几位翻转就将与其∧运算的该几位置为1即可。这是因为原数中值为1的位与1进行∧运算得0,原数中的位值0与1进行∧运算的结果得1。

    (2)实现两个值的交换

    通过按位异或运算,可以实现两个值的交换,而不必使用临时变量。例如交换两个整数a=3,b=4的值,可通过下列语句实现:

    a=a∧b;
    b=b∧a;
    a=a∧b;

    这里写图片描述

    #include <stdio.h>
    
    void main()
    {
    	int a=3,b=4;
    
    	 a=a^b;
    	 printf("first value %d\n",a);
    
    	 b=b^a;
    	 printf("second value %d\n",b);
    
    	 a=a^b;
    	 printf("third value %d\n",a);
    
    }
    

    这里写图片描述

    参考:

    1.C语言中位运算符异或“∧”的作用

    2.C语言异或运算

    展开全文
  • Java 位运算和模运算到底哪个快?修改 之前在看 ```HashMap``` 的源代码和相关博客。 看到了```HashMap```中有关```HashMap```容器大小和```indexFor()```中的方法。 1. ```HashMap```为什么长度规定需要...
  • 回顾首先来回顾一下这些运算: - &(与运算):只有当两方都为 true 时,结果才是 true,否则为 false。 - |(或运算):只要当一方为 true 时,结果就是 true,否则为 false。 - ^(异或运算):只要两方不同,...
  • 1基本运算功能 主要包括:加、减,乘、除、取余、自增、自减...4.位运算功能 主要包括:按位与、按位或、按位异或、按位取反、左移和右移。 5.进制转换功能 主要包括:包括十进制转其他进制、二进制转其他进制
  • 赋值运算与位运算

    万次阅读 2016-05-10 21:13:39
    求下面程序结果: #include using namespace std; int main() { int x=2,y,z; x*=(y=z=5); cout; x==(y=z); cout; x=(y==z); cout; x=(y&
  • Java进制转换和位运算专题

    千人学习 2019-05-14 21:28:37
    本课程是零基础学JAVA课程的第二阶段的课程,课程内容...内容包括:Java中的进制转换原理,十进制和二进制、八进制、十六进制的互相转换规律,位运算原理,按位与、按位或、按位取反、左移、右移、无符号右移的讲解!
  • java位运算>>>负位运算

    2016-05-17 08:28:33
    请教大神 -100 >>> -1 -100 >>> 1 如何计算的
  • * 我知道位运算是什么,怎么运算的,但我实在看不懂别人写的位运算代码,求高人指点我如何才能看懂别人写的位运算代码? * * 希望能得到详细的回答,除了将这个类的所有位运算都解释一遍,还请将位运算在java...
  • PHP位运算用途

    千次阅读 2013-10-23 17:27:06
    我这里说到的权限管理办法是一个普遍采用的方法,主要是使用到”运行符”操作,& 与运算符、| 或运行符。参与运算的如果是10进制数,则会被转换至2进制数参与运算,然后计算结果会再转换为10进制数输出。 它...

空空如也

1 2 3 4 5 ... 20
收藏数 61,572
精华内容 24,628
关键字:

位运算