Бит вертится много бит в С

Question

Я хотел бы использовать двоичные флаги для представления математического набора в C, где «бит i установлен» означает «элемент i находится в наборе». Это удобно, потому что такие операции, как «объединение» и «пересечение», тривиально реализовать («|» и «&»). Тем не менее, я хочу, чтобы мой набор мог содержать более 32 предметов. Кроме того, я хочу, чтобы мой код работал как на 32-, так и на 64-битных машинах.

Есть ли какой-нибудь простой способ манипулирования битами из одного слова в C? Есть ли лучший способ подойти к этой задаче?

Answer 1

Да, вы просто определяете массив ваших 32-битных целых чисел.Затем вы манипулируете конкретным элементом массива.

Если указан битовый идентификатор от 0 до 255 включительно (например), это будет массив:

unsigned int bits[8];

Для того, чтобы найти какой элемент для работы:

unsigned int index = bitId >> 5; // turns 0..255 into 0..31

Чтобы получить маски для данного идентификатора бита:

unsigned int masks[] = {
    0x0001, 0x0002, 0x0004, 0x0008,
    0x0001, 0x0020, 0x0040, 0x0080,
    0x0100, 0x0200, 0x0400, 0x0800,
    0x1000, 0x2000, 0x4000, 0x8000
};
unsigned int mask = masks[bitId & 0x1f];

Если у вас есть тип uint32_t, доступный в вашемреализация, это, вероятно, самый безопасный путь.В противном случае существуют известные способы использования unsigned int с использованием CHAR_BIT и sizeof, чтобы фактически определить во время выполнения, насколько велик размер массива masks и какие значения следует использовать для обнаружения индекса массива и индекса битовой маски.

Например, этот фрагмент из моей библиотеки кода показывает, как я это сделал для символьной битовой маски:

static unsigned char bitmask[CHAR_BIT];
void bitsetInit (void) {
        unsigned char mask = 1;
        int i = 0;
        while (i < CHAR_BIT) {
                bitmask[i++] = mask;
                mask <<= 1;
        }
}

и использования:

bsp->bits[bitnum/CHAR_BIT] &= ~bitmask[bitnum%CHAR_BIT];
bsp->bits[bitnum/CHAR_BIT] |= bitmask[bitnum%CHAR_BIT];

для очистки иустановка битов соответственно.

Если вы хотите использовать unsigned int вместо unsigned char, вы просто рассчитаете количество битов для этого:

unsigned int UINT_BIT = CHAR_BIT * sizeof (unsigned int);

и используйте его там, где яиспользуется CHAR_BIT выше (массив mask может быть динамически выделен во время выполнения при необходимости).

Answer 2

Многоточечная библиотека Gnu обеспечивает целочисленную реализацию с очень хорошей оптимизацией для целых чисел произвольной точности, а также имеет наиболее полезную функциональность битового перемешивания. (ссылка)

В зависимости от конкретных операций, которые вам действительно нужно выполнить, могут существовать некоторые причудливые структуры данных, которые могут выполнять работу немного лучше.Например, есть очень умная структура Disjoint Sets , предназначенная для моделирования набора непересекающихся наборов, которая обладает поразительной асимптотической эффективностью по сравнению с тремя операциями, которые она поддерживает.

Answer 3

paxdiablo, похоже, дал вам правильный подход к решению этой проблемы так, как вы сказали, что хотите ее решить.

Есть ли лучший способ подойти к этой задаче?

Если у вас нет конкретной производительности или аппаратной причины для выполнения вашей работы на побитовом уровне, могут быть более эффективные способы представления набора. Например, связанный список или двоичное дерево, значения которого являются членами набора. Обе эти структуры могут иметь (эффективно) бесконечный размер, и их легко перебирать.

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

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

Answer 4

Вы можете использовать uint64_t из <stdint.h>.Кроме того, я боюсь, что вам не повезло в том, что касается & и |, и вам следует искать другой дизайн (например, структуры с соответствующими функциями для их обработки или сторонние библиотеки.).

Answer 5

Если вы действительно удовлетворены 32- и 64-битными типами, в современном C (он же C99) typedefs uint_least32_t и uint_least64_t гарантированно существуют в "stdint.h".В отличие от типов точной ширины uint32_t и uint64_t (которые являются необязательными) они могут соответствовать базовому типу, ширина которого шире, чем указывает число.

Если важна скорость, вы можететакже используйте uint_fast32_t и uint_fast64_t, которые также должны существовать.Они обменивают скорость на размер и должны использовать соответствующий базовый тип, который имеет «самую быструю» поддержку на целевой машине.Взрыв данных может быть существенным, хотя.Например, на моем 64-битном Ubuntu все эти «быстрые» типы являются 64-битными.

Если вы используете gcc, вы также получите __uint128_t на 64-битных машинах в качестве дополнительной услуги.