筑基五层 —— 位运算看这篇就行了

admin • • C/C++

目录

一.修炼必备

二. 位运算

二.移位运算符

三.位运算综合使用

  恭喜你，成功突破至筑基五层！！！

一.修炼必备

 1.入门必备：VS2019社区版，下载地址：Visual Studio 较旧的下载 - 2019、2017、2015 和以前的版本 (microsoft.com)

 2.趁手武器：印象笔记/有道云笔记

 3.修炼秘籍：牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网 (nowcoder.com)

 4.雷劫必备：leetcode 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 

 注：遇到瓶颈怎么办？百度百科_全球领先的中文百科全书 (baidu.com)

二. 位运算

 1.什么是位运算？

        ——位运算就是直接对整数在内存中的二进制位进行操作的运算

 2.位运算操作符

位操作符 特点

&（按位与）

有0为0，全1为1
|（按位或） 有1为1，全0为0
^（按位异或） 相同为0.不同为1
~（按位取反） 0变1，1变0

 注：

  1）二进制的运算均是以补码进行运算的

  2）异或满足交换律和结合律

交换律：num ^ 0 = num; 0 ^ num = num;

结合律：num ^ a ^ a = num; a ^ num ^ a = num;

//任何数和0异或等于本身，相同数异或为0

  3）只有对整数才能进行位运算，浮点数不能进行位运算

 3.一个小case快速了解位运算符

#include<stdio.h>

int main()
{
    int a=7;
    int b=4;

    //按位与
    int c=a&b;
    //00000000 00000000 00000000 00000111 -> a: 7
    //00000000 00000000 00000000 00000100 -> b: 4
    //00000000 00000000 00000000 00000100 -> a&b: 4
    printf("%d & %d = %dn",a,b,c);// 7 & 4 = 4

    //按位或
    c=a|b;
    //00000000 00000000 00000000 00000111 -> a: 7
    //00000000 00000000 00000000 00000100 -> b: 4
    //00000000 00000000 00000000 00000111 -> a|b: 7 
    printf("%d | %d = %dn",a,b,c);// 7 | 4 = 7

    //按位异或
    c=a^b;
    //00000000 00000000 00000000 00000111 -> a: 7
    //00000000 00000000 00000000 00000100 -> b: 4
    //00000000 00000000 00000000 00000011 -> a^b: 3
    printf("%d ^ %d = %dn",a,b,c);// 7 ^ 4 = 3
    
    //按位取反
    c = ~a;
    //00000000 00000000 00000000 00000111 -> a: 7
    //11111111 11111111 11111111 11111000 -> ~a（补码)
    //11111111 11111111 11111111 11110111 -> 反码
    //10000000 00000000 00000000 00001000 -> 原码（打印的是原码）：-8
    printf("~%d = %dn", a, c);//~7 = -8
    
    return 0;
}

 4.常用的位操作符

  1）判断奇偶性

奇数：(num & 1) == 1 等价于 num % 2 == 1

偶数：(num & 1) == 0 等价于 num % 2 == 0

注：为什么num&1要加括号？ —— ==的优先级比&的优先级高

#include <stdio.h>

int main()
{
    int num = 0;
    scanf("%d", &num);
    
    //若是想要使用num & 1 == 1，则需要使用括号括上(num & 1) == 1
    if (num & 1)
    {
        printf("%d是奇数n", num);
    }
    else
    {
        printf("%d是偶数n", num);
    }
    return 0;
}

  2）计算二进制中有几个1：num = num & (num -1)

#include <stdio.h>

int getOneCount(int num)
{
    int count = 0;
    while (num)
    {
        num = num & (num - 1);
        count++;
        //测试用例1：7
        //00000000 00000000 00000000 00000111  : 7
        //00000000 00000000 00000000 00000110  : 6
        //00000000 00000000 00000000 00000110  : 6 :结果
        //00000000 00000000 00000000 00000101  : 5
        //00000000 00000000 00000000 00000100  : 4: 结果
        //00000000 00000000 00000000 00000011  : 3
        //00000000 00000000 00000000 00000000  : 0: 结果 -->跳出循环
        
        //测试用例2：10
        //00000000 00000000 00000000 00001010  : 10
        //00000000 00000000 00000000 00001001  : 9
        //00000000 00000000 00000000 00001000  : 8: 结果
        //00000000 00000000 00000000 00000111  : 7
        //00000000 00000000 00000000 00000111  : 0: 结果 -->跳出循环
        
    }
    return count;
}

int main()
{
    int num = 0;
    scanf("%d", &num);
    
    int count = getOneCount(num);//计算1的个数
    printf("%d的二进制中有%d个1n", num, count);
    return 0;
}

  3）num & -num：得到二进制的最低位的1（不一定是最后一位）

#include <stdio.h>

int main()
{
    int num = 0;
    scanf("%d", &num);
    
    int ret = num & -num;
    printf("%d & -%d = %dn", num, num, ret);
    
    //说明：二进制的运算均是以补码进行的
    //测试案例1：7
    //10000000 00000000 00000000 00000111 -->原码  -7
    //11111111 11111111 11111111 11111000 -->反码
    //11111111 11111111 11111111 11111001 -->补码
    //00000000 00000000 00000000 00000111 -->补码  7
    //00000000 00000000 00000000 00000001 --> 1 ：结果
    
    //测试用例2： 10
    //10000000 00000000 00000000 00001010 -->原码 -10
    //11111111 11111111 11111111 11110101 -->反码
    //11111111 11111111 11111111 11110110 -->补码
    //00000000 00000000 00000000 00001010 -->补码  10
    //00000000 00000000 00000000 00000010 -->2 ： 结果
    
    return 0;
}

  4）num & ~num：0

#include <stdio.h>

int main()
{
    int num = 0;
    scanf("%d", &num);
    
    int ret = num & ~num;
    printf("%d & ~%d = %dn", num, num, ret);
    
    //测试用例1：3
    //00000000 00000000 00000000 00000011 ：3
    //11111111 11111111 11111111 11111100 ：~3
    //00000000 00000000 00000000 00000000 ：0 结果
    
    //测试用例2：4
    //00000000 00000000 00000000 00000100 ：4
    //11111111 11111111 11111111 11111011 ：~4
    //00000000 00000000 00000000 00000000 ：0 结果
    return 0;
}

  5）低位首0变1：num | (num+1)

#include <stdio.h>

int main()
{
    int num = 0;
    scanf("%d", &num);
    int ret = num | (num + 1);
    printf("%d | %d = %dn", num, num + 1, ret);
    
    //测试用例1：5
    //00000000 00000000 00000000 00000101 ：5
    //00000000 00000000 00000000 00000110 ：6
    //00000000 00000000 00000000 00000111 : 7 --> 低位首0变1
    
    //测试用例2：9
    //00000000 00000000 00000000 00001001 ：9
    //00000000 00000000 00000000 00001010 ：10
    //00000000 00000000 00000000 00001011 ：11 --> 低位首0变1
    return 0;
}

  6）求num的相反数：~num + 1

#include <stdio.h>

int main()
{
    int num = 0;
    scanf("%d", &num);
    
    int ret = ~num + 1;
    printf("%dn", ret);
    
    //测试用例1：5
    //11111111 11111111 11111111 11111010 ：~5
    //11111111 11111111 11111111 11111011 ：~5 + 1 补码
    //11111111 11111111 11111111 11111010 ：反码
    //10000000 00000000 00000000 00000101 ：原码 --> -5
    
    //测试用例2：-5
    //10000000 00000000 00000000 00000101 原码
    //11111111 11111111 11111111 11111010 反码
    //11111111 11111111 11111111 11111011 补码
    //00000000 00000000 00000000 00000100 ~（-5）
    //00000000 00000000 00000000 00000101 ~（-5）+ 1 --> 5（结果）
    
    return 0;
}

  7）判断数是不是2的幂：num & (num-1) == 0

#include <stdio.h>

int main()
{
    int num = 0;
    scanf("%d", &num);
    
    if ((num & (num - 1)) == 0)
    {
        printf("%d是2的幂n", num);
    }
    else
    {
        printf("%d不是2的幂n", num);
    }
    
    //测试案例1：2
    //00000000 00000000 00000000 00000010 :2
    //00000000 00000000 00000000 00000001 :1
    //00000000 00000000 00000000 00000000 :0 --> 结果
    
    //测试用例2：8
    //00000000 00000000 00000000 00001000 : 8
    //00000000 00000000 00000000 00000111 : 7
    //00000000 00000000 00000000 00000000 : 0 -->结果
    return 0;
}

  8）异或应用：变量交换

#include <stdio.h>

int main()
{
    int a = 0;
    int b = 0;
    scanf("%d %d", &a, &b);
    
    //交换变量
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    printf("%d %dn", a, b);
    return 0;
}

二.移位运算符

 1.什么是移位运算符？

        ——在C语言中，使用<<和>>对数的二进制位进行向左移动和向右移动，而<<和>>称为移位运算符

 2.移位操作符

移位操作符 特点
<< 左边丢弃，右边补0
>>

算术右移：右边丢弃，左边补符号位

逻辑右移：右边丢弃，左边补0

二进制位进行移位的时候，不要移动负数位，因为这个标准是未定义的

 3.一个小case快速了解移位操作符 

#include <stdio.h>

int main()
{
    int num = 7;
    int ret = num << 2;
    //00000000 00000000 00000000 00000111  num
    //000000 00000000 00000000 0000011100  num << 2 :28
    printf("%dn", ret);//28
    
    ret = num >> 2;
    //00000000 00000000 00000000 00000111  num
    //注：我们在这个地方进行的是算术右移，现在大多数编译器都是进行算术右移的
    //0000000000 00000000 00000000 000001  num >> 2 ：1
    printf("%dn", ret);//1
    return 0;
}

 4.常用的移位操作

  1）num >> 1 等价于 num / 2

#include <stdio.h>

int main()
{
    int num = 0;
    scanf("%d", &num);
    
    int ret = num >> 1;
    int res = num / 2;
 
    //测试案例1：10
    //00000000 00000000 00000000 00001010  num: 10
    //00000000 00000000 00000000 00000101  num >> 1：5
    //num / 2 = 5
    
    //测试案例2：15
    //00000000 00000000 00000000 00001111  num：15
    //00000000 00000000 00000000 00000111  num >> 1：7
    //num / 2= 7
    
    if (ret == res)
    {
        printf("num>>1和num/2相等n");
    }
    else
    {
        printf("num>>1和num/2不相等n");
    }
    return 0;
}

  2）去掉num的低x位（从最低位一直到x位）：num >> x

#include <stdio.h>

int main()
{
    int num = 0;
    scanf("%d", &num);
    
    int ret = num >> 3;//去掉低三位
    //00000000 00000000 00000000 00001111  num：15
    //00000000 00000000 00000000 00000001  num：1
    printf("%dn", ret);//1
    
    ret = num >> 2;//去掉低两位
    //00000000 00000000 00000000 00001111  num：15
    //00000000 00000000 00000000 00000011  num：3
    printf("%dn", ret);//3
    return 0;
}

三.位运算综合使用

  注：规定，我的最低位是从1开始，最高位是32

  1.获取num二进制位的第n位值：(num >> n) &1

#include <stdio.h>

int main()
{
    int num = 0;
    scanf("%d", &num);
    
    int ret = (num >> 3) & 1;
    printf("%dn", ret);
    //测试案例：15
    //00000000 00000000 00000000 00001111  num：15
    //00000000 00000000 00000000 00000001  num >> 3
    //00000000 00000000 00000000 00000001  (num >> 3) & 1
    //00000000 00000000 00000000 00000001  1
    return 0;
}

  2.将num的第（n+1）位置为1：num | (1 << n)

#include <stdio.h>

int main()
{
    int num = 0;
    scanf("%d", &num);
    
    //将num的第4位置为1
    int ret = num | (1 << 3);
    printf("%dn", ret);
    
    //测试案例：5
    //00000000 00000000 00000000 00000101
    //00000000 00000000 00000000 00001000 1 << 3
    //00000000 00000000 00000000 00001101 13
    return 0;
}

  3.将num的第（n+1）位置为0：num & (~(1 << n))

#include <stdio.h>

int main()
{
    int num = 0;
    scanf("%d", &num);
    
    //将num的第3位置为0
    int ret = num & (~(1 << 2));
    printf("%dn", ret);
    
    //测试案例：5
    //00000000 00000000 00000000 00000100 1 << 2
    //11111111 11111111 11111111 11111011 ~(1 << 2) ：补码
    //00000000 00000000 00000000 00000101 : 5
    //00000000 00000000 00000000 00000001 : num & (~(1 << 2))
    return 0;
}

  4.获取num的第（n+1）位的幂值：num & (1 << n)

#include <stdio.h>

int main()
{
    int num = 0;
    scanf("%d", &num);
    
    //获取num第3位的幂值
    int ret = num & (1 << 2);
    printf("%dn", ret);
    
    //测试案例 ：5
    //00000000 00000000 00000000 00000101 ： 5
    //00000000 00000000 00000000 00000100 ： 1 << 2
    //00000000 00000000 00000000 00000100 ： num & (1 << 2): 4
    
    //测试案例： 8
    //00000000 00000000 00000000 00001000 ： 8
    //00000000 00000000 00000000 00000100 ： 1 << 2
    //00000000 00000000 00000000 00000000 ： num & (1 << 2): 0
    return 0;
}

  5.将num的最高位到（n+1）位置为0：num & ((1 << n) - 1)

#include <stdio.h>

int main()
{
    int num = 0;
    scanf("%d", &num);
    
    //将num的最高位到第4位置为0
    int ret = num & ((1 << 3) - 1);
    printf("%dn", ret);
    
    //测试案例：121
    //00000000 00000000 00000000 01111001 :121
    //00000000 00000000 00000000 00000111 : 1 << 3 - 1
    //00000000 00000000 00000000 00000001 : 7
    return 0;
}

  6.将num的第1位到第（n+1）位置为0：num & (~((1 << (n + 1)) - 1))

#include <stdio.h>

int main()
{
    int num = 0;
    scanf("%d", &num);
    
    //将num的第0位到第3位置为0
    int ret = num & (~((1 << (2 + 1)) - 1));
    printf("%dn", ret);
    
    //测试案例： 121
    //00000000 00000000 00000000 00000111 ：(1 << (2 +1) - 1)
    //11111111 11111111 11111111 11111000 ：~(1 << (2 +1) - 1)
    //00000000 00000000 00000000 01111001 :121
    //00000000 00000000 00000000 01111000
    return 0;
}

  7.代替减法进行两数相减：x + ~y + 1

#include <stdio.h>

int main()
{
    int x = 0;
    int y = 0;
    scanf("%d %d", &x, &y);
    
    int ret = x + ~y + 1;
    printf("%d - %d = %dn", x, y, ret);
    
    //测试案例：x = 5, y = 3
    //00000000 00000000 00000000 00000011 y
    //11111111 11111111 11111111 11111100 ~y
    //00000000 00000000 00000000 00000101 x
    //00000000 00000000 00000000 00000001 x + ~y = 1
    //00000000 00000000 00000000 00000010 x + ~y + 1 = 2
    
    //测试案例： x = 3, y = 5
    //00000000 00000000 00000000 00000101 y
    //11111111 11111111 11111111 11111010 ~y
    //00000000 00000000 00000000 00000011 x
    //11111111 11111111 11111111 11111101 x + ~y
    //11111111 11111111 11111111 11111110 x + ~y + 1 补码
    //11111111 11111111 11111111 11111101 反码
    //10000000 00000000 00000000 00000010 原码 -2
    return 0;
}

  8.代替加法进行两数相加：x - ~y - 1

#include <stdio.h>

int main()
{
    int x = 0;
    int y = 0;
    scanf("%d %d", &x, &y);
    
    int sum = ~y;
    int ret = x - ~y - 1;
    printf("%d + %d = %dn", x, y, ret);
    
    //测试案例：x = 5, y = 3
    //00000000 00000000 00000000 00000011 y
    //00000000 00000000 00000000 00000101 x
    //11111111 11111111 11111111 11111100 ~y
    //00000000 00000000 00000000 00001001 x - ~y
    //00000000 00000000 00000000 00001000 x - ~y - 1: 8
    return 0;
}

  注：位运算的基本常用的操作就在这点了，但是远不止这点，需要我们更加努力的学习和探索位运算的奥妙。

  注：若是觉得CSDN看起来很难受的话，请去有道云看我写的原文（排版更好）

  链接在此：有道云笔记

  恭喜你，成功突破至筑基五层！！！

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>