Подсчет бит в непрерывный фрагмент памяти

Граничные условия, они не получают уважения ...

Кажется, что все здесь концентрируются на поисковой таблице для подсчета битов. И это нормально, но я думаю, что еще важнее, отвечая на вопрос интервью, убедиться, что вы справляетесь с граничными условиями.

Справочная таблица - это просто оптимизация. Гораздо важнее получить правильный ответ , чем быстро его получить. Если бы это было мое интервью, сразу перейти к таблице поиска, даже не упомянув, что есть некоторые хитрые подробности обработки первых и последних битов, которые не находятся на полнобайтовых границах, было бы хуже, чем придумать решение, которое рассчитывало каждый бит громко, но правильно понял граничные условия.

Таким образом, я думаю, что решение Бхаскара в его вопросе, вероятно, превосходит большинство ответов, упомянутых здесь, - оно, кажется, обрабатывает граничные условия.

Вот решение, которое использует справочную таблицу и пытается по-прежнему обрабатывать границы (это только слегка проверено, поэтому я не буду утверждать, что это на 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) или старший значащий бит (msb). Другими словами, если начальный индекс был задан как 0, будет ли байт со значением 0x01 или байт со значением 0x80 иметь бит, установленный в этом индексе? Вроде того, как решить, рассматривают ли индексы порядок битов в байте как байты с прямым порядком байтов или с прямым порядком байтов.

На это нет «правильного» ответа - интервьюер должен будет указать, каким должно быть поведение. Я также отмечу, что мое примерное решение обрабатывает это противоположно коду примера OP (я шел по тому, как я интерпретировал диаграмму, при этом индексы также читались как «битовые числа»). Решение OP рассматривает битовый порядок как big-endian, моя функция обрабатывает их как little-endian. Так что, хотя оба обрабатывают частичные байты в звезде & amp; конец диапазона, они дадут разные ответы. Какой правильный ответ зависит от того, какова реальная спецификация для проблемы.

Версия @dimitri, вероятно, самая быстрая. Но трудно составить таблицу подсчета битов для всех 128 8-битных символов в интервью. Вы можете получить очень быструю версию с таблицей для 16 шестнадцатеричных чисел 0x0, 0x1, ..., 0xF, которую вы можете легко построить:

int countBits(void *ptr, int start, int end) {
    // start, end are byte indexes
    int hexCounts[16] =   {0, 1, 1, 2,   1, 2, 2, 3,
                           1, 2, 3, 3,   2, 3, 3, 4}; 
    unsigned char * pstart = (unsigned char *) ptr + start;
    unsigned char * pend = (unsigned char *) ptr + end;
    int count = 0;
    for (unsigned char * p = pstart; p <= pend; ++p) {
        unsigned char b = *p;
        count += hexCounts[b & 0x0F] + hexCounts[(b >> 4) & 0x0F];
    }
    return count;
}

РЕДАКТИРОВАТЬ: если start и end битовые индексы, тогда биты в первом и последнем байтах будут считаться первыми перед вызовом вышеуказанной функции:

int countBits2(void *ptr, int start, int end) {
    // start, end are bit indexes
    if (start > end) return 0;
    int count = 0;
    unsigned char* pstart = (unsigned char *) ptr + start/8; // first byte
    unsigned char* pend = (unsigned char *) ptr + end/8;     // last byte
    int istart = start % 8;                                  // index in first byte
    int iend = end % 8;                                      // index in last byte 
    unsigned char b = *pstart;                               // byte
    if (pstart == pend) {                                    // count in 1 byte only
        b = b << istart;
        for (int i = istart; i <= iend; ++i) {               // between istart, iend
            if (b & 0x80) ++count; 
            b = b << 1;
        }
    }
    else {                                                   // count in 2 bytes
        for (int i = istart; i < 8; ++i) {                   // from istart to 7
            if (b & 1) ++count; 
            b = b >> 1;
        }
        b = *pend;
        for (int i = 0; i <= iend; ++i) {                    // from 0 to iend
            if (b & 0x80) ++count; 
            b = b << 1;
        }
    }
    return count + countBits(ptr, start/8 + 1, end/8 - 1);
}