Nemo  2.3.46
bitstring.h
Go to the documentation of this file.
1 
29 #ifndef BITSRING_H
30 #define BITSRING_H
31 
32 #include <bitset>
33 #include <assert.h> //for CHAR_BIT
34 #include <limits.h>
35 #include <string.h>
36 #include <iostream>
37 
38 #ifdef _GLIBCPP_BITSET_BITS_PER_WORD
39 #define BITS_PER_WORD _GLIBCPP_BITSET_BITS_PER_WORD
40 #else
41 #define BITS_PER_WORD (CHAR_BIT*sizeof(unsigned long))
42 #endif
43 
44 #ifndef _GLIBCPP_BITSET_WORDS
45 #define BITSET_WORDS(__n) \
46 ((__n) < 1 ? 1 : ((__n) + BITS_PER_WORD - 1)/BITS_PER_WORD)
47 #else
48 #define BITSET_WORDS(__n) _GLIBCPP_BITSET_WORDS(__n)
49 #endif
50 
51 #define MASK ULLONG_MAX
52 
53 //define MASK = (BITS_PER_WORD == 64 ? 0xFFFFFFFFFFFFFFFF : 0xFFFFFFFF)
54 
56 class bitstring {
57 
58 public:
59 
60  typedef unsigned long _ul;
61 
62  class reference
63  {
64  friend class bitstring;
65 
66  _ul *_word;
67  size_t _bitpos;
68 
69  // left undefined
70  reference();
71 
72  public:
73  reference(bitstring& bs, size_t pos)
74  {
75  _word = bs.getword_atPos( pos );
76  _bitpos = pos % BITS_PER_WORD;
77  }
78 
80  { }
81 
82  // For b[i] = x;
84  {
85  if (x)
86  *_word |= ( 1UL << ( _bitpos % BITS_PER_WORD ) );
87  else
88  *_word &= ~( 1UL << ( _bitpos % BITS_PER_WORD ) );
89  return *this;
90  }
91 
92  // For b[i] = b[j];
94  {
95  if ((*(j._word) & ( 1UL << ( j._bitpos % BITS_PER_WORD ) ) ))
96  *_word |= ( 1UL << ( _bitpos % BITS_PER_WORD ) );
97  else
98  *_word &= ~( 1UL << ( _bitpos % BITS_PER_WORD ) );
99  return *this;
100  }
101 
102  // Flips the bit
103  bool operator~() const
104  { return (*(_word) & ( 1UL << ( _bitpos % BITS_PER_WORD ) ) ) == 0; }
105 
106  // For __x = b[i];
107  operator bool() const
108  { return (*(_word) & ( 1UL << ( _bitpos % BITS_PER_WORD ) ) ) != 0; }
109 
110  // For b[i].flip();
112  {
113  *_word ^= ( 1UL << ( _bitpos % BITS_PER_WORD ) );
114  return *this;
115  }
116  };
117 
118  friend class reference;
119 
120  bitstring (size_t length)
121  : _size(length), _words( BITSET_WORDS(length) ), _data(0)
122  {
123  _data = new _ul [_words];
124  memset(_data, 0, _words * sizeof(_ul));
125  }
126 
127  bitstring (const bitstring& b)
128  : _size(b._size), _words(b._words), _data(0)
129  {
130  _data = new _ul [_words];
131  memcpy(_data, b._data, _words * sizeof(_ul));
132  }
133 
134  ~bitstring () {if(_data != NULL) delete [] _data;}
135 
136  _ul* getword_atPos (size_t pos)
137  { return &_data[ pos / BITS_PER_WORD ]; }
138 
139  _ul* getword_atIdx (size_t index)
140  { return &_data[ index ]; }
141 
142  size_t size ( ) {return _size;}
143 
144  size_t nb_words ( ) {return _words;}
145 
146  reference operator[] (size_t pos)
147  { return reference(*this, pos); }
148 
149  bool operator[] (size_t n) const
150  { return static_cast<bool>( _data[ n / BITS_PER_WORD ] & ( 1UL << ( n % BITS_PER_WORD ) ) ); }
151 
153  {
154  _size = b._size;
155  _words = b._words;
156  if(_data != NULL) delete [] _data;
157  _data = new _ul [_words];
158  memcpy(_data, b._data, _words * sizeof(_ul));
159  return *this;
160  }
161 
163  {
164  for (size_t i = 0; i < _words; i++)
165  _data[i] &= x._data[i];
166  return *this;
167  }
168 
170  {
171  for (size_t i = 0; i < _words; i++)
172  _data[i] |= x._data[i];
173  return *this;
174  }
175 
177  {
178  for (size_t i = 0; i < _words; i++)
179  _data[i] ^= x._data[i];
180  return *this;
181  }
182 
184  {
185  for (size_t i = 0; i < _words; i++)
186  _data[i] = ~(_data[i]);
187  return *this;
188  }
189 
191  {
192  bitstring result(*this);
193  result &= x;
194  return result;
195  }
196 
198  {
199  bitstring result(*this);
200  result |= x;
201  return result;
202  }
203 
205  {
206  bitstring result(*this);
207  result ^= x;
208  return result;
209  }
210 
212  unsigned int local_popcountl (_ul wd)
213  {
214  unsigned char* c = (unsigned char*)&wd;
215  unsigned short cnt = 0;
216 
217  for(unsigned int i = 0; i < sizeof(_ul); i++)
218  cnt += _bit_count[ (unsigned int)c[i] ];
219 
220  return (unsigned int) cnt;
221  }
222 
224  unsigned int count ( )
225  {
226  unsigned int cnt = 0;
227 
228  for(size_t i = 0; i < _words; i++)
229  cnt += local_popcountl(_data[i]);
230 
231  return cnt;
232  }
233 
235  void set (size_t n) {_data[n / BITS_PER_WORD] |= (1UL << (n % BITS_PER_WORD));}
236 
238  void flip (size_t n) {_data[n / BITS_PER_WORD] ^= (1UL << (n % BITS_PER_WORD));}
239 
241  void set_data (_ul* srce, size_t nbwrd)
242  {
243  // if(nbwrd != _words) {
244  // std::cerr<<"bitstring::set_data: different sizes in memcpy!!\n";
245  // exit(1);
246  // }
247  assert(nbwrd == _words);
248  memcpy(_data, srce, nbwrd * sizeof(_ul));
249  }
251  void reset ( )
252  { for(unsigned int i = 0; i < _words; i++) _data[i] = 0UL; }
253 
255  void copy (const bitstring& b)
256  { memcpy(_data, b._data, _words * sizeof(_ul)); }
257 
259  void copy (const bitstring& b, size_t word_pos)
260  { _data[ word_pos ] = b._data[ word_pos ]; }
261 
262  void copy (const bitstring& b, size_t from, size_t to)
263  {
264  assert(to <= _size);
265 
266  size_t start_w, end_w, start_l, end_l;
267  _ul mask, tmpl;
268 
269  start_w = from / BITS_PER_WORD;
270  end_w = to / BITS_PER_WORD;
271 
272  start_l = from % BITS_PER_WORD;
273  end_l = to % BITS_PER_WORD;
274 
275  if(start_w != end_w) {
276  //copy wihtin first word:
277  mask = (MASK << start_l);
278 
279  _data[ start_w ] &= ~mask;
280  tmpl = b._data[ start_w ] & mask;
281 
282  _data[ start_w ] |= tmpl;
283 
284  //copy words in-between:
285  size_t k = start_w + 1;
286 
287  memcpy(&_data[k], &b._data[k], (end_w - k)*sizeof(_ul));
288 
289 // for(size_t k = start_w + 1; k < end_w; ++k) {
290 //
291 // _data[ k ] = b._data[ k ];
292 //
293 // }
294  //copy within last word:
295  mask = (MASK >> (BITS_PER_WORD - end_l) );
296 
297  _data[ end_w ] &= ~mask;;
298  tmpl = b._data[ end_w ] & mask;
299 
300  _data[ end_w ] |= tmpl;
301 
302  } else {
303  //bits to copy are within a word:
304  mask = (MASK << start_l) & (MASK >> (BITS_PER_WORD - end_l) );
305 
306  _data[ start_w ] &= ~mask;
307  tmpl = b._data[ start_w ] & mask;
308 
309  _data[ start_w ] |= tmpl;
310 
311  }
312 
313  }
314 
315 private:
316 
317  size_t _size;
318  size_t _words;
319 
320  _ul *_data;
321 
322 
323  static unsigned char _bit_count[256];
324 
325 };
326 
327 #endif
328 
static unsigned char _bit_count[256]
Definition: bitstring.h:323
friend class reference
Definition: bitstring.h:118
bitstring & operator^=(const bitstring &x)
Definition: bitstring.h:176
reference(bitstring &bs, size_t pos)
Definition: bitstring.h:73
bitstring & operator|=(const bitstring &x)
Definition: bitstring.h:169
bitstring & operator&=(const bitstring &x)
Definition: bitstring.h:162
Definition: bitstring.h:62
#define BITS_PER_WORD
Definition: bitstring.h:41
bitstring operator~(void)
Definition: bitstring.h:183
void copy(const bitstring &b, size_t from, size_t to)
Definition: bitstring.h:262
bitstring operator^(const bitstring &x)
Definition: bitstring.h:204
size_t _size
Definition: bitstring.h:317
Non-template and faster implementation of std::bitset.
Definition: bitstring.h:56
unsigned int count()
Count number of set bits.
Definition: bitstring.h:224
void copy(const bitstring &b, size_t word_pos)
Copy one word.
Definition: bitstring.h:259
~bitstring()
Definition: bitstring.h:134
bitstring operator|(const bitstring &x)
Definition: bitstring.h:197
bitstring operator&(const bitstring &x)
Definition: bitstring.h:190
size_t nb_words()
Definition: bitstring.h:144
void copy(const bitstring &b)
Unchecked copy, assumes we have sames sizes.
Definition: bitstring.h:255
_ul * _data
Definition: bitstring.h:320
unsigned int local_popcountl(_ul wd)
Counts number of one's in string using a bit table count.
Definition: bitstring.h:212
bitstring(const bitstring &b)
Definition: bitstring.h:127
reference & flip()
Definition: bitstring.h:111
_ul * getword_atPos(size_t pos)
Definition: bitstring.h:136
void set(size_t n)
Set a bit to 1.
Definition: bitstring.h:235
void reset()
Set all bits to 0.
Definition: bitstring.h:251
#define BITSET_WORDS(__n)
Definition: bitstring.h:45
_ul * _word
Definition: bitstring.h:66
reference & operator=(bool x)
Definition: bitstring.h:83
#define MASK
Definition: bitstring.h:51
unsigned long _ul
Definition: bitstring.h:60
bitstring & operator=(const bitstring &b)
Definition: bitstring.h:152
bool operator~() const
Definition: bitstring.h:103
void set_data(_ul *srce, size_t nbwrd)
Copy bits from an array of unsigned long words.
Definition: bitstring.h:241
bitstring(size_t length)
Definition: bitstring.h:120
size_t _words
Definition: bitstring.h:318
size_t size()
Definition: bitstring.h:142
reference & operator=(const reference &j)
Definition: bitstring.h:93
_ul * getword_atIdx(size_t index)
Definition: bitstring.h:139
~reference()
Definition: bitstring.h:79
void flip(size_t n)
Flip the bit at n.
Definition: bitstring.h:238
size_t _bitpos
Definition: bitstring.h:67
reference operator[](size_t pos)
Definition: bitstring.h:146

Generated for Nemo v2.3.0 by  doxygen 1.8.8 --
Catalogued on GSR