?
Solved

Delphi bitwise math problem

Posted on 2003-03-07
6
Medium Priority
?
446 Views
Last Modified: 2010-04-04
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
Comment
Question by:EddieShipman
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
6 Comments
 
LVL 7

Expert Comment

by:billious
ID: 8092153
if valuestored and (1 shl pred(section_number)) = 0 then
  missing
else
  exists;

...Bill
0
 

Accepted Solution

by:
WhoPhlungPoo earned 500 total points
ID: 8092194
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
 
LVL 7

Expert Comment

by:billious
ID: 8092266
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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 26

Author Comment

by:EddieShipman
ID: 8093706
Thanks for the input. Will evaluate on Monday.
0
 
LVL 26

Author Comment

by:EddieShipman
ID: 8105869
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
 
LVL 7

Expert Comment

by:billious
ID: 8109109
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: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article explains how to create forms/units independent of other forms/units object names in a delphi project. Have you ever created a form for user input in a Delphi project and then had the need to have that same form in a other Delphi proj…
Introduction I have seen many questions in this Delphi topic area where queries in threads are needed or suggested. I know bumped into a similar need. This article will address some of the concepts when dealing with a multithreaded delphi database…
Michael from AdRem Software outlines event notifications and Automatic Corrective Actions in network monitoring. Automatic Corrective Actions are scripts, which can automatically run upon discovery of a certain undesirable condition in your network.…
How to fix incompatible JVM issue while installing Eclipse While installing Eclipse in windows, got one error like above and unable to proceed with the installation. This video describes how to successfully install Eclipse. How to solve incompa…
Suggested Courses
Course of the Month9 days, 18 hours left to enroll

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question