CareerCup

Could you explain the desired behavior? Does the bit map act as a memory pool for bits?

#include <vector>
class BitMap
{
        const int N;
        vector<int>    bit_array;
	vector<char> bit_count; // Number of used bits in each 256bits region
public:	
	BitMap(int num_bytes = 2048) : N(num_bytes * 8), bit_array(num_bytes / sizeof(int), 0)
	{
		bit_count(N / 256, 0);
	}
	
	void clear_bit(int pos)
	{
		assert(pos >= 0 && pos < N);
		assert(bit_count[pos >> 8]);
		--bit_count[pos >> 8];
		std::pair<int, int> tmp = get_array_pos(pos);
		bit_array[tmp.first] &= ~(1 << tmp.second);
	}
        int get_bit()
	{
		int chunk = 0;
		while (chunk < (N >> 8) && bit_count[chunk] == 255)
			++chunk;
		assert (chunk < (N >> 8));
                ++bit_count[chunk];
		int res = chunk << 8;
		while (read_bit(res) == 1)
			++res;
		std::pair<int, int> tmp = get_array_pos(res);
		bit_array[tmp.first] |= 1 << tmp.second;
                return res;
	}
private:
        int log2(int val) const
        {
		return 8 * sizeof(int) - cntlz(val) -  1;
	}
        std::pair<int, int> get_array_pos(int bitpos)
	{
                int offset        = 3 + log2(sizeof(int));
		int arr_pos    = bitpos >> offset;
                int arr_offset = bitpos & (( 1 << offset) - 1);
		return make_pair(arr_pos, arr_offset);
	}
        int read_bit(int pos)
        {
                std::pair<int, int> tmp = get_array_pos(pos);
		return bit_array[tmp.first] & (1 << tmp.second);
        }
};

Store bits in array of long ints, 16K / 64 = 256 elements are required.
On Intel CPUs we can use popcnt instruction for fast counting of number of "ones" in each dword.
To speed up get_bit() we could create 128 bytes array were each byte counts the number of bits that are set on each 128 bits interval. I believe we could further develop similar idea and create some counting interval tree, but this seems overkill for just 16K bits.