1

学校のプロジェクトでは、独自のビット文字列実装を使用して基本的なセット操作を実行する必要があります (STL の使用は禁止されています)。私は非常に基本的ですが機能的なビットベクトルラッパーをセットアップしており、ネイティブの C ビット演算子 (ビット AND、OR、XOR) などで計算できるすべてのセット操作で完全に機能します。

ただし、セット減算は必要な操作の 1 つです。ビット文字列操作を使用して計算する方法がわかりません。減算の意味を設定する(A - B) = A にあるが B にないすべての値

これが私の実装と 2 つの基本的な操作です。

#include <iostream>
#include <cstdlib>
#include <vector>

#define WORDSIZE 9 // the sets will only ever contain numbers from 0 to 9
#define BIT_WS 5
#define MASK 0x1f

using namespace std;

int init_bitvector(int **bv, int val)
{
    *bv = (int*)calloc(val / WORDSIZE + 1, sizeof(int));
    return *bv != NULL;
}

void set(int bv[], int i)
{
    bv[i >> BIT_WS] |= (1 << (i & MASK));
}

int member(int bv[], int i)
{
    return bv[i >> BIT_WS] & (1 << (i & MASK));
}

int main()
{
    bool input_check = true; // Use to control user input
    int input_temp;
    int *bitvectorA, *bitvectorB, *bitvectorOR, *bitvectorAND, *bitvectorDIFF;

    vector<int> SetA;
    vector<int> SetB;

    init_bitvector(&bitvectorA, WORDSIZE);
    init_bitvector(&bitvectorB, WORDSIZE);
    init_bitvector(&bitvectorOR, WORDSIZE);
    init_bitvector(&bitvectorAND, WORDSIZE);
    init_bitvector(&bitvectorDIFF, WORDSIZE);

// ...user input for set values...

for (int i = 0; i < SetA.size(); i++)
{
    set(bitvectorA, SetA[i]);
}

for (int i = 0; i < SetB.size(); i++)
{
    set(bitvectorB, SetB[i]);
}

cout << endl << "Intersection of Set A and Set B:" << endl;

*bitvectorAND = (*bitvectorA & *bitvectorB);

for(int i = 0; i <= WORDSIZE; i++)
{
    if(member(bitvectorAND, i))
    {
        cout << i << ' ';
    }
}
cout << endl;

cout << endl << "Union of Set A and Set B:" << endl;

*bitvectorOR = (*bitvectorA | *bitvectorB);

for(int i = 0; i <= WORDSIZE; i++)
{
    if(member(bitvectorOR, i))
    {
        cout << i << ' ';
    }
}
cout << endl;

これは、ビット単位の演算子を持つすべての操作で意図したとおりに機能することを確認できます。同等の方法でSet Subtractionを実装する方法がわかりません。

4

1 に答える 1

1

解決： 

*bitvectorDIFF = (*bitvectorA & ~*bitvectorB);

Cheers と hthに感謝します。-先端のアルフ

于 2016-10-16T22:11:43.670 に答える