位运算_位运算符 - CSDN
位运算 订阅
程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。比如,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都是整数类型,则:
收起全文
精华内容
参与话题
  • 【技巧总结】位运算装逼指南

    万次阅读 多人点赞 2020-02-21 13:09:15
    位算法的效率有多快我就不说,不信你可以去用 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、给俺点个赞呗,可以让更多的人看到这篇文章,顺便激励下我,嘻嘻。

    在这里插入图片描述

    作者简洁

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

    展开全文
  • 位运算——强大得令人害怕

    万次阅读 多人点赞 2018-12-14 17:56:32
    先言众所周知,位运算是我们学计算机必学的东西,前人用二进制、位运算给我们了一个操作简单的计算机,但我们却很少接触位运算了。今天介绍一些位运算在算法中的运用。位运算基础 &amp;amp; 按位与 如果两个...

    前言

    众所周知,位运算是我们学计算机必学的东西,前人用二进制、位运算给我们了一个操作简单的计算机,但我们却很少接触位运算了。今天介绍一些位运算在算法中的运用。

    位运算基础

    • &
      • 按位与
      • 如果两个相应的二进制位都为1,则该位的结果值为1,否则为0
    • |
      • 按位或
      • 两个相应的二进制位中只要有一个为1,该位的结果值为1
    • ^
      • 按位异或
      • 若参加运算的两个二进制位值相同则为0,否则为1
    • ~
      • 取反
      • ~是一元运算符,用来对一个二进制数按位取反,即将0变1,将1
    • <<
      • 左移
      • 用来将一个数的各二进制位全部左移N位,右补0
    • >>
      • 右移
      • 将一个数的各二进制位右移N位,移到右端的低位被舍弃,对于无符号数, 高位补0

    奇技淫巧

    1.技巧一:用于消去x的最后一位的1

    x & (x-1)
    x = 1100
    x-1 = 1011
    x & (x-1) = 1000
    

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

    • 思路解析:N如果是2的幂次,则N满足两个条件。
      1.N>0
      2.N的二进制表示中只有一个1
      一位N的二进制表示中只有一个1,所以使用N&(N-1)将唯一的一个1消去。
      如果N是2的幂次,那么N&(N-1)得到结果为0,即可判断。

    1.2.应用二 计算在一个 32 位的整数的二进制表示中有多少个 1.

    • 思路解析:
      由 x & (x-1) 消去x最后一位知。循环使用x & (x-1)消去最后一位1,计算总共消去了多少次即可。

    1.3.将整数A转换为B,需要改变多少个bit位

    • 思路解析
      这个应用是上面一个应用的拓展。
      思考将整数A转换为B,如果A和B在第i(0<=i<32)个位上相等,则不需要改变这个BIT位,如果在第i位上不相等,则需要改变这个BIT位。所以问题转化为了A和B有多少个BIT位不相同。联想到位运算有一个异或操作,相同为0,相异为1,所以问题转变成了计算A异或B之后这个数中1的个数。

    2.技巧二 使用二进制进行子集枚举

    应用.给定一个含不同整数的集合,返回其所有的子集

    样例

    如果 S = [1,2,3],有如下的解:
    [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2] ]

    思路

    思路就是使用一个正整数二进制表示的第i位是1还是0,代表集合的第i个数取或者不取。所以从0到2n-1总共2n个整数,正好对应集合的2^n个子集。

    S = {1,2,3}
    N bit Combination
    0 000 {}
    1 001 {1}
    2 010 {2}
    3 011 {1,2}
    4 100 {3}
    5 101 {1,3}
    6 110 {2,3}
    7 111 {1,2,3}
    

    解题代码

    之后补充。

    技巧三.a^b^b=a

    3.1.应用一 数组中,只有一个数出现一次,剩下都出现三次,找出出现一次的。

    问题

    Given [1,2,2,1,3,4,3], return 4

    解题思路

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

    C语言解题代码
    #include<stdio.h>
    int main()
    {
        int a[7]={1,2,2,1,3,4,3};
        int ans=0;
        for(int i=0;i<7;i++){
            ans^=a[i];
        }
        printf("%d\n",ans);
    }
    

    3.2.应用二 数组中,只有一个数出现一次,剩下都出现三次,找出出现一次的。

    问题

    Given [1,1,2,3,3,3,2,2,4,1] return 4

    解题思路

    因为数是出现三次的,也就是说,对于每一个二进制位,如果只出现一次的数在该二进制位为1,那么这个二进制位在全部数字中出现次数无法被3整除。
    模3运算只有三种状态:00,01,10,因此我们可以使用两个位来表示当前位%3,对于每一位,我们让Two,One表示当前位的状态,B表示输入数字的对应位,Two+和One+表示输出状态。

    0 0 0 0 0
     0 0 1 0 1
     0 1 0 0 1
     0 1 1 1 0
     1 0 0 1 0
     1 0 1 0 0
     One+ = (One ^ B) & (~Two)
     Two+ = (~One+) & (Two ^ B)
    
    C语言解题代码
    #include<stdio.h>
    
    void findNum(int *a,int n)
    {
        int one=0;
        int two=0;
        int i,j,k;
        for(i=0;i<n;i++){
            two=two|(one&a[i]);
            one=one^a[i];
            int three=two&one;
            two=two^three;
            one=one^three;
        }
        printf("%d\n",one|two);
    }
    int main()
    {
        int a[10]={1,1,2,3,3,3,2,2,4,1};
        findNum(a,10);
    }
    

    另外一种容易理解的方法

    #include<stdio.h>
    
    void findNum(int *a,int n)
    {
        int ans=0;
        int bits[32]={0};
        for(int i=0;i<n;i++){
            for(int j=0;j<32;j++){
                bits[j]+=((a[i]>>j)&1);
            }
        }
        for(int i=0;i<32;i++){
            if(bits[i]%3==1) ans+=1<<i;
        }
        printf("%d\n",ans);
    }
    int main()
    {
        int a[10]={1,1,2,3,3,3,2,2,4,1};
        findNum(a,10);
    }
    

    3.3.应用三 数组中,只有两个数出现一次,剩下都出现两次,找出出现一次的

    问题

    Given [1,2,2,3,4,4,5,3] return 1 and 5

    解题思路

    有了第一题的基本的思路,我们不妨假设出现一个的两个元素是x,y,那么最终所有的元素异或的结果就是res = x^y。并且res!=0,那么我们可以找出res二进制表示中的某一位是1,那么这一位1对于这两个数x,y只有一个数的该位置是1。对于原来的数组,我们可以根据这个位置是不是1就可以将数组分成两个部分。求出x,y其中一个,我们就能求出两个了。

    C语言解题代码
    #include<stdio.h>
    
    void findNum(int *a,int n)
    {
        int ans=0;
        int pos=0;
        int x=0,y=0;
        for(int i=0;i<n;i++)
            ans^=a[i];
        int tmp=ans;
        while((tmp&1)==0){
        //终止条件是二进制tmp最低位是1
                pos++;
                tmp>>=1;
        }
        for(int i=0;i<n;i++){
            if((a[i]>>pos)&1){//取出第pos位的值
                x^=a[i];
            }
        }
        y=x^ans;
        if(x>y) swap(x,y);//从大到小输出x,y
        printf("%d %d\n",x,y);
    }
    int main()
    {
        int a[8]={1,2,2,3,4,4,5,3};
        findNum(a,8);
    }
    

    另外一种写法

    #include<stdio.h>
    
    void findNum(int *a,int n)
    {
        int diff=0;
        int x=0,y=0;
        for(int i=0;i<n;i++){
                diff^=a[i];
        }
        diff&=-diff;//取diff的最后一位1的位置
        for(int i=0;i<n;i++){
            if((a[i]&diff)==0){
                x^=a[i];
            }else y^=a[i];
        }
        if(x>y) swap(x,y);
        printf("%d %d\n",x,y);
    }
    int main()
    {
        int a[10]={1,2,2,3,4,4,5,3};
        findNum(a,8);
    }
    

    参考自大神:
    微信:ninechapter。

    展开全文
  • 位运算

    2020-02-23 19:41:29
    位运算 &(与)、|(或)、^(异或)、~ (非 / 取反) >> 和 <<运算符将二进制为进行右移或者左移操作 >>>运算符将用0填充高位;>>运算符用符号位填充高位,没有<<<...

    位运算基础

    • &(与)、|(或)、^(异或)、~ (非 / 取反)
    • >><<运算符将二进制为进行右移或者左移操作
    • >>>运算符将用0填充高位;>>运算符用符号位填充高位,没有<<<运算符
    • 对于int型,1<<35 与 1<<3是相同的

    位运算的一些巧妙用法

    • 判断奇偶数:x & 1 = 1 为奇数 ,= 0为偶数
    • 交换两个整数变量的值
     public static void main(String[] args) {
            int a = 5;
            int b = 3;
            a = a ^ b;
            b = a ^ b;
            a = a ^ b;
            System.out.println(a);
            System.out.println(b);     
        }
    }
    
    • 获取二进制位是1还是0
        public static void main(String[] args) {
        	int x = 4;  //二进制为0100
        	int y = 3;
        	System.out.println(x + "的第" + y + "位的二进制位为:" + ( ((x & (1<<(y-1)))>>(y-1)) == 0 ? "0":"1"));
        } 	  
       }
    

    在这里插入图片描述

    • 不用判断语句,求整数的绝对值

    原理:将一个整型整数x,带符号右移31位,则结果要么是0,要么是-1。如果是0,则x为正数,为-1则x为负数。
    然后,将x与右移31位后的结果做异或运算,当与x^0是,结果还是x。 当x^-1时,结果为x取反,即x的反码,然后+1,即为x的绝对值。

       public static void main(String[] args) {
        	int x = -35;
        	System.out.println( x>>31 == -1 ? (x ^ (x >> 31))+1 : (x ^ (x >> 31)));
        } 	  
       }
    
    • 异或,可以理解为不进位加法:1+1=0,0+0=0,1+0=1
      1.交换律:可任意交换运算因子的位置,结果不变
      2.结合律:(a ^ b)^ c == a ^ (b ^ c)
      3.对于任何数x, 都有x ^ x = 0, x ^ 0 = x, 同自己求异或为0,同0求异或为自 己
      4.自反性:A ^ B ^ B = A ^ 0 = A。

    位运算相关例题

    找出唯一成对的数

    ​ 1-1000这1000个数放在1001个元素的数组中,只有唯一的一个元素值重复,其他均只出现一次。每个数组元素只能访问一次,设计一个算法,将他找出来;不用辅助存储空间,能否设计一个算法实现?
    思路:利用异或的自反性, 将 这个数组 与 除去重复数的所有数 进行异或,最终结果就是那个重复值。

    public class Main{  
        public static void main(String[] args) {
        	int [] arr = {1,2,3,4,5,6,2};
        	int x = 0;
            //数组内的数进行异或
        	for(int i=0;i<arr.length;i++)
        		x ^= arr[i];
        	
        	//再与1到6数字进行异或
        	for(int i = 1;i<7;i++)
        		x ^= i;
        		
        	System.out.println(x);
        } 	  
       }
    

    二进制中1的个数

    请实现一个函数,输入一个整数,输出该数二进制表示中1的个数。
    例:9的二进制表示为1001,有2位是1.
    原理:(x-1) & x,利用该式可循环消去低位的1,循环了多少次,就有多少个1。

    public class Main{  
        public static void main(String[] args) {
        			int x = 4;
        			int count = 0;
        			while(x != 0) {
        				x = ((x-1) & x);
        				count++;
        			}
        			System.out.println(count); 
        		}
        	}
    

    是不是2的整数次方

    用一条语句判断一个整数是不是2的整数次方。(不考虑负整数次方)

    思路:转化为二进制问题:是否只有一个1,例如001000,0100000等,这种数就是2的整次方数,利用上一个例题的方法就可以解决这个问题。

    public class Main{  
    	public static void main(String[] args) {
    		is2(1024);
    		is2(1000);
    	}
    	
    	public static void is2(int x){
    		if(((x-1) & x) == 0) {
    			System.out.println(x + "是2的整数次方!");
    		}else {
    			System.out.println(x + "不是2的整数次方!");
    		}
    	}
    }
    
    展开全文
  • 位运算主要知识

    万次阅读 多人点赞 2017-02-25 12:33:56
    什么是位运算?  程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了,就是直接对整数在内存中的二进制位进行操作。  C++提供了6种位运算符来进行位运算操作: & 按位与 | 按位或 ^ 按位异或 ~ ...

    什么是位运算? 

    程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了,就是直接对整数在内存中的二进制位进行操作。 
    C++提供了6种位运算符来进行位运算操作:
    &      按位与
    |      按位或
    ^      按位异或
    ~      按位取反
    <<     左移(左边消失,右边补0)
    >>     右移(右边消失,左边补符号位)
    位运算的操作数是整数类型或字符型.

    按位与&运算

    将参与运算的两操作数各自对应的二进制位进行与操作。例如:6的二进制是110,11的二进制是1011,那么6 & 11的结果就是2 
        110
    &  1011
    ------------
       0010  -->  2
    & 运算常常用来将某变量的某些位清0,而保留其它位不变。例如,需要将int型变量n的低8位全置成0,而其余位不变,则用:
           n = n & 0xFFFFFF00
    & 也常用于二进制取位操作,例如一个数 & 1的结果就是取二进制的最末位。如果要判断n的第8位(从右往左,从1开始数)是否是1,则用:
                 if (n & 0x80 == 0x80)  语句
    附注:int型是32个二进制位,16进制整数每个数字代表4个二进制位,故16进制int型常量最多是8位。


    按位或|运算

     |运算通常用于二进制特定位上的强制置1,例如一个数或 1的结果就是把二进制最末位强行变成1。
          110
    |    1011
    ------------
         1111 -->  15

    按位异或^运算

    0^0=0  0^1=1  1^1=0
    ^运算通常用于对二进制的特定一位进行取反操作.例如n^0xff就使得n的最后8位取反。
        110
    ^  1011
    -----------
       1101   -->  13
    ^运算的特点是:如果a^b==c,则有a^c==b和c^b==a
    ^可用于简单加密,参见顾森BLOG


    左移<<运算

     a << b就表示把a转为二进制后左移b位(在后面添b个0)。例如100的二进制为1100100,而110010000转成十进制是400,那么100 << 2 = 400。可以看出,a << b的值实际上就是a乘以2的b次方,因为在二进制数后添一个0就相当于该数乘以2(这样做要求保证高位的1不被移出)。
    通常认为a << 1比a * 2更快,因为前者是更底层一些的操作。因此程序中乘以2的操作请尽量用左移一位来代替。
    定义常量时可以用<<运算。你可以方便地用(1 << 16) - 1来表示65535。很多算法和数据结构要求数据规模必须是2的幂,此时可以用<<来定义MAXN等常量。


    右移>>运算

    a >> b表示二进制右移b位(去掉末b位)。
    当a是正整数时,a>>b等价于a/(2的b次方)
    当a是负整数时,a>>b并不等价与a/(2的b次方),而是等于a/(2的b次方)上取整。
    如a=-9
    cout<<a/2; //输出-4.
    cout<<(a>>1); //输出-5.

    我们也经常用>> 1来代替div 2,比如二分查找、堆的插入操作等等。
    用>>代替除法运算可以使程序效率大大提高。最大公约数的二进制算法用除以2操作来代替慢得出奇的%运算,效率可以提高60%。
    二进制求最大公约数原理。
    若a<b         gcd(a,b)=gcd(b,a)
    若a、b都是偶数,则gcd(a,b)=2*gcd(a/2,b/2)
    若a是奇数、b是偶数,则gcd(a,b)=gcd(a,b/2)
    若a、b都是奇数,则gcd(a,b)=gcd((a-b)/2,b)


    位运算的简单应用 






    整数类型的储存 

    计算机用0x0000到0x7FFF依次表示0到32767的数,剩下的0x8000到0xFFFF依次表示-32768到-1的数。32位有符号整数的储存方式也是类似的。稍加注意你会发现,二进制的第一位是用来表示正负号的,0表示正,1表示负。这里有一个问题:0本来既不是正数,也不是负数,但它占用了0x0000的位置,因此有符号的整数类型范围中正数个数比负数少一个。对一个有符号的数进行~运算后,最高位的变化将导致正负颠倒,并且数的绝对值会差1。也就是说,~ a实际上等于-a-1。这种整数储存方式叫做“补码”。
    换言之,~a+1 = -a,那么a & -a得到什么?
    得到a的右数第1位为1的数,这个操作可用来枚举a中为1的位,这在位操作中有较多应用。

    展开全文
  • &运算(位运算

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

    2017-08-11 21:00:34
    所有的进制转换 http://jingyan.baidu.com/article/495ba84109665338b30ede98.html    //方法二  用位运算来进制转换 #include int main( ) {  intn;  while(scanf("%d",&n)!=EOF)  {
  • 位运算&进制转换工具

    2020-07-21 09:57:18
    本软件集合了位运算跟进制的转换,简单操作,方便软件工程人员使用,同时也适用于初学c语言的大学生,大学教师使用。
  • (就是在获取32二进制的每四,拿到二进制的最低四) 实现 代码实现 public static void BitCalc() { //获取60的二进制 System.out.println(Integer.toBinaryString(60)); int num =60; int n1 = num...
  • 进制转换 和 位运算

    2020-06-27 21:25:12
    十进制转化为二进制 例如十进制数’155’转化为二进制数: 常规操作是把155连续除以2取余倒置相加,但有时十进制数过...位运算 按位与’&‘ 0和1为0,1和1为1,0和0为0 按位或’|‘ 0和1为1,1和1为1,0和0为0 ...
  • 位运算和进制转换

    2020-03-19 14:34:58
    位运算指的是对二进制进行的计算处理。主要有 与(&)、或(|)、异或(^)、求反(~) 与运算 其特征为:“都是1的时候才是1” 如: 13 & 7 = 计算过程为: 13的二进制:1101 7的二进制: 0111 得到...
  • 算法:位运算

    千次阅读 2017-06-08 10:38:45
    lz所以3进制在一般计算机应该不能进行操作吧。基本的操作符有与、或、异或、取反、左移、右移这6种,它们的运算规则如下所示:符号 描述 运算规则& 与两个都为1时,结果才为1| 或 两个都为0时,结
  • 位运算(按位与、按位或、异或)

    万次阅读 多人点赞 2018-07-19 09:19:17
    参加运算的两个数,按二进制进行“与”运算运算规则:只有两个数的二进制同时为1,结果才为1,否则为0。(负数按补码形式参加按运算) 即 0 &amp; 0= 0 ,0 &amp; 1= 0,1 &amp; 0= 0, 1 &...
  • 参加运算的两个数据,按二进制进行“与”运算运算规则:0&0=0; 0&1=0; 1&0=0; 1&1=1;  即:两同时为“1”,结果才为“1”,否则为0 例如:3&5 即 0000 0011& 0000 0101 = 00000001 因此,3&5的值得1...
  • 位运算 实现加法

    万次阅读 多人点赞 2011-10-09 15:23:48
    位运算实现加法也就是计算机用二进制进行运算,32位的CPU只能表示32位内的数,这里先用1位数的加法来进行,在不考虑进位的基础上,如下 1 + 1 = 0 1 + 0 = 1 0 + 1 = 1 0 + 0 = 0 很明显这几个...
  • 参加运算的两个数据,按二进制进行运算. 例如:3&amp;5 先将两个数据转化为二进制数,然后按进行与运算,同为1结果为1,其它情况结果为0; 即:11&amp;101=001结果为1 特别提醒:负数按补码...
  • Python 位运算及二进制基础知识

    万次阅读 2016-06-26 19:09:42
    来补点基础知识,这篇讲的是位运算 二进制实际上就是用10进制的数的每一位数字的2的幂数 来看例子: 然后再python的操作中,只要在数字前面加上0b的字符,就可以用二进制来表示十进制数了。
  • 与、或、异或等运算方法

    万次阅读 多人点赞 2012-03-23 15:00:08
    与运算符(&)参加运算的两个数据,按二进制进行“与”运算运算规则:0&0=0; 0&1=0; 1&0=0; 1&1=1; 即:两同时为“1”,结果才为“1”,否则为0例如:3&5 即 0000 0011 & 0000 0101 = 0000 0001 ...
  • 用C语言讲一讲位运算 入门级(详细图解)

    万次阅读 多人点赞 2016-04-23 22:08:47
    程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了,就是直接对整数在内存中的二进制位进行操作。
  • 位运算实例(一):判断奇偶性

    万次阅读 2009-09-23 11:22:00
    同样一个问题,位运算可以提高程序的运行效率。下面讲一下关于奇偶性的判断。 常规方法public static boolean isOdd(int i){ return i % 2 != 0;} 位运算方法public static boolean isOdd(int i){ return (i & 1...
  • 与、或、异或运算

    万次阅读 2016-08-05 20:02:47
    1、概念:参加运算的两个对象,按二进制进行“与”运算,负数按补码形式参加按运算。 2、运算规则:0&0=0; 0&1=0;1&0=0;1&1=1;即:两同时为“1”,结果才为“1”,否则为0【有0则0】  例如:3&5=1,即...
1 2 3 4 5 ... 20
收藏数 540,810
精华内容 216,324
关键字:

位运算