Граничные условия, они не получают уважения ...
Кажется, что все здесь концентрируются на поисковой таблице для подсчета битов. И это нормально, но я думаю, что еще важнее при ответе на вопрос интервью убедиться, что вы справляетесь с граничными условиями.
Таблица поиска - это просто оптимизация. Гораздо важнее правильно ответить на вопрос , чем быстро получить ответ. Если бы это было мое интервью, сразу перейти к таблице поиска, даже не упомянув, что есть некоторые хитрые подробности обработки первых и последних битов, которые не находятся на полнобайтовых границах, было бы хуже, чем придумать решение, которое рассчитывало каждый бит громко, но правильно понял граничные условия.
Так что я думаю, что решение Бхаскара в его вопросе, вероятно, превосходит большинство ответов, упомянутых здесь, - похоже, оно справляется с граничными условиями.
Вот решение, которое использует справочную таблицу и пытается по-прежнему обрабатывать границы (это только слегка проверено, поэтому я не буду утверждать, что это на 100% правильно). Это также уродливее, чем хотелось бы, но уже поздно:
typedef unsigned char uint8_t;
static
size_t bits_in_byte( uint8_t val)
{
static int const half_byte[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
int result1 = half_byte[val & 0x0f];
int result2 = half_byte[(val >> 4) & 0x0f];
return result1 + result2;
}
int countSetBits( void* ptr, int start, int end)
{
uint8_t* first;
uint8_t* last;
int bits_first;
int bits_last;
uint8_t mask_first;
uint8_t mask_last;
size_t count = 0;
// get bits from the first byte
first = ((uint8_t*) ptr) + (start / 8);
bits_first = 8 - start % 8;
mask_first = (1 << bits_first) - 1;
mask_first = mask_first << (8 - bits_first);
// get bits from last byte
last = ((uint8_t*) ptr) + (end / 8);
bits_last = 1 + (end % 8);
mask_last = (1 << bits_last) - 1;
if (first == last) {
// we only have a range of bits in the first byte
count = bits_in_byte( (*first) & mask_first & mask_last);
}
else {
// handle the bits from the first and last bytes specially
count += bits_in_byte((*first) & mask_first);
count += bits_in_byte((*last) & mask_last);
// now we've collected the odds and ends from the start and end of the bit range
// handle the full bytes in the interior of the range
for (first = first+1; first != last; ++first) {
count += bits_in_byte(*first);
}
}
return count;
}
Обратите внимание, что деталь, которая должна быть проработана как часть интервью, заключается в том, индексируются ли биты внутри байта, начиная с младшего значащего бита (lsb) или старшего значащего бита (мсб). Другими словами, если начальный индекс был задан как 0, будет ли байт со значением 0x01 или байт со значением 0x80 иметь бит, установленный в этом индексе? Вроде того, как решить, считают ли индексы порядок следования битов в байте как байты с прямым порядком байтов или с прямым порядком байтов.
Нет «правильного» ответа на это - интервьюер должен был бы указать, каким должно быть поведение. Я также отмечу, что мое примерное решение обрабатывает это противоположно коду примера OP (я шел по тому, как я интерпретировал диаграмму, при этом индексы также читались как «битовые числа»). Решение OP рассматривает битовый порядок как big-endian, моя функция обрабатывает их как little-endian. Таким образом, хотя оба обрабатывают частичные байты в начале и в конце диапазона, они дают разные ответы. Какой правильный ответ зависит от того, какова реальная спецификация для проблемы.