集合论与位运算之间的转换

2024-08-24 19:20
文章标签 转换 运算 之间 集合论

本文主要是介绍集合论与位运算之间的转换,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

集合可以用二进制表示,二进制从低到高第 i 位为 1 表示 i 在集合中,为 0 表示 i 不在集合中。例如集合 {0,2,3} 可以用二进制数 1101(2)​ 表示;反过来,二进制数 1101(2)​ 就对应着集合 {0,2,3}。

例如集合 {0,2,3} 可以压缩成 20+22+23=13,也就是二进制数 1101(2)​。

一、集合与集合

其中 & 表示按位与,| 表示按位或, 表示按位异或,~ 表示按位取反。

两个集合的「对称差」是只属于其中一个集合,而不属于另一个集合的元素组成的集合,也就是不在交集中的元素组成的集合。

注 1:按位取反的例子中,仅列出最低 4个比特位取反后的结果,即 0110 取反后是 1001。

注 2:包含于的两种位运算写法是等价的,在编程时只需判断其中任意一种。

注 3:编程时,请注意运算符的优先级。例如 == 在某些语言中优先级比位运算更高。

二、集合与元素

在处理集合与元素的关系时,通常会用到移位运算。

其中 << 表示左移,>> 表示右移。

注:左移 i 位相当于乘以 2i,右移 i 位相当于除以 2i(注意,这里的除法指的是整数除法,即结果向下取整)。

      s = 101100s-1 = 101011 // 最低位的 1 变成 0,同时 1 右边的 0 都取反,变成 1
s&(s-1) = 101000

特别地,如果 s 是 2 的幂,那么 s&(s−1)=0。

此外,编程语言提供了一些和二进制有关的库函数,例如:

  • 计算二进制中 1 的个数,也就是集合大小;
  • 计算二进制长度(位数),减一后得到集合中最大元素的索引(注意,这里通常指的是从0开始计数的索引,如果要得到实际的元素值,则需要根据位数计算,即 2位数−1);
  • 计算二进制尾零个数,这个操作通常用于获取最低位的 1 之前的 0 的个数,但直接将其解释为集合最小元素可能不太准确,因为集合中的元素通常是从 0 或 1 开始的连续整数。不过,在某些特定场景下,这个信息可能有助于推断集合的某些性质。

调用这些函数的时间复杂度通常是 O(1),意味着它们可以在常数时间内完成计算,不随输入规模的增长而增长。

特别地,只包含最小元素的子集,即二进制最低 11及其后面的 0,也叫 lowbit,可以用 s & -s 算出。举例说明:

     s = 101100~s = 010011
(~s)+1 = 010100 // 根据补码的定义,这就是 -s  =>  s 的最低 1 左侧取反,右侧不变
s & -s = 000100 // lowbit

三、遍历集合

设元素范围从 0 到 n−1,枚举范围中的元素 i,判断 i 是否在集合 s 中。

for (int i = 0; i < n; i++) {if (((s >> i) & 1) == 1) { // i 在 s 中// 处理 i 的逻辑}
}

也可以直接遍历集合 s 中的元素:不断地计算集合最小元素、去掉最小元素,直到集合为空。

for (int t = s; t > 0; t &= t - 1) {int i = Integer.numberOfTrailingZeros(t);// 处理 i 的逻辑
}

四、枚举集合

枚举所有集合

设元素范围从 0 到 n−1,从空集 ∅ 枚举到全集 U:

for (int s = 0; s < (1 << n); s++) {// 处理 s 的逻辑
}

枚举非空子集

设集合为 s,从大到小枚举 s 的所有非空子集 sub:

for (int sub = s; sub > 0; sub = (sub - 1) & s) {// 处理 sub 的逻辑
}

枚举子集(包含空集)

如果要从大到小枚举 ss的所有子集 sub(从 ss枚举到空集 ∅),可以这样写:

int sub = s;
do {// 处理 sub 的逻辑sub = (sub - 1) & s;
} while (sub != s);

原理是:当 sub=0(空集)时,再减一就得到 -1,对应的二进制为 111⋯1。然后再与 s 进行按位与操作(&),就得到了 s。所以当循环到 sub=s 时,说明最后一次循环的 sub=0(空集),s 的所有子集都枚举到了,此时可以退出循环。

Gosper's Hack(枚举全集 U 的所有大小恰好为 k 的子集)

public class GospersHack {  // 打印一个整数表示的子集,其中集合是 0 到 n-1 的整数  private static void printSubset(int subset, int n) {  for (int i = 0; i < n; i++) {  if ((subset & (1 << i)) != 0) {  System.out.print(i + " ");  }  }  System.out.println();  }  // 使用 Gosper's Hack 枚举所有大小为 k 的子集  public static void enumerateSubsets(int n, int k) {  // 初始子集是所有最低位的 k 个 1  int subset = (1 << k) - 1;  // 循环直到达到上限(所有 n 个位中的 k 个 1 的最大子集)  while (true) {  // 打印当前子集  printSubset(subset, n);  // 查找需要翻转的最低位的 1(即需要向右移动的最低位的 1)  int x = subset & -subset; // 找到最低位的 1  int y = subset + x; // 将该位及其左边的所有位设为 1  // 清除 y 中从最低位的 1 到最右边的 1 之间的所有位  y = (y / x) >> 1;  // 翻转 y 中最右边的 1 及其右边的所有位  subset = subset ^ y;  // 检查是否已经生成了所有子集  if ((subset & (1 << (k - 1))) == 0) {  break;  }  }  }  public static void main(String[] args) {  int n = 4; // 集合大小  int k = 2; // 子集大小  enumerateSubsets(n, k);  }  
}

这篇关于集合论与位运算之间的转换的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1103377

相关文章

Linux使用dd命令来复制和转换数据的操作方法

《Linux使用dd命令来复制和转换数据的操作方法》Linux中的dd命令是一个功能强大的数据复制和转换实用程序,它以较低级别运行,通常用于创建可启动的USB驱动器、克隆磁盘和生成随机数据等任务,本文... 目录简介功能和能力语法常用选项示例用法基础用法创建可启动www.chinasem.cn的 USB 驱动

Python 标准库time时间的访问和转换问题小结

《Python标准库time时间的访问和转换问题小结》time模块为Python提供了处理时间和日期的多种功能,适用于多种与时间相关的场景,包括获取当前时间、格式化时间、暂停程序执行、计算程序运行时... 目录模块介绍使用场景主要类主要函数 - time()- sleep()- localtime()- g

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2

Java将时间戳转换为Date对象的方法小结

《Java将时间戳转换为Date对象的方法小结》在Java编程中,处理日期和时间是一个常见需求,特别是在处理网络通信或者数据库操作时,本文主要为大家整理了Java中将时间戳转换为Date对象的方法... 目录1. 理解时间戳2. Date 类的构造函数3. 转换示例4. 处理可能的异常5. 考虑时区问题6.

基于C#实现将图片转换为PDF文档

《基于C#实现将图片转换为PDF文档》将图片(JPG、PNG)转换为PDF文件可以帮助我们更好地保存和分享图片,所以本文将介绍如何使用C#将JPG/PNG图片转换为PDF文档,需要的可以参考下... 目录介绍C# 将单张图片转换为PDF文档C# 将多张图片转换到一个PDF文档介绍将图片(JPG、PNG)转

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

uva 575 Skew Binary(位运算)

求第一个以(2^(k+1)-1)为进制的数。 数据不大,可以直接搞。 代码: #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

PDF 软件如何帮助您编辑、转换和保护文件。

如何找到最好的 PDF 编辑器。 无论您是在为您的企业寻找更高效的 PDF 解决方案,还是尝试组织和编辑主文档,PDF 编辑器都可以在一个地方提供您需要的所有工具。市面上有很多 PDF 编辑器 — 在决定哪个最适合您时,请考虑这些因素。 1. 确定您的 PDF 文档软件需求。 不同的 PDF 文档软件程序可以具有不同的功能,因此在决定哪个是最适合您的 PDF 软件之前,请花点时间评估您的