技术原理

【c 标準函式库(STL)手记】bitset 详细介绍

今日学习培训c 里边的bitset专用工具,
觉得蛮好用的,自身手记一下

bitset介绍

特点: 只由0和1构成,便捷的做位元与运算
(若是int或long long数最多也就32位系统与64位,bitset能够 超出64位)

一、导入函式库

要应用bitset,必须在程序开始添加这二行

#include <bitset>
using namespace std;

二、宣布

bitset的宣布方法以下:
(比如说宣布一百个bit的bitset)

bitset<100> b;

宣布的另外复位

  1. 立即以整数金额复位
bitset<100> b = 1; //或bitset<100> b(1)
  1. 以长整数金额复位
bitset<100> b(222UL);
  1. 以字串复位
s = "100110101";
bitset<100> b(s);

三、位元与运算

  1. AND 与运算
b = b0 & b1;
  1. OR 与运算
b = b0 | b1;
  1. XOR 与运算
b = b0 ^ b1;
  1. index与运算(从右往左数的十位数)
b[0] = 1;
  1. 左移与运算
b = b0 << 2;
  1. 右移与运算
b = b0 >> 2;
  1. 每一个位元反方向
b = ~b0;

四、键入与輸出(cin, cout)

  1. cin
bitset<8> b;
cin >> b; //假定键入1010
cout << b << endl;

結果:
00001010

  1. cout
    显示信息 b 之內容,长短为 b.size(),
    範例:
bitset<8> b(string("11011"));
cout << b << endl;

結果:
00011011

运用: 子集合和难题

出现意外发觉bitset合适用来解这样子的一个經典难题,
让你一个结合(原素可重複),一个总体目标正整数target,
分辨是不是有子集合的和 = target

範例程序:

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

/*
涵数作用: 查验列阵Set里边(原素可重複)是不是有子集合的和 = Sum
留意sum = 0 时回答为 True

解法表明:
bits是一个bit_vector,
在其中从右往左数第i个位,意味着迄今为止的Set的原素是不是子集和= Sum
譬如说 Set = [2,2,3,5]
一开始bits = 1,
升级一轮以后就变为 1 | 101 = 101(二进位看来),
再升级一轮以后变为 10100 | 101 = 10101,
讲解为[2,2]能够 凑出子集和 = 0, 2, 4

应用STL bitset便能够 防止int或long long会溢位的难题
*/
bool isSubsetSum(vector<int> &Set, int Sum)
{
    bitset<1100> bits(1); //复位bits = 1(bitset<>里的数表明数最多几位数)
    for (int num : Set)
    {
        bits |= bits << num;
    }
    return bits[Sum]; //查验从右往左数的第Sum位是否1
}


int main()
{
    vector<int> arr = {2,2,3,5};
    int target = 9; //检测arr里边是不是有子集和 = target
    cout << (isSubsetSum(arr, target)?"YES":"NO") << endl;
}

参考文献

  1. cplusplus.com- bitset
  2. bitset 梳理

你也可能喜欢

发表评论

您的电子邮件地址不会被公开。 必填项已用 * 标注

提示:点击验证后方可评论!

插入图片
人工智能ai电视机 投稿者
我还没有学会写个人说明!
最近文章
  • * 没有更多文章了
  • 热门搜索

    分类目录