位运算基础知识详解

位运算基础知识详解

引用

CSDN

1.

https://blog.csdn.net/2301_80007603/article/details/138288634

位运算是计算机科学中的基础概念，它直接操作二进制数，能够实现许多高效的算法和数据结构。本文将详细介绍位运算的基本操作、规律及其在实际编程中的应用，帮助读者深入理解这一重要技术。

一、定义

众所周知，计算机中数都是以二进制的形式存储的，位运算是指一种对二进制数进行操作的运算。在运算中除了左右移动运算每一位独立，各自得到结果。

注意：

1. 位运算在竞赛中常常考察异或的性质、状态压缩、与位运算相关的数据结构（如树状数组、01Tire、01线性表）以及构造题。
2. 位运算需要注意有符号整数的运算，因为它们含有符号位，会造成影响。

二、主要操作

1. 按位与（AND，&）
   用于两个操作数的对应位数进行逻辑与操作，二者都为1时结果为1，否则为0（类似电路中的与门）。
   
   进行与运算后结果不会变大。

2. 按位或（OR，|）
   二者有1就为1（类似或门）。
   结果不会变小。

3. 按位异或（XOR，^）
   两位不同时结果为1。
   结果大小不一定。
   按位异或满足以下运算规律：

• 交换律：a^b=b^a
• 结合律：a^(b^c)=(a^b)^c
• 自反律：a^a=0
• 零元素：a^0=a
• 逆运算：a^b=c => a=c^b（由自反律可得）

4. 按位取反（~）
   1变0，0变1，所以常用于无符号整型，否则符号位会造成影响。

5. 按位左移（<<）
   将一个数的二进制向左移动指定的位数，移动后低位补0（若是有符号整型，注意不要移动到符号位上）。
   左移操作相当于对原数乘以2的移动数的次方。

6. 按位右移（>>）
   向右移动指定位数，高位补0，相当于原数除以2的移动数的次方，取整数。
   好玩的是面对有符号整型时，右移会导致高位补1。

#include"bits/stdc++.h"
using namespace std;
int main()
{
    cout<<bitset<32>(1<<31)<<'\n';//32位是一个整型的位数 
    cout<<bitset<32>((1<<31)>>31)<<'\n';
    return 0;
}   

三、应用

1. 判断奇数偶数（x&1）
   我们通常会用%来判断奇数偶数，但也可以用与1判断。
   二进制中，若末尾是1则为奇数，所以与时只用看最后一位。
   1&1->1 0&1->0
   所以1为奇数 0为偶数

2. 获取二进制中某一位
   x>>i&1 ，其中i表示某一位

3. 修改二进制位中的某一位为1
   x|(1<<i) 若是修改为0，则使用与运算

4. 判断一个数是否为二的幂次方
   x&(x-1) 如果是2的幂次方，则二进制中只有一个1，x-1就有很多个连续的1，并且和x的1没交集，两者运算一定为1。

5. 获取二进制中最低位的1
   lowbit（x）=x&-x （常用于树状数组）