1

私は夏の OO クラスに参加しており、明日はこのプロジェクトに基づいたテストがあります。基本的に、不特定の量のビットを保持する配列を作成し、この配列に対して演算を実行する 4 つの関数Set() //set bit with given index to 1( 、Unset() //set bit with given index to 0、Flip() // change bit (with given index)および) を作成する必要がありQuery() // return true if the given bit is set to 1, false otherwiseます。

誰かが興味を持っている場合は、ここに完全な説明があります: http://pastebin.com/v7BCCYjhといくつかのサンプル実行: http://pastebin.com/1ijh5p7p

私が抱えている問題は、高レベルの概念にあります。配列の各インデックスにビットのバイト表現を格納することを意図していると確信しています。それが本当なら、私は機能を実装する方法について完全に途方に暮れています。これにアプローチする方法について誰かが私にいくつかの指針を与えることができれば（私は明日中間試験のためにいくつかの疑似コードを書かなければならないので、今夜までにそれをよく理解する必要があります）、私は大いに感謝します.

.hそれが助けになるなら、これが私のものです

//   bitarray.h
//
//   BitArray class declaration

#ifndef _BITARRAY_H
#define _BITARRAY_H

#include <iostream>
using namespace std;

class BitArray
{
   friend ostream& operator<< (ostream& os, const BitArray& a);
   friend bool operator== (const BitArray&, const BitArray&);
   friend bool operator!= (const BitArray&, const BitArray&);

public:
   BitArray(unsigned int n);    // Construct an array that can handle n bits
   BitArray(const BitArray&);   // copy constructor
   ~BitArray();                 // destructor

   BitArray& operator= (const BitArray& a);  // assignment operator

   unsigned int Length() const;            // return number of bits in bitarray

   void Set   (unsigned int index);        // set bit with given index to 1
   void Unset (unsigned int index);        // set bit with given index to 0
   void Flip  (unsigned int index);        // change bit (with given index)
   bool Query (unsigned int index) const;  // return true if the given bit
                       //  is set to 1, false otherwise

private:
   unsigned char* barray;          // pointer to the bit array
   int arraySize;
};

#endif

そして私のコンストラクタ：

BitArray::BitArray(unsigned int n){
    int size = sizeof(char);

    if(n%(8*size) != 0)
        arraySize = ((n/(8*size))+1);
    else
        arraySize = n/(8*size);

    barray = new unsigned char[arraySize];

    for(int i = 0; i < arraySize; i++)
        barray[i] = 0;

}
4

2 に答える 2

2

Set()とについてQuery()、関心のあるビットを保持する単語の位置を見つけます (コードはchar単語として使用しているようです)。次に、この単語内のビットの位置を見つけます。特定のビットをアドレス指定するビットマスクを作成します。これにはシフト演算子が必要です。最終的に仕事をするのに役立つビット演算子を思い出してください。場合によっては、ビットごとの代入演算子がよりエレガントになります。

C++ のビットごとの XOR 演算子を覚えていますか? から学んだ概念でこれを使用しSet()て実装しFlip()ます。ビット単位の否定演算子を使用して、最終的に を実装しUnset()ます。

配列サイズを決定する方法は非常に複雑であることに注意してください。ceil(a/b) == floor((a+b-1)/b)ここで起こりうるケースを思い出してください。

std::vector許可されている場合は、プレーン配列の代わりに使用することを検討してください。下ネタバレ！

このクラスの興味深い専門分野もあります。

char実際のストレージ ユニット ( 、uint16_t、...) をパラメーターとして指定できるテンプレートにクラスを変換して、教師に感銘を与えます。まずtypedef char WORD_TYPE、 の定義を変更したときにコードが後でコンパイルされるかどうかを確認しますWORD_TYPE。

于 2012-07-11T23:47:51.377 に答える
0

整数の配列をビットの配列として扱うことができます。

たとえば、 arrayがあり、 53A = [0xC30FF0C3, 0xC20FF0C3]にアクセスしたいとします。少し。53を保持する an のインデックスを見つけることができます。ビット実行は であり、その実行中のビット位置は 21 です。
intfloor(53 / 32)1int53 % 32

機能に関してはFlip…

さて、あなたはすでに持っていますQuery(), Set(), Unset()。

単純

Flip(i) {
 Query(i) ? Unset(i) : Set(i)
}

仕事をするでしょう。

于 2012-07-11T23:57:03.757 に答える