34 255, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
35 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
36 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
37 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
38 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
39 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
40 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
41 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
42 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
43 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
44 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
45 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
46 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
47 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
48 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
49 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
55 0, 0, 0, 0x2, 0, 0x4, 0x4, 0x6,
56 0, 0x8, 0x8, 0x0a, 0x08, 0x0c, 0x0c, 0x0e,
57 0, 0x10, 0x10, 0x12, 0x10, 0x14, 0x14, 0x16,
58 0x10, 0x18, 0x18, 0x1a, 0x18, 0x1c, 0x1c, 0x1e,
59 0, 0x20, 0x20, 0x22, 0x20, 0x24, 0x24, 0x26,
60 0x20, 0x28, 0x28, 0x2a, 0x28, 0x2c, 0x2c, 0x2e,
61 0x20, 0x30, 0x30, 0x32, 0x30, 0x34, 0x34, 0x36,
62 0x30, 0x38, 0x38, 0x3a, 0x38, 0x3c, 0x3c, 0x3e,
63 0, 0x40, 0x40, 0x42, 0x40, 0x44, 0x44, 0x46,
64 0x40, 0x48, 0x48, 0x4a, 0x48, 0x4c, 0x4c, 0x4e,
65 0x40, 0x50, 0x50, 0x52, 0x50, 0x54, 0x54, 0x56,
66 0x50, 0x58, 0x58, 0x5a, 0x58, 0x5c, 0x5c, 0x5e,
67 0x40, 0x60, 0x60, 0x62, 0x60, 0x64, 0x64, 0x66,
68 0x60, 0x68, 0x68, 0x6a, 0x68, 0x6c, 0x6c, 0x6e,
69 0x60, 0x70, 0x70, 0x72, 0x70, 0x74, 0x74, 0x76,
70 0x70, 0x78, 0x78, 0x7a, 0x78, 0x7c, 0x7c, 0x7e,
71 0, 0x80, 0x80, 0x82, 0x80, 0x84, 0x84, 0x86,
72 0x80, 0x88, 0x88, 0x8a, 0x88, 0x8c, 0x8c, 0x8e,
73 0x80, 0x90, 0x90, 0x92, 0x90, 0x94, 0x94, 0x96,
74 0x90, 0x98, 0x98, 0x9a, 0x98, 0x9c, 0x9c, 0x9e,
75 0x80, 0xa0, 0xa0, 0xa2, 0xa0, 0xa4, 0xa4, 0xa6,
76 0xa0, 0xa8, 0xa8, 0xaa, 0xa8, 0xac, 0xac, 0xae,
77 0xa0, 0xb0, 0xb0, 0xb2, 0xb0, 0xb4, 0xb4, 0xb6,
78 0xb0, 0xb8, 0xb8, 0xba, 0xb8, 0xbc, 0xbc, 0xbe,
79 0x80, 0xc0, 0xc0, 0xc2, 0xc0, 0xc4, 0xc4, 0xc6,
80 0xc0, 0xc8, 0xc8, 0xca, 0xc8, 0xcc, 0xcc, 0xce,
81 0xc0, 0xd0, 0xd0, 0xd2, 0xd0, 0xd4, 0xd4, 0xd6,
82 0xd0, 0xd8, 0xd8, 0xda, 0xd8, 0xdc, 0xdc, 0xde,
83 0xc0, 0xe0, 0xe0, 0xe2, 0xe0, 0xe4, 0xe4, 0xe6,
84 0xe0, 0xe8, 0xe8, 0xea, 0xe8, 0xec, 0xec, 0xee,
85 0xe0, 0xf0, 0xf0, 0xf2, 0xf0, 0xf4, 0xf4, 0xf6,
86 0xf0, 0xf8, 0xf8, 0xfa, 0xf8, 0xfc, 0xfc, 0xfe
91 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
92 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
93 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
94 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
95 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
96 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
97 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
98 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
99 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
100 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
101 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
102 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
103 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
104 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
105 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
106 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
113 array_ =
new uint32_t[WordLength()];
118 if (src.bit_size_ > 0) {
119 array_ =
new uint32_t[WordLength()];
120 memcpy(array_, src.array_, ByteLength());
127 Alloc(src.bit_size_);
128 if (src.bit_size_ > 0) {
129 memcpy(array_, src.array_, ByteLength());
147 int wordlen = WordLength();
154 uint32_t new_bit_size;
157 ReverseN(&new_bit_size,
sizeof(new_bit_size));
160 int wordlen = WordLength();
163 for (
int i = 0; i < wordlen; ++i)
164 ReverseN(&array_[i],
sizeof(array_[i]));
170 memset(array_, 0, ByteLength());
173 memset(array_, ~0, ByteLength());
180 int next_bit = prev_bit + 1;
181 if (next_bit >= bit_size_)
return -1;
183 int next_word = WordIndex(next_bit);
184 int bit_index = next_word * kBitFactor;
185 int word_end = bit_index + kBitFactor;
186 uint32_t word = array_[next_word];
187 uint8_t
byte = word & 0xff;
188 while (bit_index < word_end) {
189 if (bit_index + 8 > next_bit &&
byte != 0) {
190 while (bit_index +
lsb_index_[
byte] < next_bit &&
byte != 0)
201 int wordlen = WordLength();
202 while (next_word < wordlen && (word = array_[next_word]) == 0) {
204 bit_index += kBitFactor;
206 if (bit_index >= bit_size_)
return -1;
208 while ((word & 0xff) == 0) {
217 int wordlen = WordLength();
219 for (
int w = 0; w < wordlen; ++w) {
220 uint32_t word = array_[w];
221 for (
int i = 0; i < 4; ++i) {
232 int length = std::min(WordLength(), other.WordLength());
233 for (
int w = 0; w < length; ++w)
234 array_[w] |= other.array_[w];
237 int length = std::min(WordLength(), other.WordLength());
238 for (
int w = 0; w < length; ++w)
239 array_[w] &= other.array_[w];
240 for (
int w = WordLength() - 1; w >= length; --w)
244 int length = std::min(WordLength(), other.WordLength());
245 for (
int w = 0; w < length; ++w)
246 array_[w] ^= other.array_[w];
251 int length = std::min(v1.WordLength(), v2.WordLength());
252 for (
int w = 0; w < length; ++w)
253 array_[w] = v1.array_[w] ^ (v1.array_[w] & v2.array_[w]);
254 for (
int w = WordLength() - 1; w >= length; --w)
255 array_[w] = v1.array_[w];
260 void BitVector::Alloc(
int length) {
261 int initial_wordlength = WordLength();
263 int new_wordlength = WordLength();
264 if (new_wordlength != initial_wordlength) {
266 array_ =
new uint32_t[new_wordlength];