• Status: Solved
• Priority: Medium
• Security: Public
• Views: 447

Delphi bitwise math problem

I have a set of values called Townships and Ranges. Each
Township/Range combination also has up to 36 Sections.

We currently have 95,000 Township/Range combinations stored in
a MSSQL2K DB table so adding a record for each
Township/Range/Section combination would be out of the question
(3+ million recs).

So we have surmised that we need to store valid Sections in a 36-
bit value in the field and need to determine the value for valid
Sections for a particular Township/Range combination.

Example:

Township Range  Section
001E     001N   001
001E     001N   002
001E     001N   003
001E     001N   004
001E     001N   005
001E     001N   006
001E     001N   009
001E     001N   010
001E     001N   011
001E     001N   012
001E     001N   013
001E     001N   015
001E     001N   016
001E     001N   017
001E     001N   018
001E     001N   019
001E     001N   020
001E     001N   021
001E     001N   022
001E     001N   023
001E     001N   024
001E     001N   027
001E     001N   028
001E     001N   029
001E     001N   030
001E     001N   031
001E     001N   032
001E     001N   033
001E     001N   034
001E     001N   036

As you can see, this Township/Range combination is missing
Sections 007, 008, 014, 025, 026, and 035.

Here's the value we need to store for the above example.
3         2         1
654321098765432109876543210987654321
111111001111101111111111001111111101
\$FCFBFF3FD (Hex)
67909972989 (Dec)

The user is entering Section values as '001' .. '036'. Let's say the
user entered '024' as the section. How do I check for the validity of
a section using Bitwise math?
0
Eddie Shipman
• 3
• 2
1 Solution

Commented:
if valuestored and (1 shl pred(section_number)) = 0 then
missing
else
exists;

...Bill
0

Commented:
I would start by reversing the order of bits, looking at your example bit field, you have field 001 located in the most significant bit location, it will make it easer to calculate if you place 001 in the least significant bit location.

This is what the same data would look like if re-organized:

Bytes:    5     4         3       2         1
Data:   1011 11111100 11111111 11011111 00111111
|  | |      | |      | |      | |      |
3633 32    25 24    17 16     9 8      1

HEX: \$BFCFFDF3F

Below are 2 functions you can use as an example on how to deal with individual bits; make sure you add the math unit under your uses clause.

Uses
Math;

function CheckForValidRecord(Data : int64;RecordNumber : integer):boolean;
var
BitValue : int64;

begin
//Get the value for the corresponding bit
BitValue := trunc(Power(2,RecordNumber -1));
//Check to see if we have a one or a zero for
//the corresponding bit
if (Data and BitValue) = BitValue then
result := true
else
result := false;
end;

//Set data bit on or off by specifying record number
//(1..36);
//true for on, false for off
procedure SetDataValidity(var Data : int64; RecordNumber : integer; Valid : boolean);
var
BitValue : Int64;

begin
//Get the value for the corresponding bit
BitValue := trunc(Power(2,RecordNumber -1));

if Valid then //Set the appropriate record bit
Data := Data or BitValue
else //Clear the appropriate record bit
Data := not (Data or BitValue);
end;

Hope this is what you needed, enjoy...
0

Commented:
WhoPhlungPoo's right about that bit order.

Decision time :

If you maintain your current system, then

if valuestored and (1 shl (36-section_number)) = 0 then
missing
else
exists;

or

if valuestored and (137438953472 shr section_number) = 0 then
missing
else
exists;

where 137438953472 = 2**37

will do your 'is the bit set' job.

Reversing the bit-order is desirable, since it allows you to expand the number of sections to 64 if desired with no code changes.

In that case, set the bit with
valuestored := valuestored or (1 shl pred(section_number))
and clear it with
valuestored := valuestored and not (1 shl pred(section_number))

HTH

...Bill

0

All-around developerAuthor Commented:
Thanks for the input. Will evaluate on Monday.
0

All-around developerAuthor Commented:
With some slight modifications, here is what we are using:

function CheckForValidSection(Data : int64;RecordNumber : integer):boolean;
var
BitValue : int64;
begin
//Get the value for the corresponding bit
BitValue := trunc(Power(2,RecordNumber -1));
//Check to see if we have a one or a zero for
//the corresponding bit
if (Data and BitValue) = BitValue then
result := true
else
result := false;
end;

//Set data bit on or off by specifying record number
//(1..36);
//true for on, false for off
procedure SetSection(var Data : int64; RecordNumber : integer; Valid : boolean);
var
BitValue : Int64;
begin
//Get the value for the corresponding bit
BitValue := (Int64(1) shl pred(RecordNumber));
if Valid then //Set the appropriate record bit
Data := Data or BitValue
else //Clear the appropriate record bit
Data := (Data and (not BitValue));
end;
0

Commented:
Er, Eddie,

I think that I should point out that had you converted the function I
first offered in the same way as you converted the set/clear procedure
I suggested, then the resulting function would be

function CheckForValidSection(Data : int64;RecordNumber : integer):boolean;
begin
CheckForValidSection := data and
(int64(1) shl pred(recordnumber)) <> 0 ;
end;

Which
* is shorter than your selection
* is smaller AND doesn't require the MATH unit
* is approximately nine times faster than the trunc..... method

{demo}
function CheckForValidSection2(Data : int64;RecordNumber : integer):boolean;
begin
CheckForValidSection2 := data and
(int64(1) shl pred(recordnumber)) <> 0 ;
end;

function CheckForValidSection(Data : int64;RecordNumber : integer):boolean;
var
BitValue : int64;
begin
//Get the value for the corresponding bit
BitValue := trunc(Power(2,RecordNumber -1));
//Check to see if we have a one or a zero for
//the corresponding bit
if (Data and BitValue) = BitValue then
result := true
else
result := false;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
d,t1,t2    : int64;
od,s       : integer;
done       : Boolean;
begin
t1 := 0;
t2 := 0;
for od := 0 to 1234567 do
for s := 1 to 36 do
begin
d := od;
{just count BITS encountered}
if checkforvalidsection(d,s) then inc(t1);
end;
for od := 0 to 1234567 do
for s := 1 to 36 do
begin
d := od;
{just count BITS encountered}
if checkforvalidsection2(d,s) then inc(t2);
end;
{show the count of BITS encountered was the same for both functions}
memo1.lines.add(inttostr(t1) + ' & ' + inttostr(t2));
done := false;

(* additional routine just to prove the two are equivalent

{ select your own range of interest for initial-d and final-d :
should take a month of running with max/min values
shown (1200MHz machine) }
d := 137438953472 ; {2 ** 37}
while (d <> 0) and (not done) do
begin
dec(d);
for s := 1 to 36 do
begin
if checkforvalidsection(d,s) <> checkforvalidsection2(d,s) then
begin
if not done then {interested in firs mismatch only }
memo1.lines.add('differ where ' + inttostr(d) + ' & ' + inttostr(s));
done := true;
end;
end;
end;
*)

end;
{enddemo}

Further,

//Set data bit on or off by specifying record number
//(1..36);
//true for on, false for off
procedure SetSection(var Data : int64; RecordNumber : integer; Valid : boolean);
var
BitValue : Int64;
begin
//Get the value for the corresponding bit
BitValue := (Int64(1) shl pred(RecordNumber));
if Valid then //Set the appropriate record bit
Data := Data or BitValue
else //Clear the appropriate record bit
Data := (Data and (not BitValue));
end;

Can be simplified to
//Set data bit on or off by specifying record number
//(1..36);
//true for on, false for off
procedure SetSection(var Data : int64; RecordNumber : integer; Valid : boolean);
begin
//Get the value for the corresponding bit
if Valid then //Set the appropriate record bit
Data := Data or (Int64(1) shl pred(RecordNumber))
else //Clear the appropriate record bit
Data := (Data and (not (Int64(1) shl pred(RecordNumber))));
end;

which avoids having to temporarily store BitValue.

HTH

...Bill
0

Featured Post

• 3
• 2
Tackle projects and never again get stuck behind a technical roadblock.