Часто встречается множество булевых параметров, которые нужно хранить в базе. Что-то существует или не существует. Что-то true или false. И когда таких параметров несколько десятков – сложно воспринимать базу. Для этого, как я понял, существуют битовые операции и фильтр Блума. Суть в том, что мы храним данные в виде, скажем 00100000, где 5-й выставленный бит отвечает за что-то в логике программы, ну, скажем, за то, адаптивный это тест или нет. Таким образом, можно вместо 8 полей в базе прийти к 1 полю, которое будет содержать в себе 8 boolean полей. Этакая экономия сил, минус которой – потеря читабельности. Если проект огромный, то, конечно, это нормальный ход. Но где-то нужно хранить расшифровку, ключ того, какой бит отвечает за тот или иной параметр.
Что делаем дальше?
Элементарные битовые операции
Освежим в памяти работу с битовыми операциями, написав небольшую программку. Как известно, над byte, shortint, word, integer, longint возможны побитовые операции. Для простоты, будем работать с 8 битами, то есть с байтом. Как в Delphi узнать сколько байтов и битов занимает переменная?
SizeOf(byte) =1, это 8 бит.
SizeOf(integer) =4, это 4*8 бит=32 бита.
На калькуляторе программиста будем видеть, соответственно для 32 разрядов, например…
Будем выставлять 5 бит, снимать его, переключать и др.
Итак, пусть у нас есть переменная типа Byte. В ней содержится 8 бит как мы знаем из школы)
|
1 |
a: byte; |
Как выставить и снять бит (через степени двойки)?
|
1 |
a := (a or 32); // 2^5 Выставили |
|
1 |
a := ( a and (255-32) ); // 2^5=32 Сняли |
Как выставить и снять бит через shl?
|
1 |
a := (a or (1 shl 5)); // Выставили |
|
1 |
a := ( a and not (1 shl 5) ); // Сняли (поправил здесь, всем спасибо) |
Как переключить бит? Если был выставлен – то снять, если был снят, то выставить?
|
1 |
a := (a xor 32); // 2^32 |
Как проверить несколько битов?
|
1 2 3 |
//Check if 5,2,0 bit in true like 00100101, 2^5+2^2+0^2=37 if (a and 37) = 37 then Memo.Lines.Add('5,2,0 bit in true'); |
Как перевести Byte в “нормальные биты”, то есть, например в 00100000 ?
|
1 2 3 4 5 6 7 8 9 10 11 12 |
function ShowBits(a:byte):string; var i: Integer; begin for i := 7 downto 0 do // Variant1 if (a and (1 shl i))<>0 then Result:=Result+'1' else Result:=Result+'0'; // Variant2 //for i:=7 downto 7 do if ((a shr i) and 1)=1 then Result:=Result+'1' else Result:=Result+'0'; end; |
А теперь все вместе…
Код, программы, иллюстрирующий элементарные битовые операции
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
procedure TfBits.StartClick(Sender: TObject); var a:byte; begin Memo.Lines.Clear; a:=0; // initializing as 1 if not to set manually... Memo.Lines.Add(ShowBits(a)+ ' a in string='+a.ToString()); //----------------------Setting 5 bit to true and check - Variant1 a:= (a or 32); // 2^5 //Check if 5 bit in true like 00100000, 2^5=32 if (a and 32)=32 then Memo.Lines.Add(ShowBits(a)+' Variant1. Setting 5 bit to true; a:= (a or 32); 5 bit in true'); //---------------------------Setting 5 bit to false and check - Variant1 a:=( a and (255-32) ); // 2^5=32 //Check if 5 bit in true or false like 00100000, 2^5=32 if not ( (a and 32)=32 ) then Memo.Lines.Add(ShowBits(a)+' Variant1. Setting 5 bit to false; a:=( a and (255-32) ); 5 bit in false'); //-------------------------Setting 5 bit to true and check - Variant2 a:=(a or (1 shl 5)); if (a and ((1 shl 5)))=32 then Memo.Lines.Add(ShowBits(a)+' Variant2. Setting 5 bit to true; a:=(a or (1 shl 5)); 5 bit in true'); //---------------------------Setting 5 bit to false - Variant2 a:=( a and not (1 shl 5) ); // //Check if 5 bit in true or false like 00100000, 2^5=32 if not ( (a and 32)=32 ) then Memo.Lines.Add(ShowBits(a)+' Variant2. Setting 5 bit to false; a:=( a and not (1 shl 5) ); 5 bit in false'); //Toggle 5 bit - if was true - will be false, if false - will be true a:=(a xor 32); // 2^32 //Check if 5 bit in true or false if ( (a and 32)=32 ) then Memo.Lines.Add(ShowBits(a)+' Toggle 5 bit; a:=(a xor 32); ; 5 bit in true if was in false and false if was in true') else if not ( (a and 32)=32 ) then Memo.Lines.Add(ShowBits(a)+' Toggle 5 bit; a:=(a xor 32); ; 5 bit in true if was in false and false if was in true'); //Check if 5,2,0 bit in true like 00100101, 2^5+2^2+0^2=37 if (a and 37)=37 then Memo.Lines.Add('5,2,0 bit in true'); end; function TfBits.ShowBits(a:byte):string; var i: Integer; One:Byte; begin for i := 7 downto 0 do // Variant1 if (a and (1 shl i))<>0 then Result:=Result+'1' else Result:=Result+'0'; // Variant2 //for i:=7 downto 7 do if ((a shr i) and 1)=1 then Result:=Result+'1' else Result:=Result+'0'; end; |
В принципе, это уже можно хранить в базе как varchar скажем в mySQL, но в MySQL, да и в любой другой базе есть свои возможности для работы с битовыми операциями. В одном из след. постов продолжу эту тему, а также постараюсь раскрыть работу с фильтром Блума. Этот пост получился как замануха))) Но по сути это было вступление.
6 Responses to Delphi. Битовые операции и фильтр Блума. Вступление.