Битовый массив.Delphi

[nvse]

Недавно на лекции услышал впервые этот термин.И кое-что я не могу понять.
Я знаю,что в Delphi нет такой готовой стркутры данных,максимум есть array of byte.И у меня вопрос а как его тогда создать?
Например:есть array [1..3] of byte .Как мне из него сделать битовый массив из 24 элементов и к примеру занести единицы в 3-ий и 17-ий бит?
Заранее спасибо.В интернете искал,но ничего похожего не нашёл.

@темы: Pascal, Delphi

Comments

[O]

Вообще, это всё делается битовыми операциями. Т.е. чтобы установить i'й бит, надо сделать так:

byteIdx:=i shr 3; //получаем индекс байта в массиве
bitIdx:=i and 7; // получаем индекс бита в этом байте
mask:=1 shl bitIdx; // получаем маску
b:=bArr[byteIdx]; //получаем интересующий нас байт
b:= b or mask; //устанавливаем нужный бит
bArr[byteIdx]:=b; //загоняем модифицированный байт обратно в массив

Здесь я считаю, что bArr индексируется с нуля (привык я так), если это не так, надо просто к byteIdx прибавить номер первого элемента. Т.е. для array [1..3] of byte это будет byteIdx:=(i shr 3) +1;

Для того, чтобы получить значение i'го бита, делаем так:

byteIdx:=i shr 3; //получаем индекс байта в массиве
bitIdx:=i and 7; // получаем индекс бита в этом байте
b:=bArr[byteIdx]; //получаем интересующий нас байт
b:= b shr bitIdx; //сдвигаем побитово значение b так, чтобы интересующий нас бит был первым
bitVal:=b and 1; // очищаем все неинтересные нам биты

[A r i s e n]

Не знаю, как конкретно в Дельфи, но в Паскале к понятию битового массива ближе всего множество. То есть set of 1..24 делаешь, и оно в памяти машины представляется как битовый вектор из 24 элементов (1 - элемент входит в множество, 0 - не входит). Соответственно, простым плюсом (данное множество +3) выставляешь в единичку 3-й бит, +17 - соответственно 17-й. Обнуляешь минусом.

[nvse]

Эх...наверное я идиот,но я ничего не понимаю.Вот например я хочу занести 1 в 13-ый по счёту бит а потом считать егоего номер.У меня есть массив из 2-ух чисел типа byte:
A:array[0..1] of byte .Для начала там будет два нуля.Или {0000 0000;0000 0000}.Мне нужно сделать {0000 0000;0000 1000} и потом считать номер где находится эта единица.
Тогда byteIdx:=13 shr 3 = 1101 shr 3 = 0001 = 1 .BitIdx:=1101 and 0111 = 0101 = 5.Вроде пока всё верно.Но вот дальше возникают проблемы.mask := 1 shl 5 =
0001 shl 5 = 0000 ? или 00001 shl 5 = 10000 ? Интуиция всё таки подсказывает,что mask = 1000 .Дальше b:= Arr[1]= 0. b:= 0000 or 1000 = 1000(0000 1000).Тогда
Arr[1]:={0000 1000}.То есть п.1 вроде бы ясно,но остался вопрос насчёт маски,которую я не могу понять и для чего она вообще нужна.
Теперь нужно считать номер этой единицы.byteIdx:=1 ; bitIdx:=5 .b:=Arr[1]=8 .b:= 1000 0000(бит стал первым) .bitval:=1000 0000 and 0000 0001 = 0.
Ещё один вопрос:а зачем нам сдвигать число,чтобы бит становился первым?Что это даёт?И как можно получить из этого всего искомое число 13?И мне к сожалению не понятно
какая переменная содержит значение i-го бита

[Crazy Wizard]

> {0000 0000;0000 1000}
-- это 4 бит, а не 13.

> И как можно получить из этого всего искомое число 13?
Никак, ты же записываешь "1" или "0", только тру или фолс, для записи чисел надо использовать обычный массив чисел

[O]

nvse Попытаюсь проиллюстрировать. Пусть надо установить 13'й бит в массиве A: array[0..1] of byte c установленными битами 0,1,5,6,9,15.

 1111 1198  7654 3210   - индексы битов в битовом массиве
 5432 10                /

{1000 0010; 0110 0011}  - массив A с уже какими-то установленными битами

     1          0       - индексы байт в массиве A


 0000 1101              = 13
 0000 0001              = 13 shr 3 = 13 div 8 = 1 => byteIdx - индекс байта, в котором будет интересующий нас бит
 0000 0101              = 13 and 7 = 13 mod 8 = 5 => bitIdx - индекс интересующего нас бита в интересующем нас байте

 0010 0000              = 1 shl bitIdx = 1 shl 5 => mask - маска

 1000 0010		= A[byteIdx] = A[1]
 0010 0000              = mask
 1010 0010              = A[1] and mask

{1010 0010; 0110 0011}  - массив A c установленным 13'м битом, что и требовалось.

Далее. В данном примере в массиве получаются установленными биты 0,1,5,6,9,15 и 13 (который мы только что установили). Просто число 13, равно как и числа 0,1,5,6,9,15 просто так получить не выйдет. Однако, можно проверить, установлен ли какой-то конкретный бит - что в общем-то и требуется при практическом применении битовых массивов.
Проверим, установлен ли бит, скажем, 15 в массиве A.

 1111 1198  7654 3210   - индексы битов в битовом массиве
 5432 10                /

{1010 0010; 0110 0011}  - массив A 

     1          0       - индексы байт в массиве A


 0000 1111              = 15
 0000 0001              = 15 shr 3 = 15 div 8 = 1 => byteIdx - индекс байта, в котором будет интересующий нас бит
 0000 0111              = 15 and 7 = 15 mod 8 = 7 => bitIdx - индекс интересующего нас бита в интересующем нас байте

 1000 0000              = 1 shl bitIdx = 1 shl 7 => mask - маска

 1010 0010		= A[byteIdx] = A[1]
 1000 0000              = mask
 1000 0000              = A[1] and mask

 0000 0001              = (A[1] and mask) shr bitIdx

Получили 1 - т.е. значение 15'го бита. Хотя в принципе, ты прав, это не обязательно. Сравнение с нулём значения A[byteIdx ] and mask тоже может сказать, установлен интересующий нас бит или нет.

Да, должен покаяться, с дельфями я уже лет шесть дела не имел и расписал подход, который больше в ходу в среде программистов на си-подобных языках. Как верно было подмечено A r i s e n, есть такой тип в дельфях - Set. Это по сути - битовый массив в 32 байта (т.е. 256 бит) максимум, все битовые операции с которым компилятор делфи прописывает за программиста. Для большинства практических задач этого должно хватать с лихвой. Мною же озвученный подход необходим, если приходится оперировать большими, нежели 256 бит, массивами (с учётом ограничений делфи на длину массива - до полугигабита). Ну, или если хочется "чувствовать память" =)

[nvse]

O спасибо,всё наглядно и главное понятно.Единственное,вы наверное описались в строчке

1010 0010 = A[1] and mask

Там ведь A[1] or mask .А так всё понятно.Про set: я бы рад,но мне в задаче нужно создать битовый массив из 7*10^7 чисел)Ещё раз спасибо

[O]

nvse Не за что =)
Да, естественно, описался, спасибо, что подметили. И что забавно - я ведь когда писал, заметил эту описку, и даже вроде бы исправил... =)