c++ - simple - paginas y marcos sistemas operativos

Conteo de bits en un trozo de memoria contigua

Question

Me preguntaron en una entrevista la siguiente pregunta.

int countSetBits(void *ptr, int start, int end); 

Sinopsis: Supongamos que ptr apunta a una gran parte de la memoria. Al ver esta memoria como una secuencia contigua de bits, el start y el end son posiciones de bits. Supongamos que el start y el end tienen valores adecuados y ptr está apuntando a un chunck inicializado de la memoria.

Pregunta: Escriba un código C para contar el número de bits establecido de start a end [inclusive] y devuelva el conteo.

Solo para que quede más claro.

 ptr---->+-------------------------------+
         | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
         +-------------------------------+
         | 8 | 9 |                   |15 |
         +-------------------------------+
         |                               |
         +-------------------------------+
              ...
              ...
         +-------------------------------+
         |               | S |           |
         +-------------------------------+
              ...
              ...
         +-------------------------------+
         |    | E |                      |
         +-------------------------------+
              ...
              ...

Mi solución:

int countSetBits(void *ptr, int start, int end )
{
    int count = 0, idx; 

    char *ch; 

    for (idx = start; idx <= end; idx++) 
    {     ch = ptr + (idx/8); 

          if((128 >> (idx%8)) & (*ch)) 
          {
                   count++; 
          }
    }

    return count; 
}

Di un código muy largo y algo ineficiente durante la entrevista. Trabajé en ello más tarde y se me ocurrió la solución anterior.

Estoy muy seguro de que la comunidad SO puede proporcionar una solución más elegante. Solo tengo curiosidad por ver su respuesta.

PS: El código anterior no está compilado. Es más como un pseudo código y puede contener errores.

Answer 1

Condiciones de frontera, no reciben ningún respeto ...

Todo el mundo aquí parece concentrarse en la tabla de búsqueda para contar los bits. Y eso está bien, pero creo que aún más importante al responder una pregunta de una entrevista es asegurarse de que usted maneje las condiciones de los límites.

La tabla de consulta es solo una optimización. Es mucho más importante obtener la respuesta correcta que obtenerla rápidamente. Si esta fuera mi entrevista, ir directamente a la tabla de búsqueda sin siquiera mencionar que hay algunos detalles difíciles sobre el manejo de los primeros y los últimos pocos bits que no están en los límites de bytes completos sería peor que encontrar una solución que contara Cada bit fue laborioso, pero acertó las condiciones de los límites.

Así que creo que la solución de Bhaskar en su pregunta es probablemente superior a la mayoría de las respuestas que se mencionan aquí: parece manejar las condiciones de los límites.

Aquí hay una solución que usa una tabla de búsqueda y trata de controlar los límites (solo está ligeramente comprobada, por lo que no afirmaré que sea 100% correcta). También es más feo de lo que me gustaría, pero es tarde:

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;
}

Tenga en cuenta que un detalle que tendría que resolverse como parte de la entrevista es si los bits dentro de un byte se indexan empezando por el bit menos significativo (lsb) o el bit más significativo (msb). En otras palabras, si el índice de inicio se especificara como 0, ¿un byte con el valor 0x01 o un byte con el valor 0x80 tienen el bit establecido en ese índice? Algo así como decidir si los índices consideran el orden de los bits dentro de un byte como big-endian o little-endian.

No hay una respuesta ''correcta'' para esto: el entrevistador tendría que especificar cuál debería ser el comportamiento. También notaré que mi solución de ejemplo maneja esto de manera opuesta al código de ejemplo del OP (estaba siguiendo la forma en que interpreté el diagrama, y ​​los índices también se leen como ''números de bits''). La solución de los OP considera el orden de bits como big-endian, mi función los trata como little-endian. Entonces, aunque ambos manejan bytes parciales en la estrella y el final del rango, darán respuestas diferentes. Cuál es la respuesta correcta depende de cuál es la especificación real del problema.

Answer 2

Dependiendo de la industria en la que se inscribió, las tablas de búsqueda podrían no ser un medio aceptable de optimización, mientras que las optimizaciones específicas de la plataforma / compilador sí lo son. Sabiendo que la mayoría de los compiladores y los conjuntos de instrucciones de la CPU tienen una instrucción de recuento pop, me gustaría ir por esto. Sin embargo, es una compensación entre la simplicidad y el rendimiento porque en este momento todavía estoy iterando sobre una lista de caracteres.

También tenga en cuenta que, a diferencia de la mayoría de las respuestas, asumo que el inicio y el final son compensaciones de bytes porque no se especifica en la pregunta que no lo son y es el valor predeterminado en la mayoría de los casos.

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;
}

Answer 3

Descargo de responsabilidad: no se ha hecho ningún intento de compilar el siguiente código.

/*
 * 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;
}

Edición: encabezado de función actualizado.

Answer 4

Hay muchas maneras de resolver el problema. This es una buena publicación que compara el rendimiento de las opciones más comunes.

Answer 5

La forma más rápida y eficiente en mi opinión es utilizar una tabla de 256 entradas, donde cada elemento representa la cantidad de bits en el índice. El índice es un byte siguiente de la ubicación de memoria.

algo como esto:

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];

Answer 6

La versión de @dimitri es probablemente la más rápida. Pero es difícil construir la tabla de conteos de bits para los 128 caracteres de 8 bits en una entrevista. Puedes obtener una versión muy rápida con una tabla para 16 números hexadecimales 0x0, 0x1, ..., 0xF, que puedes construir fácilmente:

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;
}

EDITAR: Si el start y el end son índices de bits, los bits en el primer y último byte se contarán primero antes de llamar a la función anterior:

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);
}

Answer 7

Puede encontrar esta página interesante, contiene varias soluciones alternativas para su problema.

Answer 8

Un excelente estudio reciente que compara varias de las técnicas más modernas para contar el número de bits ''set'' (valor 1) en un rango de memoria ( también conocido como peso de Hamming , cardinalidad de bits , suma lateral , conteo de población o popcnt , etc. ) puede se encuentra en Wojciech, Kurz y Lemire (2017), conteos de población más rápidos utilizando las instrucciones AVX2 ¹

La siguiente es una adaptación C # completa, probada y totalmente funcional del algoritmo "Harley-Seal" de ese documento, que los autores encontraron como el método más rápido que utiliza operaciones bitwise de propósito general (es decir, eso no es así). requiere hardware especial).

1. Puntos de entrada de matriz gestionados
(opcional) Proporciona acceso al conteo de bits optimizado por bloques para la matriz administrada ulong[] .

/// <summary> Returns the total number of 1-valued bits in the array </summary>
[DebuggerStepThrough]
public static int OnesCount(ulong[] rg) => OnesCount(rg, 0, rg.Length);

/// <summary> Finds the total number of ''1'' bits in an array or its subset </summary>
/// <param name="rg"> Array of ulong values to scan </param>
/// <param name="index"> Starting index in the array </param>
/// <param name="count"> Number of ulong values to examine, starting at ''i'' </param>
public static int OnesCount(ulong[] rg, int index, int count)
{
    if ((index | count) < 0 || index > rg.Length - count)
        throw new ArgumentException();

    fixed (ulong* p = &rg[index])
        return OnesCount(p, count);
}

2. API escalar
Utilizado por el contador optimizado de bloque para agregar resultados del sumador carry-save, y también para terminar cualquier resto para tamaños de bloque no divisibles por el tamaño de trozo optimizado de 16 x 8 bytes / ulong = 128 bytes. Adecuado para uso general también.

/// <summary> Finds the Hamming Weight or ones-count of a ulong value </summary>
/// <returns> The number of 1-bits that are set in ''x'' </returns>
public static int OnesCount(ulong x)
{
    x -= (x >> 1) & 0x5555555555555555;
    x = ((x >> 2) & 0x3333333333333333) + (x & 0x3333333333333333);
    return (int)((((x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F) * 0x0101010101010101) >> 56);
}

3. "Harley-Seal" contador de 1 bit-bit optimizado en bloque
Procesa bloques de 128 bytes a la vez, es decir, 16 valores de ulong por bloque. Utiliza el sumador carry-save (que se muestra a continuación) para agregar bits simples a través de ulong s adyacentes, y agrega los totales hacia arriba como potencias de dos.

/// <summary> Count the number of ''set'' (1-valued) bits in a range of memory. </summary>
/// <param name="p"> Pointer to an array of 64-bit ulong values to scan </param>
/// <param name="c"> Size of the memory block as a count of 64-bit ulongs </param>
/// <returns> The total number of 1-bits </returns>
public static int OnesCount(ulong* p, int c)
{
    ulong z, y, x, w;
    int c = 0;

    for (w = x = y = z = 0UL; cq >= 16; cq -= 16)
        c += OnesCount(CSA(ref w,
                            CSA(ref x,
                                CSA(ref y,
                                    CSA(ref z, *p++, *p++),
                                    CSA(ref z, *p++, *p++)),
                                CSA(ref y,
                                    CSA(ref z, *p++, *p++),
                                    CSA(ref z, *p++, *p++))),
                            CSA(ref x,
                                CSA(ref y,
                                    CSA(ref z, *p++, *p++),
                                    CSA(ref z, *p++, *p++)),
                                CSA(ref y,
                                    CSA(ref z, *p++, *p++),
                                    CSA(ref z, *p++, *p++)))));

    c <<= 4;
    c += (OnesCount(w) << 3) + (OnesCount(x) << 2) + (OnesCount(y) << 1) + OnesCount(z);

    while (--cq >= 0)
        c += OnesCount(*p++);

    return c;
}

4. Adicionar-guardar (CSA)

/// <summary> carry-save adder </summary> [MethodImpl(MethodImplOptions.AggressiveInlining)] static ulong CSA(ref ulong a, ulong b, ulong c) { ulong v = a & b | (a ^ b) & c; a ^= b ^ c; return v; } Observaciones

Debido a que el enfoque que se muestra aquí cuenta el número total de bits de 1 bit al proceder con trozos de 128 bytes a la vez, solo se vuelve óptimo con tamaños de bloque de memoria más grandes. Por ejemplo, es probable que al menos un poco (pequeño) múltiplo de ese tamaño de trozo de dieciséis palabras (16 ulong ). Para contar 1 bits en rangos de memoria más pequeños, este código funcionará correctamente, pero superará drásticamente los métodos más ingenuos. Vea el documento para más detalles.

En el documento, este diagrama resume cómo funciona el sumador de la acción de guardar :

1

Referencias

[1.] Muła, Wojciech, Nathan Kurz y Daniel Lemire. "Recuentos de población más rápidos utilizando instrucciones AVX2". The Computer Journal 61, no. 1 (2017): 111-120.