このビットセットの実装を理解する (C++)

Question

数独ソルバー用のフレームを入手したところですが、使用されている構文とどのように進めるべきかがわかりません。彼らはそれをビットセットと呼んでいますが、検索しても同様のものは見つかりませんでした。

   // This file contains a simple implementation of sets of
   // digits between 1 and 9, called fields.
 #ifndef __SUDOKU_FIELD_H__
#define __SUDOKU_FIELD_H__
#include <iostream>
#include <cassert>
#include "digit.h"

class Field {
private:
  // Use integers for a bitset
  unsigned int _digits;
  // Number of digits in bitset
  unsigned int _size;
public:
  // Initialize with all digits between 1 and 9 included
  Field(void) 
    : _digits((1 << 1) | (1 << 2) | (1 << 3) |
          (1 << 4) | (1 << 5) | (1 << 6) |
          (1 << 7) | (1 << 8) | (1 << 9)), _size(9) {}

  // Return size of digit set (number of digits in set)
  unsigned int size(void) const {
    // FILL IN
  }

  // Test whether digit set is empty
  bool empty(void) const {
    // FILL IN
  }

  // Test whether set is assigned (that is, single digit left)
  bool assigned(void) const {
    // FILL IN
  }

  // Test whether digit d is included in set
  bool in(digit d) const {
    assert((d >= 1) && (d <= 9));
    // FILL IN
  }

  // Return digit to which the set is assigned

  digit value(void) const {
    assert(assigned());
    // FILL IN
  }



  // Print digits still included
  void print(std::ostream& os) const;

  // Remove digit d from set (d must be still included)
  void prune(digit d) {
    assert(in(d));
        // FILL IN
}

  // Assign field to digit d (d must be still included)
  void assign(digit d) {
    assert(in(d));
    // FILL IN
  }
};



// Print field
inline std::ostream&
operator<<(std::ostream& os, const Field& f) {
  f.print(os); return os;
}

#endif

明らかに //FILL IN は私が書くためのもので、ビットセットの意味は 9 ビットで、最初はすべて 1 に設定されています。問題は、それらをどのように操作または使用するかです。

あ、ちなみにこれは数字です。

#ifndef __SUDOKU_DIGIT_H__
#define __SUDOKU_DIGIT_H__
typedef unsigned char digit;
#endif

Answer 1

「ビットフィールド」は、メモリ内の整数をビットのリストであるかのように解釈したものです。この整数のビットを個別に設定、テスト、およびリセットします。コード内のコメントは、各関数で何をすべきかを正確に示しています。

「＆」と「|」を使用できますビット単位のANDとORの場合、および '<<'と '>>'は、すべてのビットを左右にシフトします。この記事は非常に役立ちます： http://en.wikipedia.org/wiki/Bitwise_operation

Answer 2

この初期化により、_digitsのビット1〜9が1に設定されます。(1 << n)という式は、1がnビット左にシフトされたことを意味します。a | bという表現は、ビット単位またはaとbの表現を意味します。

したがって、詳細には、(1 << n)のすべての式は、0 n 番目の位置に1を持つビットパターンになります。これらはすべてorです。一緒に、1に設定されたビットパターンビット1から9を生成します。 ジェネラコディセタグプレ

（未使用ビットは表示されていません）

Answer 3

4ビット:

0000

1 は 2 進数で次のようになります。

0001

シフトは単一ビットを選択するために使用されます。

0001 << 0 = 0001 // first bit

0001 << 1 = 0010 // second bit

0001 << 2 = 0100 // third bit

または、個々のビットを設定するために使用されます。

0000 | 0100 = 0100

ビットを取得するために使用されます。

0111 & 0001 = 0001

これがビットセットの仕組みです。

例：

unsigned int x = 0;
x |= 1 << 4; // set 5th bit
x |= 1 << 3; // set 4th bit
x |= 0x3; // set first 2 bits - 0x3 = 0011
unsigned int b = true;
x |= b << 7; // set 8th bit to value of b
if (x & (1 << 2)) { // check if 3rd bit is true
  // ...
} 
b = (x >> 3) & 1; // set b to value of 4th bit

ここでは、ビット数をカウントする方法と他の便利なアルゴリズムを紹介します。:

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}