笙亿网络策划

数据结构与算法中 Bit Mask 怎么用？

约 11 分钟读完 2 阅
文章导读
上一个 测验 下一个 位掩码是一种强大的技术，在计算机科学和编程中被广泛用于操作位。你可以将其视为一种在二进制数中开启或关闭特定位的方法。
📋 目录
  1. A 什么是位掩码？
  2. B 位掩码上的位运算
  3. C 位掩码的操作
  4. D 位掩码上的置位操作
  5. E 位掩码的清零操作
  6. F 位掩码上的切换操作
  7. G 位掩码的应用
  8. H 结论
A A

数据结构中的位掩码

上一个
测验
下一个

位掩码是一种强大的技术，在计算机科学和编程中被广泛用于操作位。你可以将其视为一种在二进制数中开启或关闭特定位的方法。

位掩码用于执行位运算，例如 AND、OR、XOR 和 NOT，作用于二进制数。它们在计算机科学中被广泛应用于各种场景，我们将在本章详细讨论位掩码。

什么是位掩码？

Bitmask，也称为掩码，是一个由 N-bits 组成的序列，用于编码集合的子集。掩码的每个元素可以被设置或未设置（即 0 或 1）。这表示所选元素在位掩码中的可用性。

例如，如果掩码的第 i 位被设置，则元素 i 存在于子集中。对于包含 N 个元素的集合，可能有 2N 个掩码，每个掩码对应一个子集。

因此，为了解决问题，我们将从一个掩码（即一个子集）开始，为其分配一个值，然后使用前一个掩码的值来计算后续掩码的值。通过这种方式，我们最终能够计算出主集的值。

位掩码上的位运算

现在，让我们讨论可以对位掩码执行的位运算：

  • AND 操作：AND 操作用于在两个位均为 1 时将位设置为 1，否则设置为 0。
  • OR 操作：OR 操作用于在任一位置为 1 时将位设置为 1，否则设置为 0。
  • XOR 操作：XOR 操作用于在位不同时将位设置为 1，否则设置为 0。
  • NOT 操作：NOT 操作用于反转位，即 1 转换为 0，0 转换为 1。

位掩码的操作

位掩码上主要可以执行三种操作：

  • Set：在二进制数中将一位设置为 1。
  • Clear：在二进制数中将一位清零为 0。
  • Toggle：在二进制数中将一位从 0 切换到 1 或从 1 切换到 0。

位掩码上的置位操作

在二进制数中将一位设置为 1 是通过使用 OR 操作完成的。OR 操作用于在两位中任一位为 1 时将该位设置为 1，否则设置为 0。

置位操作的算法

以下是将二进制数中第 ith 位设置为 1 的算法：

1.读取二进制数和要设置的位的位置。
2.使用左移操作创建一个在第 i 位为 1 的 mask。
3.对二进制数和 mask 执行 OR 操作以设置第 i 位。
4.输出修改后的二进制数。

置位操作的代码

以下是在不同编程语言中对位掩码执行置位操作的代码：

C C++ Java Python 
//C 程序执行位掩码上的置位操作
#include <stdio.h>

int setBit(int num, int pos){
   return num | (1 << pos);
}

int main(){
   int num = 5;
   int pos = 1;
   num = setBit(num, pos);
   printf("Number after Set Operation: %d\n", num);
   return 0;
}

输出

Number after Set Operation: 7

//C++ 程序执行位掩码上的置位操作
#include <iostream>

int setBit(int num, int pos){
   return num | (1 << pos);
}
int main(){
   int num = 5;
   int pos = 1;
   num = setBit(num, pos);
   std::cout << "Number after Set Operation: " << num << std::endl;
   return 0;
}

输出

Number after Set Operation: 7

//Java 程序执行位掩码上的置位操作
public class Main {
   public static int setBit(int num, int pos){
      return num | (1 << pos);
   }
   
   public static void main(String[] args) {
      int num = 5;
      int pos = 1;
      num = setBit(num, pos);
      System.out.println("Number after Set Operation: " + num);
   }
}

输出

Number after Set Operation: 7

#Python 程序执行位掩码上的置位操作
def setBit(num, pos):
   return num | (1 << pos)

num = 5
pos = 1
num = setBit(num, pos)
print("Number after Set Operation:", num)

输出

Number after Set Operation: 7

位掩码的清零操作

清零 二进制数中的一位为 0 是通过使用 AND 操作 完成的。AND 操作 用于在两位均为 1 时将位设置为 1，否则设置为 0。

为什么需要将一位清零为 0？

有时，我们需要在二进制数中将一位清零为 0，以便对其执行进一步的操作。例如，如果我们想将一位设置为 1，首先需要将该位清零为 0，然后再设置为 1。

清零操作的算法

以下是将二进制数中第 i 位清零为 0 的算法：

1.读取二进制数和要清零的位的位置。
2.使用左移创建第 i 位为 1 的掩码，然后对其取反。
3.对二进制数和掩码执行 AND 操作，以清零第 i 位。
4.输出修改后的二进制数。

清零操作的代码

以下是在不同编程语言中对位掩码执行清零操作的代码：

C C++ Java Python 
/*C 程序执行位掩码的清零操作*/
#include <stdio.h>

int clearBit(int num, int pos){
   return num & ~(1 << pos);
}

int main(){
   int num = 7;
   int pos = 1;
   num = clearBit(num, pos);
   printf("清零操作后的数字: %d\n", num);
   return 0;
}

输出

清零操作后的数字: 5

/*C++ 程序执行位掩码的清零操作*/
#include <iostream>

int clearBit(int num, int pos){
   return num & ~(1 << pos);
}

int main(){
   int num = 7;
   int pos = 1;
   num = clearBit(num, pos);
   std::cout << "清零操作后的数字: " << num << std::endl;
   return 0;
}

输出

清零操作后的数字: 5

/*Java 程序执行位掩码的清零操作*/
public class Main {
   public static int clearBit(int num, int pos){
      return num & ~(1 << pos);
   }
   
   public static void main(String[] args) {
      int num = 7;
      int pos = 1;
      num = clearBit(num, pos);
      System.out.println("清零操作后的数字: " + num);
   }
}

输出

清零操作后的数字: 5

#Python 程序执行位掩码的清零操作
def clearBit(num, pos):
   return num & ~(1 << pos)

num = 7
pos = 1
num = clearBit(num, pos)
print("清零操作后的数字:", num)

输出

清零操作后的数字: 5

位掩码上的切换操作

在二进制数中将一个位从 0 切换到 1 或从 1 切换到 0，通过使用XOR 操作来实现。XOR 操作用于在位不同时将位设置为 1，否则设置为 0。

切换操作的算法

以下是在二进制数中切换第 i 位的算法：

1.读取二进制数和要切换的位的位置。
2.使用 XOR 操作在二进制数中切换第 i 位。
3.输出修改后的二进制数。

切换操作的代码

以下是在不同编程语言中对位掩码执行切换操作的代码：

C C++ Java Python 
/*C 程序执行位掩码上的切换操作*/
#include <stdio.h>

int toggleBit(int num, int pos){
   return num ^ (1 << pos);
}
int main(){
   int num = 5;
   int pos = 1;
   num = toggleBit(num, pos);
   printf("Number after Toggle Operation: %d\n", num);
   return 0;
}

输出

Number after Toggle Operation: 7

/*C++ 程序执行位掩码上的切换操作*/
#include <iostream>

int toggleBit(int num, int pos){
   return num ^ (1 << pos);
}
int main(){
   int num = 5;
   int pos = 1;
   num = toggleBit(num, pos);
   std::cout << "Number after Toggle Operation: " << num << std::endl;
   return 0;
}

输出

Number after Toggle Operation: 7

/*Java 程序执行位掩码上的切换操作*/
public class Main {
   public static int toggleBit(int num, int pos){
      return num ^ (1 << pos);
   }
   
   public static void main(String[] args) {
      int num = 5;
      int pos = 1;
      num = toggleBit(num, pos);
      System.out.println("Number after Toggle Operation: " + num);
   }
}

输出

Number after Toggle Operation: 7

#Python 程序执行位掩码上的切换操作
def toggleBit(num, pos):
   return num ^ (1 << pos)

num = 5
pos = 1
num = toggleBit(num, pos)
print("Number after Toggle Operation:", num)

输出

Number after Toggle Operation: 7

位掩码的应用

位掩码在计算机科学中用于各种应用，例如：

  • 在二进制数中设置和清除位。
  • 对二进制数执行位运算。
  • 以紧凑形式编码和解码数据。
  • 实现数据结构，如位数组和位图。
  • 优化算法和数据结构以提升性能。

结论

位掩码用于操作二进制数中的位。在计算机科学和编程中，它们常用于对二进制数执行位运算。

位掩码可用于在二进制数中设置、清除和切换位，以及执行如AND、OR、XOR和NOT等位运算。它们是优化算法和数据结构性能的强大技术。