C битовый массив макросов, кто-нибудь может объяснить мне, как они работают?

Я пытаюсь внедрить сито из эратостенов в школьный проект, и я решил сделать это, используя битовые массивы. Когда я искал материалы, я наткнулся на эти 3 макроса, они работают безупречно, но я не могу их по-настоящему прочитать (понять).

#define ISBITSET(x,i) ((x[i>>3] & (1<<(i&7)))!=0)
#define SETBIT(x,i) x[i>>3]|=(1<<(i&7));
#define CLEARBIT(x,i) x[i>>3]&=(1<<(i&7))^0xFF;

Не могли бы вы объяснить мне хотя бы один из них подробно, у меня есть базовые знания о побитовых операциях в C (в основном я знаю, что они "существуют").

Будет ли это работать на другой архитектуре с использованием другого порядка байтов? Заранее спасибо.

Источник

3 ответа

Решение

Во-первых, эти макросы злобно предполагают, что CHAR_BIT == 8, а также i >> 3 на самом деле i / 8, (Так что на самом деле этот код должен сказать i / CHAR_BIT.) Это первое выражение вычисляет байт, который содержит желаемый бит и, таким образом, является индексом массива в вашем массиве. x (который должен быть массивом unsigned char!).

Теперь, когда мы выбрали правильный байт, а именно x[i >> 3] (или же x[i / CHAR_BIT] в вашем собственном, лучшем коде), мы должны сделать немного Снова, i & 7 действительно хочет быть i % CHAR_BIT, и он извлекает только остаток от вашего количества битов, который дает вам смещение в байте.

Пример. Запрос 44-го бита с i = 43и предполагая CHAR_BIT = 8, i / CHAR_BIT 5, поэтому мы находимся в шестом байте, и i % CHAR_BIT равно 3, поэтому мы смотрим на четвертый бит шестого байта.

Само по себе суета делает обычные вещи; например, тестирование для данного бита выполняет побитовое И с соответствующей битовой комбинацией (а именно 1 << k для kбит); установка бита использует побитовое ИЛИ, а обнуление требует чего-то более сложного (подумайте об этом!).

Источник

xэто массив символов. i это индекс битов. так как каждый char 8 бит, последние 3 бита i определите бит в символе, а остальные биты определяют символ в массиве.

i>>3 сдвиньте на 3 бита вправо, так что вы получите часть, которая говорит вам, какой символ, так x[i>>3] символ, содержащий бит, проиндексированныйi,

i&7 последние 3 бита i (поскольку 710==1112), так что это индекс бита в символе. 1<<(i&7) это символ (на самом деле это int, но в этом контексте вы можете игнорировать разницу), который имеет бит, проиндексированный i вкл, а остальные биты выключены. (маска бита)

char&mask это общий способ проверить, включен ли бит.

char|=mask это обычный способ включить немного.

char&=~mask это обычный способ выключить бит, и если mask это символ, то ~mask==mask^0xFF,

Я не думаю, что эти макросы зависят от endiannes. (если вы получили x путем преобразования int[] в *charэто другая история)

Источник 
#define ISBITSET(x,i) (((x)[(i) / CHAR_BIT] & (1u << ((i) % CHAR_BIT))) != 0)
#define SETBIT(x,i) (x)[(i) / CHAR_BIT] |= (1u << ((i) % CHAR_BIT);
#define CLEARBIT(x,i) (x)[(i) / CHAR_BIT] &= ~(1u << ((i) % CHAR_BIT))
  • Всегда ставьте скобки вокруг аргументов макроса
  • всегда предпочитайте беззнаковые типы для битовых операций
  • (1u << CHAR_BIT) - 256 для 8-битных платформ
  • был exra ; после последнего макроса
Источник
Другие вопросы по тегам