位运算 订阅
程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。比如,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、给俺点个赞呗,可以让更多的人看到这篇文章,顺便激励下我,嘻嘻。

    在这里插入图片描述

    作者简洁

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

    展开全文
  • 位运算 - 初见

    千次阅读 多人点赞 2020-07-10 14:48:59
    以前也多多少少接触过一点位运算,课本上,LeetCode上,但是就是没有动手实操过,因为没遇到那个场景。。 我一度不知道位运算干嘛用,昨天在《编程珠玑》上看到一个位运算解决大数排序的问题,突然我就对这个技术有...

    在这里插入图片描述

    以前也多多少少接触过一点位运算,课本上,LeetCode上,但是就是没有动手实操过,因为没遇到那个场景。。
    我一度不知道位运算干嘛用,昨天在《编程珠玑》上看到一个位运算解决大数排序的问题,突然我就对这个技术有了兴趣。

    位运算 VS 普通运算

    其实我个人觉得没有什么可比性,这两种运算,要说它们属于不同领域也是可以的,位运算是位运算,普通运算是普通运算。
    不过吧,位运算快一点,程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了,就是直接对整数在内存中的二进制位进行操作。
    由于位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快。
    但是吧,数据量小的时候也看不出什么区别来,不过数据量大的话,嘿嘿,我也没试过。

    多学点总是好的,技多不压身嘛。

    位运算运算符

    按位与 &

    相同位的两个数字都为1,则为1;若有一个不为1,则为0。

    示例:6&11

    	0 1 1 0
    	1 0 1 1
    &-----------
    	0 0 1 0 = 2
    

    and运算通常用于二进制的取位操作。
    小技巧:一个数 and 1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶,二进制的最末位为0表示该数为偶数,最末位为1表示该数为奇数。

    更多技巧慢慢看,在后面。

    按位或 |

    相同位只要一个为1即为1。

    示例:6 | 11

    	0 1 1 0
    	1 0 1 1
    | ----------- 
    	1 1 1 1 = 15
    

    or运算通常用于二进制特定位上的无条件赋值。
    小技巧:一个数or 1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0,对这个数or 1之后再减一就可以了,其实际意义就是把这个数强行变成最接近的偶数。

    更多技巧慢慢看,在后面。

    按位异或 ^

    两个位相同为0,相异为1

    示例:6 ^ 11

    	0 1 1 0
    	1 0 1 1
    ^ -----------
    	1 1 0 1 = 13
    

    ^运算通常用于翻转指定位。
    小技巧:将数 X=1010 1110 的低4位进行翻转,只需要另找一个数Y,令Y的低4位为1,其余位为0,即Y=0000 1111,然后将X与Y进行异或运算(X^Y=1010 0001)即可得到。

    更多技巧慢慢看,在后面。

    按位取反

    not运算的定义是把内存中的0和1全部取反。

    示例:~ 6

    使用按位取反运算符,要知道几点:
    1、内存中,一个int,4个字节,1字节8位。
    2、有符号整数的按位取反情况略有偏差。

    	00000000 00000000 00000000 00000110
    ~ --------------------------
    	11111111 11111111 11111111 11111001
    

    小技巧:可以用~使每个数的最低位为0,方法:a & ~1

    别问我上面为什么不用这么长,我也不知道。我猜,是我不想写这么长哈哈哈。

    左移位运算符 <<

    将一个运算对象的各二进制位全部左移若干位(左边的二进制位丢弃,右边补0)。

    示例:6 << 2

    		0 1 1 0
    <<2 ------------
    	0 1 1 0 0 0 = 24
    

    小技巧:若左移时舍弃的高位不包含1,则每左移一位,相当于该数乘以2。

    右移位运算符 >>

    将一个数的各二进制位全部右移若干位,正数左补0,负数左补1,右边丢弃。

    示例: 6 >> 2

    		0 1 1 0
    >>2 -------------
    		0 0 0 1 = 1
    

    小技巧:操作数每右移一位,相当于该数除以2。

    负数的二进制表示

    既然都讲到这里了,那自然要了解一下负数的表示形式了。

    ==用字节的最高位表bai示:“1"表示"正”,“0"表示"负” ==

    1、把补码“取反”(把二进制数的各位“1”换“0”,“0”换“1”。比如“101010”取反后为“010101”)
    2、把取反后的二进制数“加1”

    示例:-17 转码
    再转回来

    -17转码:

    1700000000 00000000 00000000 00010001
    反码:	11111111 11111111 11111111 11101110
    转码:	11111111 11111111 11111111 11101111
    

    转回来自己动手。

    所以C++中int的取值范围为:-2^31~2^31-1


    投机

    异或的几条性质

    1、交换律
    2、结合律(即(a^b)^c == a^(b^c)3、对于任何数x,都有x^x=0,x^0=x
    4、自反性:  a^b^b=a^0=a;
    

    位运算实现乘除

    上面有

    位运算实现swap

    //普通操作
    void swap(int &a, int &b) {
      a = a + b;
      b = a - b;
      a = a - b;
    }
    
    //位与操作
    void swap(int &a, int &b) {
      a ^= b;
      b ^= a;
      a ^= b;
    }
    

    呐,我来试试分析:

    a ^= b  -->  a = a^b
    b ^= a  -->  b = b^a^b = a
    a ^= b  -->  a = a^b^a = b
    

    挺秀的啊,不过有的人说这样会出问题,比方说 a = b 的时候。
    那我再来分析一下:

    a ^= b  -->  a = a^b = 0
    b ^= a  -->  b = b^a^b = a = 0
    a ^= b  -->  a = a^b^a = b = 0
    

    哦,确实,他是对的。
    都说是投机了,大家看着用吧,下面的其他投机技巧也说不定会是地雷哦。

    位操作判断奇偶数

    只要根据数的最后一位是 0 还是 1 来决定即可,为 0 就是偶数,为 1 就是奇数。

    if(0 == (a & 1)) {
     //偶数
    }
    

    位操作交换符号交换符号

    将正数变成负数,负数变成正数

    int reversal(int a) {
    	return ~a + 1;
    }
    

    整数取反加1,正好变成其对应的负数(补码表示);负数取反加一,则变为其原码,即正数5. 位操作求绝对值整数的绝对值是其本身,负数的绝对值正好可以对其进行取反加一求得,即我们首先判断其符号位(整数右移 31 位得到 0,负数右移 31 位得到 -1,即 0xffffffff),然后根据符号进行相应的操作

    int abs(int a) {
    	int i = a >> 31;
    	return i == 0 ? a : (~a + 1);
    }
    

    上面的操作可以进行优化,可以将 i == 0 的条件判断语句去掉。我们都知道符号位 i 只有两种情况,即 i = 0 为正,i = -1 为负。对于任何数与 0 异或都会保持不变,与 -1 即 0xffffffff 进行异或就相当于对此数进行取反,因此可以将上面三目元算符转换为((a^i)-i),即整数时 a 与 0 异或得到本身,再减去 0,负数时与 0xffffffff 异或将 a 进行取反,然后在加上 1,即减去 i(i =-1)

    int abs2(int a) {
        int i = a >> 31;
        return ((a^i) - i);
    }
    

    位操作统计二进制中 1 的个数

    统计二进制1的个数可以分别获取每个二进制位数,然后再统计其1的个数,此方法效率比较低。这里介绍另外一种高效的方法,同样以 34520 为例,我们计算其 a &= (a-1)的结果:

    第一次:计算前:1000 0110 1101 1000 计算后:1000 0110 1101 0000
    第二次:计算前:1000 0110 1101 0000 计算后:1000 0110 1100 0000
    第三次:计算前:1000 0110 1100 0000 计算后:1000 0110 1000 0000 
    

    我们发现,没计算一次二进制中就少了一个 1,则我们可以通过下面方法去统计:count = 0

    while(a){  
        a = a & (a - 1);  
        count++;  
    }
    

    用 O(1) 时间检测整数 n 是否是 2 的幂次

    N如果是2的幂次,则N满足两个条件。

    1.N >0
    2.N的二进制表示中只有一个1
    

    因为N的二进制表示中只有一个1,所以使用N & (N - 1)将N唯一的一个1消去,应该返回0。

    数组中,只有一个数出现一次,剩下都出现两次,找出出现一次的数

    因为只有一个数恰好出现一个,剩下的都出现过两次,所以只要将所有的数异或起来,就可以得到唯一的那个数。(异或自反性)

    但当涉猎

    1
    a&a=a
    a^a=0
    
    2
    a&0=0
    a|0=a
    a^0=a
    
    3
    a|(a&b)=a
    a&(a|b)=a
    
    4、交换值
    a^=b;
    b^=a;
    a^=b;
    
    5、判断奇偶(取出最后一位)
    a &1
    等价于a%2(结果等于,位运算效率高)
    
    6、比较两值是否相等
    a^b==0
    
    7、i+1位置1
    a |=1<<i
    
    8、i+1位置0
    a &=~(1<<i)
    
    9、取出i+1(联系第5)
    a & (1<<i)
    
    10、在对应i+1位,插入b的对应位;
    a |=1<<i; (a的bit位置1)
    a & (b & 1<<i) (与b的bit位相与)
    
    11、删除最后的1;
    a & (a-1)
    
    12、负数
    a = ~a+1
    
    13、仅保留最后一-1
    a&(-a)
    
    14、得到全1
    ~0
    
    15、保留最后i-1位
    a & ((1<<i)-1)
    
    16、清零最后i-1位
    a & ~((1<<i)-1)
    
    

    以上,为最常见的用法,不带循环,全部O(1)。

    这个要常回来看看啊。

    一个大数去重的栗子

    如何对10亿个QQ号进行去重


    初次见面,先打基础,待我这两天去LeetCode上包装一下。
    待我包装完,试试看用位运算进行排序能不能写出来。

    位图

    不急。。

    过两天就写,估计也会是粉丝可见咯

    展开全文
  • 位运算基础

    千次阅读 多人点赞 2020-01-09 00:40:15
    什么是位运算2.位运算有哪些3.常用的位运算操作 1.什么是位运算 位运算又称为位操作,指的是直接对二进制位进行的一系列操作。 2.位运算有哪些 AND( & ) 按位与 1 & 1 = 0 1 & 0 = 0 0 & 0 = 1 ...

    基础知识和算法合集:https://blog.csdn.net/GD_ONE/article/details/104061907

    1.什么是位运算

     位运算又称为位操作,指的是直接对二进制位进行的一系列操作。
    

    2.位运算有哪些

    1. AND( & )
      按位与
      1 & 1 = 1
      1 & 0 = 0
      0 & 0 = 0
      1101 & 1100 = 1100

    2. OR( | )
      按位或
      1 | 1 = 1
      1 | 0 = 1
      0 | 0 = 0
      1001 | 1010 = 1011

    3. XOR( ^ )
      按位异或
      1 ^ 1 = 0
      0 ^ 0 = 0
      1 ^ 0 = 1
      0 ^ 1 = 1
      1101 ^ 1100 = 0001

    4. NOT( ~ )
      取反
      ~1 = 0
      ~0 = 1
      ~0111 = 1000
      另:& | ^ ~ 是c或类c的编程语言中所用的位操作符。 除了~是单目运算符
      其余的三个都是双目运算符。

    5. 移位运算

      • 左移运算符: <<

        二进制表示下把数字同时向左移, 低位以0填充, 高位越界后舍弃。

      • 右移运算符: >>
        右移运算又分为算术右移和逻辑右移。
        • 算术右移:

          在二进制补码表示下,把数字同时向右移位,高位以符号位填充,低位越界后舍弃。

          对于 n >> 1 在C/C++中相当于 n/2 下取整。

        • 逻辑右移:

          在二进制补码表示下把数字同时向右移动,高位以0填充,低位越界后舍弃。

          C++并没有规定右移的方式,所以编译器不同,可能实现的方式也不一样。
          不过说了这么多,总结下来其实就是:
          00001 << 2 = 00100
          00100 >> 2 = 00001

    3.常用的位运算操作

    1. (n>>k) &1 取出整数n在二进制表示下的第k位

    2. n & ((1 << k) - 1) 取出整数n在二进制表示下的第0~k-1位(后k位)

    3. n ^ (1 << k) 把整数n在二进制表示下的第k位取反

    4. n | (1 << k) 把整数n在二进制表示下的第k位赋值为1

    5. n & (~(1 << k)) 把整数n在二进制表示下的第k位赋值为0

    6. n ^ (1 << k) = n - (1<<k)

    7. 除以2
      a / 2 = a >> 1
      a + b / 2 == a + b >> 1 ( + - 运算的优先级高于 <<, >> )

    8. 判断奇偶
      一个数的二进制数的最低位如果是1 则该数一定是奇数 否则一定是偶数
      所以 用 a & 1 检测最低为是否位1

      if(a & 1) cout<<"奇数";
      else cout<<"偶数" 
      
    9. 快速幂

    10. 状态压缩
      以一个二进制数表示一个状态集合。
      如 n = 1100 S = {2, 3} S表示状态所有为1的集合。

    11. 成对变换

      当n 为偶数时 n ^ 1 = n + 1
      当n为奇数时 n ^ 1 = n - 1
      所以
      (0,1) (2, 3) (4, 5)… 关于 ^1 运算 构成“成对变换”
      这一性质常用于图论邻接表中边集的存储。在具有无向边(双向边)的图中把一对正反方向的边分别存储在邻接表数组中的第n和第n+1位置(n为偶数),就可以通过^1
      的运算获得与当前边(x, y) 反向的边(y, x)的存储位置。
      摘自<<算法竞赛进阶指南>>

    12. lowbit运算

      lowbit(n) 定义为非负整数n在二进制表示下"最低为1及其后边所有0"构成的数值. 例如 n = 10
      的二进制表示为(1010)2, 则lowbit(n) = 2 = (10)2 .
      lowbit(n) = n & (~n + 1) = n&(-n)
      摘自<<算法竞赛进阶指南>>

    展开全文
  • java位运算

    千次阅读 2019-01-24 19:16:46
    java中的位运算,涉及到计算机二进制,位用bit表示,1 byte=8bit,根据各种基本数据类型占用的字节空间,可以计算各种数据有多少位二进制,可以算出对应的取值范围。 java中的位运算包括:与(&)运算,或(|)...
  • 位运算与逻辑运算

    千次阅读 2018-01-04 19:14:11
    小白开始学习编程,计算机基础知识很是薄弱,于是打开百度,恶补好多,下面我们讲讲位运算与逻辑运算的区别。  首先从概念上区分下,位运算是将运算符两边的数字换算成二进制(例:0000010001)后比较相同位置...
  • 位运算 学习笔记

    千次阅读 多人点赞 2021-01-28 14:44:11
    位运算 应用 快速幂 标记状态 —— 动态规划 用异或实现配偶 lowbit 运算 功能 示例 位运算 运算符 去掉最后一位 (101101->10110) x shr 1 x>>1 在最后加一个0 (101101->1011010) x shl 1 x...
  • 位运算和取模运算的运算效率对比

    千次阅读 2019-09-25 07:19:16
     总说计算机是擅长于做位运算的,那么到底它有多擅长呢?  通过简单的测试,来探究一样位运算和取模运算的运算效率对比。 一、测试代码: 1 public class BitAndModulus { 2 @Test 3 public void bit() ...
  • 位运算——异或运算

    千次阅读 2020-01-07 17:25:26
    今天刷题时遇到一个题,本以为是暴力+大模拟,结果看完别人的AC代码后人都傻了,竟然是位运算。其中用到了异或^这种运算符。 先上原题连接 :传送门 题目意思很好理解,有无限多个路灯,编号为1.2.3…刚...
  • 文章目录一、位运算符1.1按位取反1.2按位与1.3按位或1.4按位异或二、移位运算符2.1左移运算符2.2右移运算符三、类型转换详解四、详解释多种位运算实例分析 一、位运算符 1.1按位取反 按位取反~:作用是按位将0变成1...
  • 数字的位运算

    万次阅读 2020-02-14 19:07:18
    数字的位运算问题描述(一)问题分析正向分析python代码扩展分析问题描述(二)题目分析暴力求解位运算求解python代码总结   在做算法题的时候,如果涉及到数字的判断问题,通常来讲,如果能有效利用数字的位操作...
  • 逻辑运算与位运算

    千次阅读 2018-04-14 20:19:38
    总是将逻辑运算与位运算混淆,于是乎,在这里进行总结一下! 1.逻辑运算 逻辑运算又称布尔运算,它的结果应该是一个真假值,也就是true还是false。 1)&amp;&amp;:与运算,同为真时才为真。 2&gt...
  • 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异或任何数,其...
  • &运算(位运算

    万次阅读 2018-08-28 13:14:15
    给大家举个列子:  8的二进制是1000 7的二进制是0111  1000  0111  &amp;运算中1&...并且按位置对应运算的,也就是说第一位和第一位运算,其他类推 所以可以得出0000,故输出的是0。...
  • python之位运算

    万次阅读 2019-06-10 14:16:27
    位运算,计算机内所有的数都以二进制存储,位运算就是对二进制位的操作 位运算符 说明 << 按位左移,左移n位相当于乘以2的n次方 >> 按位右移 ,左移n位相当于除以2的n次方 & 按位与,二...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 69,369
精华内容 27,747
关键字:

位运算