C++

Forum

 
Constraints in memory footprints of bitarr

sparki (57)
Hi, Sorry if I am making a few posts. But I'd really need help here as deadline is near. Anyway, I am having trouble with the additional constraints
on memory footprint that my lecturer has given in his test cases shown in int main() below. I am supposed to pass all test cases such that no "failed" in the output comes up. I hope someone is able to help in this. Or at least have an idea of what I need to do. Because I am at a total lost. Thank you. Note: I am not supposed to modify main(). 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
 
#include <iostream>    
#include <vector>    

template<size_t k>
class bitarr
{
public:
	bitarr()
	{
		array = new int[k];
 		memset(array, 0, sizeof(int) * k);

	}
	bitarr& set(size_t pos, bool val = true)
	{
		array[pos] = val;
		return *this;
	}
	const std::string to_string()
	{
		std::string str;
		for (unsigned int i = k; i-- > 0;)
		{
			str.push_back('0' + array[i]);
		}
		return str;
	}
private:
	int* array;
 };
int main()
{
	int index = 0;

	for (int index{}; index < 4; index++)
	{
		switch (index)
		{
			case 0:
			{
				try
				{
					constexpr size_t HUGE_value = 1024 * 1024;
					if constexpr (
						sizeof(bitarr<HUGE_value * CHAR_BIT>) !=
						HUGE_value
						)
					{
						throw std::runtime_error
						{
							"Use an array since there is no "
							"data ype that's big enough to store all the bits."
						};
					}
				}
				catch (const std::exception& exception)
				{
					std::cout
						<< "failed " << std::endl;

				}
			}
			break;
			case 1:
			{
				try
				{
					if constexpr (sizeof(bitarr<1>) != 1)
					{
						throw std::runtime_error
						{
							"1 bye is necsary for (CHAR_BIT*2) bits."
						};
					}
				}
				catch (const std::exception& exception)
				{
					std::cout
						<< "failed " << std::endl;

				}
			}
			break;
			case 2:
			{
				try
				{
					if constexpr (
						sizeof(bitarr<CHAR_BIT * 2>) !=
						2
						)
					{
						throw std::runtime_error
						{
							"2 bye is necery for (CHAR_BIT*2) bits."
						};
					}
				}
				catch (const std::exception& exception)
				{
					std::cout
						<< "failed " << std::endl;

				}
			}
			break;
			case 3:
			{
				try
				{
					constexpr size_t MAX_int_size = sizeof(long long) / CHAR_BIT;
					if constexpr (
						sizeof(bitarr<MAX_int_size * CHAR_BIT + 1>) !=
						MAX_int_size + 1
						)
					{
						throw std::runtime_error
						{
							"Use an array since there is no "
							"data type that's big enough to store all the bits."
						};
					}
				}
				catch (const std::exception& exception)
				{
					std::cout
						<< "failed " << std::endl;

				}
			}
			break;
		}
			
	}
 

}
Last edited on
salem c (3687)
> array = new int[k];
You're allocating k int's, not k bits.

number_of_bits_in_int = sizeof(int) * CHAR_BIT
number_of_ints_you_need = ( k + number_of_bits_in_int - 1 ) / number_of_bits_in_int;


sparki (57)
Hi Salem,

Thanks for the reply,

So am I correct to say I'll have to replace k with number_of_ints_you_need?

array = new int[number_of_ints_you_need]; <- like this?

I tried to do what you have recommended above, but still doesn't work. Are you able to show me? I might be doing it wrong.

Last edited on
sparki (57)
Like this? in my main code, it still fails. Not sure where I've gone wrong.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
#include <iostream>    
#include <vector>    

template<size_t k>
class bitarr
{
private:
	static const unsigned number_of_bits_in_int = sizeof(int) * CHAR_BIT;
	static const unsigned number_of_ints_you_need = (k + number_of_bits_in_int - 1) / number_of_bits_in_int;
	int* array;
public:
	bitarr()
	{
		array = new int[number_of_ints_you_need];
 		memset(array, 0, sizeof(int) * k);

	}
	bitarr& set(size_t pos, bool val = true)
	{
		array[pos] = val;
		return *this;
	}
	const std::string to_string()
	{
		std::string str;
		for (unsigned int i = k; i-- > 0;)
		{
			str.push_back('0' + array[i]);
		}
		return str;
	}

 };
Last edited on
jonnin (11348)
I am not sure what you are doing, but 2 more hints that may help you:
1) vector<bool> is *usually* optimized (on major compilers; not sure if this is a language requirement or a recommended tweak) to be effectively a vector of bits.
2) there are the bitset tools

sparki (57)
Hi, I am not supposed to be using the bitset tools. It's a requirement by the school. Vector<bool>? Can I know why use bool instead of int?
Last edited on
salem c (3687)
> memset(array, 0, sizeof(int) * k);
Maybe
memset(array, 0, sizeof(int) * number_of_ints_you_need);
dhayden (5795)
1
2
3
4
5
6
7
 
if constexpr (sizeof(bitarr<1>) != 1)
{
	throw std::runtime_error
	{
		"1 byte is necessary for (CHAR_BIT*2) bits."
	};
}

This means a bitarr with 1 bit must be exactly 1 byte long. You can't store a pointer to an array because the pointer alone is 4 or 8 bytes, depending on whether you're compiling a 32 or 64 bit program . You can't store an array of ints because an int is typically 4 bytes. You must use an array of chars and it must be stored directly in the bitarr<>. Actually, you should use unsigned char.

To get, set, and clear the i'th bit, you'll need to know the index in the array of the byte that contains it, and its position within that byte. For the position, you'll find it easier to create the bit mask for it. In other words, an unsigned char that has just 1 bit set - the one corresponding to the bit you're interested in.

For these, I suggest two private members:
1
2
3
4
5
 
// find the index of the byte in arr that contains bit #pos
size_t index(size_t pos);

// Return the bit mask for bit #pos
unsigned char mask(size_t pos);


Test these functions. For example, you could temporarily make them public and add this to main():
1
2
3
4
5
 
    bitarr<10> ba;
    for (unsigned i=0; i<10; ++i) {
        std::cout << "pos " << std::dec << i << " is byte " << ba.index(i)
                  << " and mask 0x" << std::hex << (int)ba.mask(i) << '\n';
    }

pos 0 is byte 0 and mask 0x1
pos 1 is byte 0 and mask 0x2
pos 2 is byte 0 and mask 0x4
pos 3 is byte 0 and mask 0x8
pos 4 is byte 0 and mask 0x10
pos 5 is byte 0 and mask 0x20
pos 6 is byte 0 and mask 0x40
pos 7 is byte 0 and mask 0x80
pos 8 is byte 1 and mask 0x1
pos 9 is byte 1 and mask 0x2


Once you have these, the rest of the code is simple, but you may have to brush up on binary numbers and how to manipulate them in C++
jonnin (11348)
again, vector<bool> is optimized by the compiler to store it as bits (sorta... details behind the magic don't matter).
vector<int> is going to use {32, 64, whatever} bits for each location, which is a LOT of wasted space. even using char here (char is a type of integer, if you didnt know) is a factor of 8 times bigger than necessary. Bools are effectively (logically) a bit anyway (true, false, 1/0 same idea) so the compiler writers tweaked the vector class for them specifically to save space. If you want a large # of bits, this is a good way to do it.
Last edited on
dhayden (5795)
vector<bool> won't meet the size requirements that are tested in the main program. On my system, bitset<> won't either. It appears to use 64-bit values (unsigned long long?) to store the bits.

I have verified that an array of unsigned char will meet the requirements.
jonnin (11348)
that makes sense -- the design of both of those was for dealing with giant things, idea that no one cares that your 2 billion bits have 63 more than necessary worst case. Apologies if it was unhelpful... I didn't think about the tight low end requirement.
Last edited on
Topic archived. No new replies allowed.