Программирование на языке Pascal




Представление множеств битовыми массивами - часть 2


Удаление элемента из множества придется записать более сложным образом:

set_arr[kmp]:= set_arr[kmp]and not(1 shl(bit-1));

Операция not превратит все 0 в 1 и наоборот, следовательно, теперь в качестве второго операнда для побитового and будет фигурировать число, состоящее из семи единиц и нуля на месте с номером bit. Единицы сохранят любые значения тех битов, которые должны остаться без изменения, и лишь 0 "уничтожит" значение единственного нужного бита.

  • Пересечение множеств реализуется теперь при помощи операции "побитовое и":

    for i:= 0 to N-1 do set_res[i]:= set1[i] and set2[i];

  • Объединение множеств реализуется при помощи операции "побитовое или":

    for i:= 0 to N-1 do set_res[i]:= set1[i] or set2[i];

  • Разность двух множеств может быть построена так:

    for i:= 0 to N-1 do set_res[i]:= (set1[i] or set2[i]) and not set2[i];

    Поясним, что здесь мы вначале прибавляем содержимое второго множества к первому, чтобы затем быть полностью уверенными в правомерности операции вычитания.

  • Проверка двух множеств на равенство по-прежнему не требует особых пояснений:

    equal:= true; for i:=0 to N-1 do if set1[i]<> set2[i] then begin equal:= false; break end;

  • Проверка двух множеств на включение (set1<set2) будет производиться по схеме: "Если (A\B)

    B=A, то B
    A ", доказательство которой настолько очевидно, что мы не станем на нем задерживаться:

    subset:= true; for i:= 0 to N-1 do if((set1[i] or set2[i])and not set2[i]) or set2[i] <> set1[i] then begin subset:= false; break end;

  • Замечание. Если предстоит многократно выполнять действия с элементами битовых массивов, то используемые для этого значения "единиц" удобнее всего сразу задать в специальном массиве:

    {ed: array[1..8] of byte;} ed[1]:=1; for k:= 2 to 8 do ed[k]:= ed[k-1] shl 1;

    И далее вместо громоздкой конструкции 1 shl(bit-1) можно использовать просто ed[bit].




    Содержание  Назад  Вперед