Monday, September 30, 2019

CompareValue for booleans

CompareValue function is incredibly practical when you are writing comparers (functions that determine how some data structure is ordered). System.Math and System.StrUtils define a bunch of functions that can be used to compare integers, doubles, strings … There’s, however, no CompareValue for booleans.

A CompareValue function compares two parameters, traditionally named left and right, and returns 0 if they are the same, –1 if left is smaller and 1 if right is smaller.

If we use the usual ordering of false < true, we can write the missing function as follows:

function CompareValue(left, right: boolean): integer; overload;
begin
  if left < right then
    Result := -1
  else if left > right then
    Result := 1
  else
    Result := 0;
end;

Your task for today – if you choose to accept it – is: Write this function without any if statements.

One possible solution:

function CompareValue(left, right: boolean): integer; overload;
begin
  Result := Ord(left and not right) - Ord(right and not left);
end;

A proof – in a form of an Excel spreadsheet, nonetheless:

left right left and not right right and not left Ord(l & ^r) Ord(r & ^l) Ord(l & ^r) - Ord(r & ^l)
FALSE FALSE FALSE FALSE 0 0 0
FALSE TRUE FALSE TRUE 0 1 -1
TRUE FALSE TRUE FALSE 1 0 1
TRUE TRUE FALSE FALSE 0 0 0

9 comments:

  1. > Write this function without any if statements

    But why would you do that...?

    I'd bet that if you compare the generated assembly of the two functions, the first version is more efficient.

    ReplyDelete
  2. Um, why not just do:

    Result := Ord(Left) - Ord(Right);

    For Booolean, False is 0 and True is 1, unless I've missed something.

    ReplyDelete
    Replies
    1. Certainly better than my solution. I never claimed I have published the best one ;)

      Delete
    2. You missed that value might come from outside. Like in Microsoft compilers TRUE is -1 not +1 as in Borland compilers. Also, there can be any garbage like 42. Or -42.

      Also, true(10) and true(100), which is larger?

      So, my approach would be Result := Sign(cardinal(Left)) - Sign(Cardinal(Right);
      Why not byte(...) ? Because there are also LongBool and WordBool data types.

      Or equivalent assembler code if we could have inline assembler functions :-D

      Delete
    3. Funny thing, Intel also makes True being +1, in hardware (see SETcc opcodes introduced into 80386 processor in early 1990-s). Dunno why, for -1 always seemed more natural TRUE to me, being the complement thus unifying bitwise and logic operations.

      Delete
    4. @Arioch, do the non-bit Boolean types cast down implicitly? I'm not sure.

      Your approach should work though. As long as casting to Cardinal doesn't cause problems for LongBools. Aren't LongBools signed?

      Delete
    5. @Arioch:

      sign() requires math.pas and will end up slow. And <0 is true in boolean!

      Result := Ord(left <> false) - Ord(right <> false);

      This also gives you the simplest assembly, better than "ifs" even.

      Delete
    6. Or maybe even

      Result := Ord(Ord(left)<>0) - Ord(Ord(right)<>0)

      In case Delphi ever decides to start optimizing "left <> false" to simply "left".

      Delete