位运算 订阅
程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。比如,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时,我们很可能不能直接用二进制枚举出状态并储存。

    更多相关内容
  • 位运算大师级使用方法---位运算大师级使用方法---位运算大师级使用方法---位运算大师级使用方法---位运算大师级使用方法---位运算大师级使用方法---位运算大师级使用方法---位运算大师级使用方法---位运算大师级使用...
  • 【LeetCode】位运算

    千次阅读 2022-02-09 21:01:53
    最近刷了几道算法题,有一些是和位运算有关的,虽然位运算在源码中较多的出现,但个人仍认为其实操意义不大。不过不得不说,基于位运算的一些算法处理,有时候确实很神奇。因此做一个记录。

            最近刷了几道算法题,有一些是和位运算有关的,虽然位运算在源码中较多的出现,但个人仍认为其实操意义不大。不过不得不说,基于位运算的一些算法处理,有时候确实很神奇。因此做一个记录。

    备注:所有例子都以Java中int类型来说明。

    1.二进制与补码

            大家都知道,计算机中的一切都是用二进制来表示的,Java中以int为例,一般来说的32位的二进制数字。简单来说,正数的最高位为0,负数的最高位为1,另因为一些原因(具体见参考文档1),负数是使用补码来进行表示。我们可以使用Integer.toBinaryString()方法来查看一些常见的值,做一下直观理解。

    System.out.println(Integer.toBinaryString(1));  //1
    
    System.out.println(Integer.toBinaryString(-1)); //11111111 11111111 11111111 11111111
    
    System.out.println(Integer.toBinaryString(Integer.MAX_VALUE));  //1111111 11111111 11111111 11111111
    
    System.out.println(Integer.toBinaryString(Integer.MIN_VALUE));  //10000000 00000000 00000000 00000000

    2.常见的位运算符

    符号

    含义

    详解

    &

    位与

    两个比特位都为 1 时,结果才为 1,否则为 0 (位与操作满足交换律和结合律,甚至分配律)

    |

    位或

    两个比特位都为 0 时,结果才为 0,否则为 1 (位或操作满足交换律和结合律,甚至分配律)

    ~

    位非

    即按位取反,1 变 0,0 变 1

    ^

    异或

    两个比特位相同时(都为 0 或都为 1)为 0,相异为 1(异或操作满足交换律和结合律,甚至分配律。任何整数和自己异或的结果为 0,任何整数与 0 异或值不变)

    <<

    左移

    将所有的二进制位按值向←左移动若干位,左移操作与正负数无关,它只是傻傻地将所有位按值向左移动,高位舍弃,低位补 0

    >>

    右移

    将所有的二进制位按值向右→移动若干位,低位直接舍弃,跟正负无关,而高位补 0 还是补 1 则跟被操作整数的正负相关,正数补 0 ,负数补 1

    >>>

    无符号右移

    将所有的二进制位按值向右→移动若干位,低位直接舍弃,跟正负无关,高位补 0 ,也跟正负无关

    3.位运算的一些常规操作

    这些操作看了都很容易理解,但自己去想,一般却想不出这些个用法。

    //判断奇数偶数
    public void isOddOrEven(int n){
        if ((n & 1) == 1) {//n是奇数
            System.out.println("Odd");
        }else {//n是偶数
            System.out.println("Even");
        }
    }
    
    //交换两数的值,无需中间变量
    public void swap(){
        int a = 1, b = 2;
        a ^= b;
        b ^= a;//b == 1
        a ^= b;//a == 2
        System.out.println("a:" + a);//a:2
        System.out.println("b:" + b);//b:1
    }
    
    //判断正数是不是2的幂
    public boolean isPowerOfTwo(int num) {
        if (num < 1) {
            return false;
        }
        return (num & (num - 1)) == 0;
    }

    4.上例题

    1---剑指 Offer 65. 不用加减乘除做加法,力扣

    写一个函数,求两个整数之和,要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

    示例:

            输入: a = 1, b = 1

            输出: 2

    提示:

            a, b 均可能是负数或 0

            结果不会溢出 32 位整数

    这种题初看真的很容易僵住。但我们找几个数出来试试,还是能找到点端倪。

    设两数字的二进制形式 a, b ,其求和 s = a + b ,a(i) 代表 a 的二进制第 ii位,则分为以下四种情况:

    a(i)

    b(i)

    无进位和 n(i)

    进位 c(i+1)

    0

    0

    0

    0

    0

    1

    1

    0

    1

    0

    1

    0

    1

    1

    0

    1

    观察发现,无进位和 与 异或运算 规律相同,进位 和 与运算 规律相同(并需左移一位)。通过反复的异或操作,到没有进位的时候,就可以实现加法,顺势可以写出以下代码。

    public static int add(int a, int b) {
        if (a == 0) {
            return b;
        }
        if (b == 0) {
            return a;
        }
        return add(a ^ b, (a & b) << 1);
    }

    2---136. 只出现一次的数字,力扣

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

    说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

    示例 1:

            输入: [2,2,1]

            输出: 1

            如果没有经过训练,或者提示本题目可以使用位运算,可能主要的思路还是排序或者哈希来记个数。翻翻位运算,可以很快的想到,两个相同的数异或后会清零,剩下的思路就很自然了。

    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }

    3---剑指 Offer 56 - I. 数组中数字出现的次数,力扣

     一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

    示例 1:

            输入:nums = [4,1,4,6]

            输出:[1,6] 或 [6,1]

    限制:

            2 <= nums.length <= 10000

            做了上面的,可能感觉有点东西,有点感觉了。这题咋一看和上一题基本一样,但凭空从一个数字变成了两个数字,如果也是全部异或一遍,只会得到两个出现一次的数字的异或,拿着似乎也没有用,着实有点下头。

            这时候,我们可能有个模糊的想法,能不能把数组分成两部分,两个待找出的数字放到两个数组中,两边再分别搭配一些出现了两次的数字,这样我们只需要把上一题玩两遍,就可以拿到答案了。

    public int[] singleNumbers(int[] nums) {
        int x = 0, y = 0, n = 0, m = 1;
        for(int num : nums)               // 1. 遍历异或
            n ^= num;
        while((n & m) == 0)               // 2. 循环左移,计算 m
            m <<= 1;
        for(int num: nums) {              // 3. 遍历 nums 分组
            if((num & m) != 0) x ^= num;  // 4. 当 num & m != 0
            else y ^= num;                // 4. 当 num & m == 0
        }
        return new int[] {x, y};          // 5. 返回出现一次的数字
    }

    5.练习

    题目编号题目名称难度链接
    leetcode 461汉明距离简单力扣
    剑指 Offer 15二进制中1的个数简单力扣
    面试题 17.04消失的数字简单力扣
    剑指 Offer 56 - II数组中数字出现的次数 II中等力扣
    leetcode 477汉明距离总和中等力扣
    leetcode 1879两个数组最小的异或值之和困难力扣

    6.关于位运算的效率

    实际编码中,显然没有人特别去使用位运算来提高所谓的执行效率。但在大部分人心中,位运算的效率理论上应高于一般的四则运算,但在笔者的实操中,并没有跑出预想中的结果,也没能查阅到确切的资料。这一点欢迎大家讨论。

    参考文档

    1.原码、反码、补码的产生、应用以及优缺点有哪些? - 知乎

    2.Java 位运算超全面总结 - antball - 博客园

    3.题解来源,力扣

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

    万次阅读 多人点赞 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 位运算详解

    千次阅读 2022-02-18 12:08:44
    一、Java中支持的位运算 二、位运算规则 三、逻辑运算 (一)、与运算(&)  一、运算规则  二、运算流程 (二)、或运算(|)  一、运算规则  二、运算流程 (三)、异或运算(^)  一、运算...

    目录

    一、Java中支持的位运算

    二、位运算规则

    三、逻辑运算

    (一)、与运算(&)

      一、运算规则

      二、运算流程

    (二)、或运算(|)

      一、运算规则

      二、运算流程

    (三)、异或运算(^)

      一、运算规则

       二、运算流程

    (四)、取反运算(~)

      一、运算规则

      二、运算规则

    四、位移操作

      (一)、左移(<<)

      (二)、右移(>>)

      (三)、无符号右移(>>>)


    一、Java中支持的位运算

    1. 位与(&):二元运算符,两个为1时结果为1,否则为0
    2. 位或(|):二元运算符,两个其中有一个为1时结果就为1,否则为0
    3. 位异或(^):二元运算符,两个数同时为1或0时结果为1,否则为0
    4. 位取非(~):一元运算符,取反操作
    5. 左移(<<):一元运算符,按位左移一定的位置。高位溢出,低位补符号位,符号位不变。
    6. 右移(>>):一元运算符,按位右移一定的位置。高位补符号位,符号位不变,低位溢出。
    7. 无符号右移(>>>):一元运算符,符号位(即最高位)保留,其它位置向右移动,高位补零,低位溢出。

    二、位运算规则

      Java数值运算过程中都是先将十进制转换为二进制然后再进行运算,再把二进制数据转换为十进制展现给用户。二进制运算规则如下:

      对于有符号的而言,

    • 最高位为符号位,0表示正数,1表示负数
    • 正数的原码,反码和补码都一样,三码合一
    • 负数的反码:符号位保持不限,其他位取反
    • 负数的补码:补码 + 1

    • 0的反码和补码都是0
    • 计算机的运算的时候,都是将原码转成补码进行运算

      下面以 -1 为例子展示原码、反码和补码的转换关系(以int数据类型为例,int类型在Java中占4字节):

      

    三、逻辑运算

    (一)、与运算(&)

      一、运算规则

        两个数相同位置的比特进行与运算,若两个位置均为1,那么结果就为1,否者为0

      二、运算流程

      以 4 & -5 = 0为例子展示运算流程:

      1. 因为4为正数,所以原码和补码相同,即4的补码为:00000000 0000000 00000000 00000100

      2.因为-5为负数,所以需要进行原码 >>> 反码 >>> 补码的转换

        1)原码:10000000 00000000 00000000 00000101

        2)反码:11111111 11111111 11111111 11111010

        3)补码:11111111 11111111 11111111 11111011

      3.将4和-5的补码进行 & 运算:00000000 0000000 00000000 00000100

                      11111111 11111111 11111111 11111011         &

                   00000000 00000000 00000000 00000000

      4.得到的补码结果为:00000000 00000000 00000000 00000000。所以结果为0

    (二)、或运算(|)

      一、运算规则

        两个数相同位置的比特进行或运算,若其中一个为1则结果为1,否个结果为0。

      二、运算流程

      以 -2 | 5 = -1为例展示运算流程:

      1.-2为负数,需要进行原码 > 反码 > 补码的转换。转换步骤如下: 

        1)原码:10000000 00000000 00000000 00000010

        2)符号位不变,其他位置取反得反码:11111111 11111111 11111111 11111101

        3)在反码的基础上+1得到补码: 11111111 11111111 11111111 11111110

      2.5为正数,补码和反码一致,所以5的补码为:00000000 00000000 00000000 00000101

      3.将-2 和 5 的补码进行或运算: 11111111 11111111 11111111 11111110

                   |    00000000 00000000 00000000 00000101 

                      11111111 11111111 11111111 11111111

      4.根据上面的运算得到补码结果为:11111111 11111111 11111111 11111111

      5.结果显然是一个负数,而负数的补码和原码不一致,所以需要将补码结果转换为原码才能得到最终的结果

      6.补码转原码的过程是跟原码转补码相反的过程,具体过程如下:

        1)补码:11111111 11111111 11111111 11111111

        2)补码 -1 得到反码:11111111 11111111 11111111 11111110

        3)符号位不变,其他位置取反得:10000000 00000000 00000000 00000001

      7.最终得到的原码结果为 10000000 00000000 00000000 00000001,转成十进制为 -1

    (三)、异或运算(^)

      一、运算规则

        两个数相同位置的比特进行或运算,若两个数均为0或1,则结果为0,否者为1.

     

       二、运算流程

        以 1 ^ -5 = 6 为例,具体运算流程如下:

        1.1的补码为:00000000 00000000 00000000 00000001

        2.-5的补码为:11111111 11111111 11111111 11111011(可参考与运算给出的流程)

        3.两个补码运算:  

              00000000 00000000 00000000 00000001

            ^     11111111   11111111   11111111    11111011

                11111111   11111111  11111111     11111010

        4.得到的补码结果为:11111111   11111111  11111111     11111010

        5.补码为负数,需要转换成原码:

          1)补码:11111111   11111111  11111111     11111010

          2)反码:11111111   11111111  11111111     11111001

          3)原码:10000000 00000000 00000000 000000110

        6.由原码:10000000 00000000 00000000 000000110,得出最终的时间结果为 -6.

    (四)、取反运算(~)

      一、运算规则

        若位数为0,则取反后为1,若为1,取反后为0。

      二、运算规则

        以~2 = -3为例运算流程如下:

        1.2的原码为:00000000 00000000 00000000 00000010

        2.2的补码跟原码一致也为:00000000 00000000 00000000 00000010

        3.取反:111111111 11111111 11111111 11111101

        4.取反后的结果仍未补码,此时补码为负数,则需要转成原码

        5. 11111111 11111111 11111111 11111101 - 1 得到反码:11111111 11111111 11111111 11111100

        6. 11111111 11111111 11111111 11111100 符号位不变,其他位置取反得到原码为:10000000 00000000 00000000 00000011

        7.  10000000 00000000 00000000 00000011 转成十进制结果为 -3

              

    四、位移操作

      (一)、左移(<<)

        规则:符号位不变,高位溢出截断,低位补零。比如 -1 << 2 = -4 (为方便讲解,图示的补码为-1)

      (二)、右移(>>)

        规则:符号位不变,低位溢出截断,高位用符号位填充。如:8 >> 2 = 2。

      (三)、无符号右移(>>>)

        规则:高位填充0,低位溢出。如-1>>>1=2147483647

    展开全文
  • C#位运算及运算符

    2012-10-16 12:07:13
    0、逻辑运算符 1、逻辑非运算 2、逻辑与运算 4、逻辑异或运算 5、左移运算 6、右移运算
  • 位运算 - 初见

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

    千次阅读 多人点赞 2019-06-06 17:47:01
    在位运算前,需要先了解二进制码相关知识,详情请见博主的另一篇博文:原码、反码、补码 Java定义了运算符,应用于整数类型(int),长整型(long),短整型(short),字符型(char),和字节类型(byte)等类型。 Java...
  • 数字的位运算

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

    千次阅读 2022-02-07 22:59:37
    1.位运算 处理数据类型的时候,可以直接对组成整型数值的各个位完成操作 &("and") |("or") ~("not") ^("xor”) ------------------------------------------------------------------------------ 以下...
  • 位运算(&、|、^、~、>>、)

    万次阅读 多人点赞 2021-01-22 16:39:49
    位运算(&、|、^、~、>>、<<) 1.位运算概述 从现代计算机中所有的数据二进制的形式存储在设备中。即0、1两种状态,计算机对二进制数据进行的运算(+、-、*、/)都是叫位运算,即将符号位共同参与运算...
  • 彻底搞清楚Java的位运算(位实现加减乘除)

    万次阅读 多人点赞 2019-12-23 20:27:19
    二进制位运算是最贴近计算机真实运算操作,通过位运算,我们可以高效的完成各种基础运算(加减乘除取余等),我们还可以使用位运算巧妙的完成原本很复杂的工作,真正理解计算机,我们才能更好的使用计算机。...
  • python位运算(&、|、^、~、>>、)

    千次阅读 2022-01-11 15:49:34
    位运算概览 符号 描述 运算规则 & 与 两个位都为1时,结果才为1 | 或 两个位都为0时,结果才为0 ^ 异或 两个位相同为0,相异为1 ~ 取反 0变1,1变0 << 左移 ...
  • 使用位运算&取余

    千次阅读 2021-03-10 08:15:35
    取余运算符为“%”。但在以前,CPU采用如下方法...所以可以使用位运算X & (2^N - 1)代替取余= 9 & ( 4 - 1 )= 9 & 3= 1001 & 0011= 0001= 1原理:二进制数乘以2^n,相当于左移n位;二进制数除以2...
  • C++ 算法篇 位运算

    万次阅读 多人点赞 2018-11-26 15:34:01
    1. 理解与掌握 C++ 中的位运算。 2. 灵活应用位运算优化程序。 任何信息在计算机中都是采用二进制表示的,数据在计算机中是以补码形式存储的,位运算就是直接对整数在内存中的二进制位进行运算。由于位运算直接对...
  • php的位运算详解

    千次阅读 2021-03-23 12:47:38
    php的运算符有一类是位运算的,本文主要和大家分享php的位运算详解,希望能帮助到大家。一:& And按位与$a&$b 将把二进制$a和二进制$b位数都为1的设为1,其他位为0例如:7&3=>7(0111)&3(0011) 可以...
  • C语言——位运算

    千次阅读 2021-03-26 09:21:38
    位运算是C语言的重要特点,是其他计算机高级语言所没有的。所谓位运算是指以二进制位为对象的运算。在系统软件中,常要处理二进制位的问题。例如,将一个存储单元中的各二进制位左移或右移一位、两个数按位相加等。 ...
  • 位运算符号 移位运算: 二 常用技巧: 三 运算符号优先级: 四 位运算常用技巧 1 判断奇偶性 2 求a的b次方 3 找处未重复的数 4用O(1)时间检测整数n是否是2的幂次. 5计算在一个 32 位的整数的二进制表示...
  • C#位运算

    千次阅读 2019-06-28 11:51:00
    在C#中可以对整型运算对象按进行逻辑运算,按进行逻辑运算的意义是:依次取被运算对象的每个,进行逻辑运算,每个的逻辑运算结果是结果值的每个,C#支持的逻辑运算符如下表。 1、逻辑非运算 1变0...
  • C语言位运算

    千次阅读 2019-11-26 15:11:28
    位运算说穿了,就是直接对整数在内存中的二进制位进行操作。注意,位运算只针对于整数进行操作。 运算符号 运算规则 1、&与运算:对应两个二进位均为1时,结果位才为1,否则为0。(有假为假==0) 2、|或...
  • 位运算♢常用公式及练习详解

    万次阅读 多人点赞 2020-12-13 11:11:10
    JAVA位运算符详解 详细见知乎穆哥学堂 ...位运算符是对long、int、short、byte和char这5种类型的数据进行运算的,我们不能对double、float和boolean进行位运算操作 【注意】 >> 带符号右移 ,右移时
  • 位运算是算法题里比较特殊的一种类型,它们利用二进制位运算的特性进行一些奇妙的优化和计算。常用的位运算符号包括:“∧” 按位异或、“&” 按位与、“|” 按位或、“∼” 取反、“<<” 算术左移和 ...
  • java位运算

    千次阅读 2019-01-24 19:16:46
    java中的位运算,涉及到计算机二进制,位用bit表示,1 byte=8bit,根据各种基本数据类型占用的字节空间,可以计算各种数据有多少位二进制,可以算出对应的取值范围。 java中的位运算包括:与(&)运算,或(|)...
  • Java 位运算和模运算到底哪个快?修改 之前在看 ```HashMap``` 的源代码和相关博客。 看到了```HashMap```中有关```HashMap```容器大小和```indexFor()```中的方法。 1. ```HashMap```为什么长度规定需要...
  • 回顾首先来回顾一下这些运算: - &(与运算):只有当两方都为 true 时,结果才是 true,否则为 false。 - |(或运算):只要当一方为 true 时,结果就是 true,否则为 false。 - ^(异或运算):只要两方不同,...
  • 位运算全面总结,关于位运算看这篇就够了

    万次阅读 多人点赞 2021-05-28 13:04:55
    关于位运算的奇技淫巧,看完这篇你就能灵活使用位运算了。
  • C语言位运算详解

    千次阅读 2020-02-27 11:02:46
    C语言位运算包括:按位与运算、或运算、异或运算、左移运算、右移运算。 位运算,就是对一个比特(Bit)位进行操作。比特(Bit)是一个电子元器件,8个比特构成一个字节(Byte),它已经是粒度最小的可操作单元了。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 839,448
精华内容 335,779
关键字:

位运算

友情链接: Navigationwithtabs.zip