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

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

相关文章

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次,点赞13次,收藏8次。本文详细介绍了Java分层架构中的几个关键包:DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1

利用Python脚本实现批量将图片转换为WebP格式

《利用Python脚本实现批量将图片转换为WebP格式》Python语言的简洁语法和库支持使其成为图像处理的理想选择,本文将介绍如何利用Python实现批量将图片转换为WebP格式的脚本,WebP作为... 目录简介1. python在图像处理中的应用2. WebP格式的原理和优势2.1 WebP格式与传统

java Long 与long之间的转换流程

《javaLong与long之间的转换流程》Long类提供了一些方法,用于在long和其他数据类型(如String)之间进行转换,本文将详细介绍如何在Java中实现Long和long之间的转换,感... 目录概述流程步骤1:将long转换为Long对象步骤2:将Longhttp://www.cppcns.c

在Java中将XLS转换为XLSX的实现方案

《在Java中将XLS转换为XLSX的实现方案》在本文中,我们将探讨传统ExcelXLS格式与现代XLSX格式的结构差异,并为Java开发者提供转换方案,通过了解底层原理、性能优势及实用工具,您将掌握... 目录为什么升级XLS到XLSX值得投入?实际转换过程解析推荐技术方案对比Apache POI实现编程

C/C++中OpenCV 矩阵运算的实现

《C/C++中OpenCV矩阵运算的实现》本文主要介绍了C/C++中OpenCV矩阵运算的实现,包括基本算术运算(标量与矩阵)、矩阵乘法、转置、逆矩阵、行列式、迹、范数等操作,感兴趣的可以了解一下... 目录矩阵的创建与初始化创建矩阵访问矩阵元素基本的算术运算 ➕➖✖️➗矩阵与标量运算矩阵与矩阵运算 (逐元

Python使用FFmpeg实现高效音频格式转换工具

《Python使用FFmpeg实现高效音频格式转换工具》在数字音频处理领域,音频格式转换是一项基础但至关重要的功能,本文主要为大家介绍了Python如何使用FFmpeg实现强大功能的图形化音频转换工具... 目录概述功能详解软件效果展示主界面布局转换过程截图完成提示开发步骤详解1. 环境准备2. 项目功能结

使用Python实现网页表格转换为markdown

《使用Python实现网页表格转换为markdown》在日常工作中,我们经常需要从网页上复制表格数据,并将其转换成Markdown格式,本文将使用Python编写一个网页表格转Markdown工具,需... 在日常工作中,我们经常需要从网页上复制表格数据,并将其转换成Markdown格式,以便在文档、邮件或

Python将字符串转换为小写字母的几种常用方法

《Python将字符串转换为小写字母的几种常用方法》:本文主要介绍Python中将字符串大写字母转小写的四种方法:lower()方法简洁高效,手动ASCII转换灵活可控,str.translate... 目录一、使用内置方法 lower()(最简单)二、手动遍历 + ASCII 码转换三、使用 str.tr