Please enable JavaScript to view this site.

ASQL Reference

Navigation: » No topics above this level «

Boolean Bit-wise Arithmetic

Scroll Prev Top Next More

The Boolean operators labeled "Logical" in the Operator Table above (AND, OR, NOT, etc.) can give rise to two kinds of confusion. The first results from general confusion about the rules of Boolean logic when multiple operators are combined. For example, forgetting that [ NOT X AND NOT Y ] is equivalent to [ NOT (X OR Y) ] rather than [ NOT (X AND Y) ]. This isn't the place to resolve that kind of confusion; instead consult a textbook on Boolean logic. The second kind, which hopefully we can resolve here, has to do with the fact that, at least in ASB, these so-called "logical" operators are actually arithmetic operators, similar to other arithmetic operators except that they work at the bit-by-bit level with no borrowing or carrying between bits. So while you may be tempted to view the expression [ X AND Y ] as having a purely logical value, i.e. TRUE or FALSE, in fact it has a purely numeric value resulting from the bit-wise ANDing operation, which can then be used like any other numeric expression, e.g. P = (X AND Y) * Z.

The following example should make this more clear:

MAP1 X,B,1

MAP1 Y,B,1

 

X = 1

Y = 4

? (X OR Y)       ! 00000001 OR 00000100  = 00000101 (5)

? (X AND Y)      ! 00000001 AND 00000100 = 00000000 (0)

? NOT X          ! NOT 00000001 = 11111110 (-2)

? NOT (X AND Y)  ! NOT 00000000 = 11111111 (-1)

? (X + Y)        ! 00000001 + 00000100 = 00000101 (5)

 

This is pure bit-wise Boolean arithmetic. Note that negative values are represented using 2's complement notation; -1 is represented by all 1 bits. Also note that in the above example, (X OR Y) is equivalent to (X + Y), because when viewed one bit at a time, the OR and + operations are equivalent. The difference between the two only shows up when there is a carry operation, e.g.

X = 1

Y = 5

? (X OR Y)       ! 00000001 OR 00000101  = 00000101 (5)

? (X + Y)        ! 00000001 + 00000101 = 00000110 (6)

 

So the Boolean operators are for all practical purposes like other arithmetic operators, except that the Boolean operations never result in borrowing or carrying from one bit position to the next.

The question of truth value, i.e. is the expression TRUE or FALSE, only arises in conjunction with relational operators (=, >, <, etc.) or conditional statements (IF, WHILE, UNTIL, etc.), which convert the numeric value of an expression to TRUE or FALSE according to the simple rule:

Zero is FALSE

Non-Zero is TRUE

 

If we revisit our first example above, this time using IF statements to test the logical truth value of the expressions instead of directly printing the numerical value, we get the following:

10 X = 1 : Y = 4

20 IF (X OR Y)       ? "TRUE" ELSE ? "FALSE"  ! TRUE  (5)

30 IF (X AND Y)      ? "TRUE" ELSE ? "FALSE"  ! FALSE (0)

40 IF NOT X          ? "TRUE" ELSE ? "FALSE"  ! TRUE (-2)

50 IF NOT (X AND Y)  ? "TRUE" ELSE ? "FALSE"  ! TRUE (-1)

60 IF (X + Y)        ? "TRUE" ELSE ? "FALSE"  ! TRUE (5)

 

These results follow directly from the rule just stated, that 0 is FALSE and any other value is TRUE. Yet line 30 often confuses programmers, considering that since both X and Y are non-zero—i.e. both are TRUE when considered individually—the expression (X AND Y) should be equivalent to (TRUE AND TRUE), i.e. should be TRUE. Similarly, in line 40, since X is non-zero, it must be TRUE, and therefore NOT X must be FALSE. Right? Wrong. The discrepancy is caused by the fact that the Boolean operators act arithmetically at the bit-wise level resulting in a numeric value which is only converted to logical TRUE or FALSE when needed for the conditional IF statement.

A-Shell, like most other languages, does not have a specific built-in Boolean data type and relies instead on the above rule for converting numeric expressions to logical TRUE/FALSE as required by relational operators and statements. If you want to define variables to represent TRUE and FALSE, you can either MAP them, i.e.:

MAP1 LOGICAL'CONSTANTS

    MAP2 TRUE,B,1,-1

    MAP2 FALSE,B,1,0

 

or defined constants, e.g.:

define TRUE = -1

define FALSE = 0

 

Although you might be tempted to use 1 for your TRUE value, and that might work in some cases, but -1 is a far better choice, since its binary representation is all 1's, and thus any bit-wise operation will always be dealing with a 1 on the TRUE side. If you used 1 (i.e. 00000001), then only the first bit would get the benefit of the non-zero value and all the other bit-wise operations would be dealing with zeroes (i.e. FALSE bits). See Boolean Data Type.

Note that when a logical expression is converted back to a numeric expression, as in the statement PRINT (X = Y), FALSE becomes 0 and TRUE becomes -1. So there is an asymmetry in the conversion back and forth between numeric and logical truth. When converting from numeric to logical, any non-zero value becomes TRUE; but when converting logical to numeric, TRUE always becomes -1. This is another reason why if you're going to define a constant TRUE, it should be set to -1.

Also note that while defining constants TRUE and FALSE may be convenient for the readability of code similar to the following:

IF (X AND Y) THEN

    AUTHORIZED = TRUE

ELSE

    AUTHORIZED = FALSE

ENDIF

 

... be careful not to casually use a relational operator to compare a numeric expression directly with your constant TRUE, e.g.

IF AUTHORIZED = TRUE THEN ...     ! bad!!!

Instead, use the logical equivalence operator EQV:

IF AUTHORIZED EQV TRUE THEN ...   ! good

Or better yet, just test the variable directly and let the IF operator convert it from a number to a truth value:

IF AUTHORIZED THEN ...            ! best

The problem with using the relational equals operator (=) is that the result of the expression is TRUE only if both operands are numerically equal (i.e. AUTHORIZED = -1). Almost surely what you mean to be testing is if they are logically equivalent to TRUE (i.e. both are non-zero). And since TRUE is obviously equivalent to itself, X EQV TRUE is the same as X, so just testing the target variable directly as in the last example is the simplest.

To take another example:

10 define F_DOG   = &h0001

20 define F_CAT   = &h0002

30 define F_TAME  = &h0010

30 IS'PET = (ANIMAL'TYPE AND (F_DOG OR F_CAT or F_TAME))

40 IF IS'PET = TRUE THEN CALL FEED'IT    ! bad idea, pet will starve

50 IF IS'PET THEN CALL FEED'IT           ! good, pet gets fed

 

Line 30 sets IS'PET to a non-zero value if the ANIMAL'TYPE bit representation contains either of the dog or cat or tame bits. Line 40 would virtually always fail, since the result of the assignment at line 30 will almost surely not be -1 (i.e. all bits set). Line 50 shows the correct approach, since the numeric expression IS'PET will be converted to logical TRUE if any of the bits are set.

Beware of Boolean combinations

When dealing with bit flags, we are often interested in testing whether if one among several bits is set, or if two or more bits are together set. We can use the AND operator to test if bits are set, and the OR operator to create an expression containing multiple bits that can then be tested as a group. Continuing with the pet example above, to test if our animal represented by ANIMAL'TYPE is either a dog or is tame, we can do either of the following:

IF (ANIMAL'TYPE AND F_DOG) OR (ANIMAL'TYPE AND F_TAME) THEN ...  ! if dog or tame

IF (ANIMAL'TYPE AND (F_DOG OR F_TAME)) THEN ...                  ! "    "    "   "

 

So far so good.  But to test if it is a tame dog (i.e. is both a dog and tame), don't make the mistake of just flipping the central Boolean from OR to AND:

IF (ANIMAL'TYPE AND F_DOG) AND (ANIMAL'TYPE AND F_TAME) THEN ... ! bad

IF (ANIMAL'TYPE AND (F_DOG AND F_TAME)) THEN ...                 ! bad 

 

The problem with both of the above statements is that F_DOG and F_TAME are non-overlapping bit patterns (&h0001 and &h0010). Thus the numeric expressions (ANIMAL'TYPE AND F_DOG) and (ANIMAL'TYPE AND F_TAME) are also going to be non-overlapping bit patterns, so ANDing them together will always result in zero (FALSE). Even worse, the expression (F_DOG AND F_TAME) is always zero (both are constants), and anything ANDed with zero is zero, so the second conditional will might as well be a null statement . The way to test if both bits are set is to introduce relational operators to strategically convert the numeric sub-expressions to logical ones, e.g.

IF ((ANIMAL'TYPE AND F_DOG) # 0) AND ((ANIMAL'TYPE AND F_TAME) # 0) THEN ... ! good

IF (ANIMAL'TYPE AND (F_DOG OR F_TAME)) = (F_DOG OR F_TAME) THEN ...          ! good 

 

Here, in the first statement we used the relational operator # (not equal) to convert the numerical expressions (ANIMAL'TYPE AND F_xxx) to logical expressions (i.e. to -1 for TRUE or 0 for FALSE). That allows the central AND operator to give us a numerical result which is non-zero if both of the sub-expressions were non-zero (matching the expected logical behavior). In the second line, we mask out all of the other bits in ANIMAL'TYPE except for the F_DOG and F_TAME bits, and then use the relational operator = to numerically compare if that equals the combination of those two bits, i.e. if both bits are set.