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

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
Asked:
Eddie Shipman
  • 3
  • 2
1 Solution
 
billiousCommented:
if valuestored and (1 shl pred(section_number)) = 0 then
  missing
else
  exists;

...Bill
0
 
WhoPhlungPooCommented:
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
 
billiousCommented:
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
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
Eddie ShipmanAll-around developerAuthor Commented:
Thanks for the input. Will evaluate on Monday.
0
 
Eddie ShipmanAll-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
 
billiousCommented:
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;
  memo1.lines.add(datetimetostr(now));
  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;
  memo1.lines.add(datetimetostr(now));
  memo1.lines.add(datetimetostr(now));
  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;
  memo1.lines.add(datetimetostr(now));
  {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

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

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