Бит-подсчет в смежном фрагменте памяти

Ответ 1

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

что-то вроде этого:

int bit_table[256] = {0, 1, 1, 2, 1, ...};
char* p = ptr + start;
int count = 0;
for (p; p != ptr + end; p++)
    count += bit_table[*(unsigned char*)p];

Ответ 2

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

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

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

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

Здесь решение, которое использует таблицу поиска и пытается все еще обрабатывать границы (это только слегка проверено, поэтому я не буду утверждать, что он на 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 иметь бит, установленный в этом индексе? Подобно тому, как определить, учитывают ли индексы битовый порядок в байте как big-endian или little-endian.

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

Ответ 3

Вы можете найти эту страницу, она содержит несколько альтернативных решений для вашей проблемы.

Ответ 4

Версия @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;
}

EDIT: если 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);
}

Ответ 5

Существует множество способов решения проблемы. Это - хорошая публикация, которая сравнивает производительность наиболее распространенных опций.

Ответ 6

Отказ от ответственности: не было сделано попыток скомпилировать следующий код.

/*
 * Table counting the number of set bits in a byte.
 * The byte is the index to the table.
 */
uint8_t  table[256] = {...};

/***************************************************************************
 *
 * countBits - count the number of set bits in a range
 *
 * The most significant bit in the byte is considered to be bit 0.
 *
 * RETURNS: 0 on success, -1 on failure
 */
int countBits (
    uint8_t *  buffer,
    int        startBit,  /* starting bit */
    int        endBit,    /* End-bit (inlcusive) */
    unsigned * pTotal     /* Output: number of consecutively set bits */
    ) {
    int      numBits;     /* number of bits left to check */
    int      mask;        /* mask to apply to byte from <buffer> */
    int      bits;        /* # of bits to end of byte */
    unsigned count = 0;   /* total number of bits set */
    uint8_t  value;       /* value read from the buffer */

    /* Return -1 if parameters fail sanity check (skipped) */

    numBits   = (endBit - startBit) + 1;

    index  = startBit >> 3;
    bits   = 8 - (startBit & 7);
    mask   = (1 << bits) - 1;

    value = buffer[index] & mask;  /* mask-out any bits preceding <startBit> */
    numBits -= bits;

    while (numBits > 0) {          /* Note: if <startBit> and <endBit> are in */
        count += table[value];     /* same byte, this loop gets skipped. */
        index++;
        value = buffer[index];
        numBits -= 8;
    }

    if (numBits < 0) {             /* mask-out any bits following <endBit> */
        bits   = 8 - (endBit & 7);
        mask   = 0xff << bits;
        value &= mask;
    }

    count += table[value];

    *pTotal = count;
    return 0;
}

Изменить: обновлен заголовок функции.

Ответ 7

В зависимости от отрасли, в которую вы применили, поисковые таблицы могут быть не приемлемым средством оптимизации, в то время как оптимизация платформы/компилятора. Зная, что большинство компиляторов и наборов инструкций процессора имеют команду подсчета pop, я бы пошел на это. Это простота против компромисса с производительностью, потому что сейчас я все еще повторяю список символов.

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

int countSetBits(void *ptr, int start, int end )
{
    assert(start < end);

    unsigned char *s = ((unsigned char*)ptr + start);
    unsigned char *e = ((unsigned char*)ptr + end);

    int r = 0;

    while(s != e)
    {
        // __builtin_clz is not defined for 0 input.
        if(*s) r += 32 - __builtin_clz(*s);
        s++;
    }

    return r;
}