集合的运算
问题：如何通过位运算求两个集合的交集、并集、差以及对称差呢？
运行截图：
其实很简单，步骤如下：
①将所有可能出现的元素从1~n编上号
这里我们假设所有可能的元素为'0'~'9'，'A'~'Z'，'a'~'z'
则编号为'0'~'9':0~9 'A'~'Z':10~35 'a'~'z':36~61
②利用一个整数保存一个集合的信息
C++中long long类型占有64个比特位，第i个比特位就表示了对应字符的有无：1代表有，0代表无
③利用两个整数的位运算即可表示相应集合的运算
"集合的交" --- (a & b)
"集合的并" --- (a | b)
"集合的差" --- a & (~b)
"集合的对称差" --- (a | b) & (~(a&b)）
④根据整数的运算结果反写出集合的运算结果即可
注意：系统默认只支持32位的移位运算，因此将1左移32位以上时：
1 << 40（×）
long long one = 1; one << 40; （√）
C++11代码如下：
/*C++11*/
#include <iOStream>
#include <string>
#include <cctype>
using namespace std;
//改进1：将字符操作改为string操作
//'0'~'9':0~9 'A'~'Z':10~35 'a'~'z':36~61
char getKey(int i)
{
if (i <= 9) return '0' + i;
else if (i <= 35) return 'A' + i - 10;
else return 'a' + i - 36;
}
//从字符串中得到64位的比特串
long long input()
{
string a;
cin >> a;
long long tmp = 0, one = 1;
for (auto p : a)
{
//改进2：判断'0'~'9'/'A'~'Z'/'a'~'z'时运用isnum(),isupper(),islower()函数
if (isdigit(p)) tmp |= one << (p - '0');
else if (isupper(p)) tmp |= one << (p - 'A' + 10);
else if (islower(p)) tmp |= one << (p - 'a' + 36);
}
return tmp;
}
//相应的字符集合
string output(long long a)
{
string tmp = "{";
long long one = 1;
for (int i = 0; i <= 61; ++i)
{
if (a & (one << i))
tmp = tmp + getKey(i) + ',';
}
if (*(tmp.end() - 1) == ',') *(tmp.end() - 1) = '}';
else tmp += '}';
return tmp+"\n";
}
//笛卡儿积
string outputDsc(long long a, long long b)
{
string tmp;
long long one = 1;
for (int i = 0; i <= 61; ++i)
for (int j = 0; j <= 61; ++j)
if ((a&(one << i) && (b&(one << j))))
tmp = tmp + '<' + getKey(i) + ',' + getKey(j) + '>' + ',';
if (!tmp.empty()) tmp.erase(tmp.end() - 1, tmp.end());
return '{'+tmp+"}\n";
}
int main()
{
long long a = 0, b = 0;
cout << "输入集合A:";
a = input();
cout << "输入集合B:";
b = input();
//改进3：使用位运算代替双重for循环查找
cout << "集合A:" << output(a);
cout << "集合B:" << output(b);
cout << "集合的交:" << output(a & b);
cout << "集合的并:" << output(a | b);
cout << "集合的差:" << output(a & (~b));
cout << "集合的对称差:" << output((a | b) & (~(a&b)));
cout << "集合的笛卡尔积:" << endl << outputDsc(a, b);
system("pause");
return 0;
}谢谢观看~
相关阅读
关于java集合类Collections.在前端开发中可能用到的比较少，不过java后台用到的应该挺多，比较后台主要是基于数据库的读写的，对于并发
如何把得到的结果集放到map集合中+取得列和值ResultSe
1先利用sql语句进行查询2利用反射创建实体类 的对象emp3获取结果集的列名4获取结果集的每一列的值，结合3得到一个Map，键是列名，值的
先说下原因，最近项目中出现了获取网络数据混乱的情况，经过仔细查看才知道是加入集合的顺序出了问题，由于我是循环获取id，然后再循环请
题目描述 输入一个正整数N，输出N的阶乘。 输入描述: 正整数N(0<=N<=1000) 输出描述: 输入可能包括多组数据，对于每一组输入数据，输出
Collection集合的特点是每次进行单个对象的保存，如果现在要进行一对对象的保存，就只能用Map集合来完成，即Map集合中会一次性保存两个