您当前的位置: 首页 > 技术文章 > 编程语言

【C语言】超详细的移位、位操作符详解(含力扣实战)

作者: 时间:2022-05-23阅读数:人阅读

【C语言】超详细的移位、位操作符详解(含力扣实战)(图1)

【C语言】超详细的移位、位操作符详解(含力扣实战)(图2)


目录

​1、整数的二进制表示

​2、移位操作符

​2.1左移操作符(低位补0)

​举例

​原理分析

 ​2.2右移操作符

​算术右移(高位补原符号位)

​逻辑右移(高位补0)

​ 3、位操作符

​3.1按位与&

​原理分析

​3.2按位或|

​原理分析

​3.3按位异或^

​原理分析

​4、实战应用

​4.1交换两个变量(不创建临时变量)

​原理分析:

​4.2消失的数字

​(1)思路一:冒泡排序,先排序后遍历(时间复杂度O(n²),不符合题意)

​(2)思路二:(0-n的等差数列和)-(数组nums的和)

​(3)思路三——异或


【C语言】超详细的移位、位操作符详解(含力扣实战)(图3)1、整数的二进制表示

【C语言】超详细的移位、位操作符详解(含力扣实战)(图4)正数的原码、反码、补码相同,整数在内存中存储的是补码(所以需要用补码对移位、位操作符进行分析)。

【C语言】超详细的移位、位操作符详解(含力扣实战)(图5)负数的原反补不同,以-1为例:

原码:10000000000000000000000000000001(原码就是原码)

反码:11111111111111111111111111111110(符号位不变,其他位按位取反)

补码:11111111111111111111111111111111(补码=反码+1)

【C语言】超详细的移位、位操作符详解(含力扣实战)(图6)负数的补码也可以用该负数的绝对值-1,按位取反,即可得到该负数的补码。

【C语言】超详细的移位、位操作符详解(含力扣实战)(图3)2、移位操作符

<< 左移操作符
>> 右移操作符
移动的是二进制位,只能对整数进行整数位的移动

【C语言】超详细的移位、位操作符详解(含力扣实战)(图8)2.1左移操作符(低位补0)

【C语言】超详细的移位、位操作符详解(含力扣实战)(图9)举例

【C语言】超详细的移位、位操作符详解(含力扣实战)(图10)

 3的二进制位左移1位,输出结果为3。

【C语言】超详细的移位、位操作符详解(含力扣实战)(图9)原理分析

左移操作符,移动后,高位删除,低位补0;

每左移一位,原始数据乘2。

【C语言】超详细的移位、位操作符详解(含力扣实战)(图12)

 【C语言】超详细的移位、位操作符详解(含力扣实战)(图8)2.2右移操作符

【C语言】超详细的移位、位操作符详解(含力扣实战)(图9)算术右移(高位补原符号位)

【C语言】超详细的移位、位操作符详解(含力扣实战)(图15)

目前主流编译器都是采用算术右移,以VS为例,-1的二进制位向右移动一位,结果为-1。

【C语言】超详细的移位、位操作符详解(含力扣实战)(图16)

【C语言】超详细的移位、位操作符详解(含力扣实战)(图9)逻辑右移(高位补0)

由于主流编译器不采用逻辑右移,其原理同上不作介绍。

【C语言】超详细的移位、位操作符详解(含力扣实战)(图3) 3、位操作符

【C语言】超详细的移位、位操作符详解(含力扣实战)(图19)3.1按位与&

int main()
{
    int a = -2;
    int b = 3;
    int c = a&b;
    printf("%d\n", c);//打印2
    return 0;
}

【C语言】超详细的移位、位操作符详解(含力扣实战)(图20)原理分析

【C语言】超详细的移位、位操作符详解(含力扣实战)(图21)

按位与指按二进制位,若两个数字的同一个二进制位均为1,则该位为1;反之,为0。

【C语言】超详细的移位、位操作符详解(含力扣实战)(图22)3.2按位或|

int main()
{
    int a = -2;
    int b = 3;
    int c = a|b;
    printf("%d\n", c);//打印-1
    return 0;
}

【C语言】超详细的移位、位操作符详解(含力扣实战)(图23)原理分析

【C语言】超详细的移位、位操作符详解(含力扣实战)(图24)

按位或指按二进制位,若两个数字的同一个二进制位有1,则该位为1;反之,为0。

【C语言】超详细的移位、位操作符详解(含力扣实战)(图25)3.3按位异或^

int main()
{
    int a = -2;
    int b = 3;
    int c = a^b;
    printf("%d\n", c);//输出-3
    return 0;
}

【C语言】超详细的移位、位操作符详解(含力扣实战)(图26)原理分析

【C语言】超详细的移位、位操作符详解(含力扣实战)(图27)

按位异或指按二进制位,两个二进制位相同为0相异为1。

【C语言】超详细的移位、位操作符详解(含力扣实战)(图28)4、实战应用

【C语言】超详细的移位、位操作符详解(含力扣实战)(图29)4.1交换两个变量(不创建临时变量)

不允许创建临时变量,交换两个整数的内容。

这是某互联网大厂的一道笔试真题。咱们很容易想到通过创建临时变量的方式来解决这道题,但是题目限制创建临时变量。那么可以通过异或的方式进行解决!

#include <stdio.h>
int main()
{
    int a = -2;
    int b = 3;
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    printf("%d %d\n", a, b);
    return 0;
}

【C语言】超详细的移位、位操作符详解(含力扣实战)(图30)原理分析:

1、自身和自身异或得0;

2、任何数和0异或得本身;

第六行a(新)= a ^ b,指把a^b的值赋值a

第七行b(新)=a(新) ^ b=a ^ b^ b=a;(代入第六行的数据)

第八行a = a (新)^ b(新)=a ^ b^a=b; (代入上两行的数据)

实现a和b的交换!

【C语言】超详细的移位、位操作符详解(含力扣实战)(图31)4.2消失的数字

【C语言】超详细的移位、位操作符详解(含力扣实战)(图32)

【C语言】超详细的移位、位操作符详解(含力扣实战)(图33)(1)思路一:冒泡排序,先排序后遍历(时间复杂度O(n²),不符合题意)

int missingNumber(int* nums, int numsSize){
    for(int i=0;i<numsSize-1;i++)
    {
        for(int j=0;j<numsSize-1-i;j++)
        {
            if(nums[j]>nums[j+1])
            {
                int tmp=nums[j];
                nums[j]=nums[j+1];
                nums[j+1]=tmp;
            }
        } 
    }
    if(nums[0]!=0)
        return 0;
    if(numsSize!=1)
    {
        for(int i=0;i<numsSize-1;i++)
        {
            if(nums[i+1]-nums[i]==2)
            {
                return nums[i]+1;              
            }      
        }
        return nums[numsSize-1]+1;
    }
    if(nums[0]==0)
        return 1;
    return nums[0]-1;
}

虽然力扣题目要求了时间复杂度,但是力扣后台是不会测试复杂度的。只要代码能通过就行。

主要思想:对数组先进行冒泡排序,排序后让数组后一个元素减去前一个元素,若结果等于2,则nums[i]+1则为结果,注意此处需要举出特例。

【C语言】超详细的移位、位操作符详解(含力扣实战)(图34)(2)思路二:(0-n的等差数列和)-(数组nums的和)

int missingNumber(int* nums, int numsSize){
    int sum1=(0+numsSize+1)*numsSize/2;//sum1为0-n的等差数列求和,首项为0,末项为numsSize+1
    int sum2=0;//sum2为缺失数组的和
    for(int i=0;i<numsSize;i++)
    {
        sum2+=nums[i];
    }
    return sum1-sum2;//相减即为结果,时间复杂度O(n)
}

【C语言】超详细的移位、位操作符详解(含力扣实战)(图35)(3)思路三——异或

异或原理:二进制位相同为0,相异为1,两个相同的数字异或,结果为0;故可通过异或的方式找出缺失的数字。原理图与代码如下:

int missingNumber(int* nums, int numsSize){
    int ret=0;//缺失的数字
    for(int i=0;i<numsSize;i++)//数组nums的元素逐个异或
    {
        ret^=nums[i];
    }
    for(int i=0;i<numsSize+1;i++)//ret再次与完整的数组异或
    {
        ret^=i;
    }
    return ret;//时间复杂度O(n)
}

关注!点赞!评论!收藏!关注!点赞!评论!收藏!关注!点赞!评论!收藏!关注!点赞!评论!收藏!关注!点赞!评论!收藏!

【C语言】超详细的移位、位操作符详解(含力扣实战)(图36)

本站所有文章、数据、图片均来自互联网,一切版权均归源网站或源作者所有。

如果侵犯了你的权益请来信告知我们删除。邮箱:licqi@yunshuaiweb.com

加载中~
如果您对我们的成果表示认同并且觉得对你有所帮助可以给我们捐赠。您的帮助是对我们最大的支持和动力!
捐赠我们
扫码支持 扫码支持
扫码捐赠,你说多少就多少
2
5
10
20
50
自定义
您当前余额:元
支付宝
微信
余额

打开支付宝扫一扫,即可进行扫码捐赠哦

打开微信扫一扫,即可进行扫码捐赠哦

打开QQ钱包扫一扫,即可进行扫码捐赠哦

天猫38节现货-全屋智能