¿Cómo implementar un conjunto de bits en C?

6 minutos de lectura

avatar de usuario
David Robles

he estado usando el conjunto de bits class en Java y me gustaría hacer algo similar en C. Supongo que tendría que hacerlo manualmente como la mayoría de las cosas en C. ¿Cuál sería una forma eficiente de implementar?

byte bitset[]

quizás

bool bitset[]

?

  • ¿Eficiente en términos de memoria o CPU?

    – Roberto

    7 de diciembre de 2010 a las 1:09

  • @robert: Supongo que en términos de memoria en primer lugar. Se debe a la poca sobrecarga de procesamiento posible, pero a los serios gastos generales en caso de errores de caché.

    – ruso

    7 de diciembre de 2010 a las 1:23


  • @robert: ¿hay alguna diferencia? Si hay una gran cantidad de bits, el rendimiento estará limitado por errores de caché, por lo que empaquetar los bits lo más ajustado posible brindará el mejor rendimiento. Solo si hay muy pocos bits podría ser más eficiente usar un byte completo (o más) por bit.

    – R.. GitHub DEJA DE AYUDAR A ICE

    7 de diciembre de 2010 a las 4:05

avatar de usuario
mike axiak

CCAN tiene una implementación de conjunto de bits que puede usar: http://ccan.ozlabs.org/info/jbitset.html

Pero si termina implementándolo usted mismo (por ejemplo, si no le gustan las dependencias de ese paquete), debe usar una matriz de ints y usar el tamaño nativo de la arquitectura de la computadora:

#define WORD_BITS (8 * sizeof(unsigned int))

unsigned int * bitarray = (int *)calloc(size / 8 + 1, sizeof(unsigned int));

static inline void setIndex(unsigned int * bitarray, size_t idx) {
    bitarray[idx / WORD_BITS] |= (1 << (idx % WORD_BITS));
}

No use un tamaño específico (por ejemplo, con uint64 o uint32), deje que la computadora use lo que quiera usar y se adapte a eso usando sizeof.

  • Tal vez, pero también tal vez desee el tamaño más grande en el que pueda operar de manera eficiente. Si está escaneando a través de bits, esto puede ser eficiente. Por otra parte, la forma en que algunas CPU cargan cachés desde la memoria no importa el tamaño que elija. Pero por una tercera parte… tal vez solo tengas que experimentar y medir.

    – Presidente James K. Polk

    7 de diciembre de 2010 a las 1:21


  • Ciertamente experimente, pero en mi experiencia, usar el tamaño de palabra para dividir es generalmente más rápido. ¿No estoy seguro de entender tu primer punto?

    -Mike Axiak

    7 de diciembre de 2010 a las 1:25

  • sizeof está en bytes, no en bits. Necesitas multiplicar por 8 (o más generalmente CHAR_BIT en algunas de esas expresiones.

    – R.. GitHub DEJA DE AYUDAR A ICE

    7 de diciembre de 2010 a las 4:06

  • ¿No es el primer parámetro para calloc ¿incorrecto? Creo que debería ser (size + WORD_BITS - 1) / WORD_BITS porque ese es el número de entradas sin firmar que se requiere.

    –Björn Lindqvist

    14/11/2016 a las 21:38


  • también (idx % WORD_BITS) se puede simplificar a (idx & (WORD_BITS - 1)) pero un buen compilador tal vez haga esa optimización automáticamente.

    –Björn Lindqvist

    14/11/2016 a las 21:51

Nadie mencionó lo que recomiendan las preguntas frecuentes de C, que son un montón de macros antiguas:

#include <limits.h>     /* for CHAR_BIT */

#define BITMASK(b) (1 << ((b) % CHAR_BIT))
#define BITSLOT(b) ((b) / CHAR_BIT)
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
#define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))
#define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)

(vía http://c-faq.com/misc/bitsets.html)

  • Pero esto no siempre evita los efectos secundarios de las macros, por ejemplo, intente: int i = 0, bits; BITSET(bits, i++)

    – Lucas Smith

    6 de febrero de 2015 a las 0:22


  • @LukeSmith Tienes razón, pero parece bastante usado. Parece que la forma correcta de implementar una macro es hacer que la persona que llama entienda que es una macro, y así poner la responsabilidad en la persona que llama. (Cualquiera a quien no le guste eso, puede envolverlo en una función en línea)

    – Opux

    25 de enero de 2016 a las 17:28

Bueno, conjunto de bits de bytes[] parece un poco engañoso, ¿no?

Use campos de bits en una estructura y luego puede mantener una colección de estos tipos (o utilícelos de otra manera como mejor le parezca)

struct packed_struct {
  unsigned int b1:1;
  unsigned int b2:1;
  unsigned int b3:1;
  unsigned int b4:1;
  /* etc. */
} packed;

  • Esta no es una mala idea para una pequeña colección de banderas, pero si usa un conjunto de bits, normalmente querrá que sea indexable por un número entero. Véase, por ejemplo, la clase de conjunto de bits de Java.

    – Presidente James K. Polk

    7 de diciembre de 2010 a las 1:14

  • Sí, pensé en eso más tarde y luego noté que Mike publicó algo así.

    – Ed S.

    7 de diciembre de 2010 a las 1:20

  • Uso contraproducente de campos de bits y uso de índices en nombres de variables.

    – R.. GitHub DEJA DE AYUDAR A ICE

    7 de diciembre de 2010 a las 4:06


recomiendo mi Biblioteca BITSCAN C++ (La versión 1.0 acaba de ser lanzada). BITSCAN está específicamente orientado para operaciones rápidas de escaneo de bits. Lo he usado para implementar problemas combinatorios NP-Hard que involucran gráficos simples no dirigidos, como la camarilla máxima (ver BBMC algoritmo, para un solucionador exacto líder).

Una comparación entre BITSCAN y las soluciones estándar STL conjunto de bits y IMPULSAR conjunto_de_bits_dinámico está disponible aquí:
http://blog.biicode.com/bitscan-efficiency-at-glance/

puedes dar mi PackedArray codifique un intento con un bitsPerItem de 1.

Implementa un contenedor de acceso aleatorio donde los elementos se empaquetan a nivel de bits. En otras palabras, actúa como si pudieras manipular un ejemplo. uint9_t o uint17_t formación:

PackedArray principle:
  . compact storage of <= 32 bits items
  . items are tightly packed into a buffer of uint32_t integers

PackedArray requirements:
  . you must know in advance how many bits are needed to hold a single item
  . you must know in advance how many items you want to store
  . when packing, behavior is undefined if items have more than bitsPerItem bits

PackedArray general in memory representation:
  |-------------------------------------------------- - - -
  |       b0       |       b1       |       b2       |
  |-------------------------------------------------- - - -
  | i0 | i1 | i2 | i3 | i4 | i5 | i6 | i7 | i8 | i9 |
  |-------------------------------------------------- - - -

  . items are tightly packed together
  . several items end up inside the same buffer cell, e.g. i0, i1, i2
  . some items span two buffer cells, e.g. i3, i6

avatar de usuario
Presidente James K. Polk

Como de costumbre, primero debe decidir qué tipo de operaciones necesita realizar en su conjunto de bits. ¿Quizás algún subconjunto de lo que define Java? Después de eso, puede decidir la mejor manera de implementarlo. Sin duda, puede consultar la fuente de BitSet.java en OpenJDK para obtener ideas.

avatar de usuario
EvilTeach

Conviértalo en una matriz de int 64 sin firmar.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad