Understanding this bitset implementation (C++)

Question

I just got this frame for a sudoku solver, but I don't understand the syntax they've used and how I'm supposed to proceed. They call it a bitset, but upon searching for it I found nothing similar.

   // 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

Obviously the //FILL IN's are for me to write, and the meaning of the bitset is 9 bits where all of them initially are set to 1. The question is how I manipulate or use them.

Oh, by the way, this is a digit:

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

google, 1st result: http://www.cplusplus.com/reference/stl/bitset/ — OSH, Dec 02 '11 at 10:55
@OrenS. He need to develop his "own" bitset. Your comment is not helpful. — FailedDev, Dec 02 '11 at 10:58
@FailedDev the link I sent starts with an explanation of how a bitset works. I didn't mean for him to use that implementation, but rather that he should at least try to google before asking. — OSH, Dec 02 '11 at 11:07
@OrenS. I think you could post that as the answer, with a bit of introduction if you can spare the time — sehe, Dec 02 '11 at 11:17
I've seen your other questions, they are mostly homework. Please next time at least try before asking, do a google search and show us some attempt you've made. We're not here to do your homework for you. — Giovanni Funchal, Dec 02 '11 at 15:46

score 4 · Answer 1 · answered Dec 02 '11 at 10:57

This initialization sets the bits 1 - 9 of _digits to 1. The expression (1 << n) means 1 shifted n bits to the left. The expression a | b means a bit-wise or of a and b.

So, in detail, all of the expressions (1 << n) result in a bit-pattern with all zeroes and a 1 at the n th position, for 0 < n < 10. All of these are or'd together, to yield a bit-pattern bits 1 through 9 set to 1:

(1 << 1)   0010 |
(1 << 2)   0100 |
(1 << 3)   1000
======================
           1110

(unused bits not shown)

score 4 · Accepted Answer · edited Dec 02 '11 at 11:18

4

A "bitfield" is just an interpretation of a integer in memory as if it was a list of bits. You will be setting, testing and resetting bits in this integer individually, and the comments in the code tell you exactly what to do in each function.

You can use '&' and '|' for bitwise AND and OR, and '<<' and '>>' for shifting all bits to the left and right. This article can be very helpful to you: http://en.wikipedia.org/wiki/Bitwise_operation

edited Dec 02 '11 at 11:18

sehe

374,641
47
450
633

answered Dec 02 '11 at 11:03

Giovanni Funchal

8,934
13
61
110

In response to the deleted message: I know you're not supposed to do my homework for me, and I don't expect you to. Most of my question are tagged 'homework', simply because most of my programs are in my studies, and the homework tag tells people to not give me a complete answer, but to point me in the right direction. In fact, all I asked for here was how I could change the variable _digits. You (and several others) answered this, and more, so thank you. I still think my questions here are legit. – Rickard Dec 03 '11 at 00:54
I have absolutely no problem with you asking a question related to homework specially if you tag it correctly. What I'm saying is that if everyone did this we would be overwhelmed by such questions. Next time make sure you do enough research from your side before asking, at least spend 5 min googling. Searching for "c++ bitset" returns this in the 3rd result (http://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit-in-c). – Giovanni Funchal Dec 03 '11 at 10:47

Pubby · Answer 3 · 2011-12-02T11:07:55.707

4 bits:

0000

1 in binary is:

0001

Shifting is used to choose a single bit:

0001 << 0 = 0001 // first bit

0001 << 1 = 0010 // second bit

0001 << 2 = 0100 // third bit

Or is used to set individual bits:

0000 | 0100 = 0100

And is used to retrieve bits:

0111 & 0001 = 0001

This is how bitsets work.

Example:

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

Here is a way to count number of bits, along with other helpful algorithms:

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
}

Understanding this bitset implementation (C++)

3 Answers3