## BooleansA Boolean is a simple data type that has two states; TRUE and FALSE. However, the representations of these states can differ. One possibility is that any non-zero value is defined to be TRUE, and zero is false. Another is that TRUE always takes the value of 1, and yet another is that TRUE is always -1. Each of these possibilities has different strengths and weaknesses. The flexibility of the non-zero TRUE case can be very helpful when writing code. However, the greater specificity of the other cases can lead to greater optimization. Different computer languages make different choices here. The C programming language uses the more flexible definition in ## C-like BooleansThe problem is how to efficiently evaluate boolean expressions when given the flexible inputs. (The more concrete cases are easy as the bitwise Such a "clamp" or "booleanize" operation looks like:
in C. Fortunately, this is relatively easy to optimize. We just compare with zero, and set the result to be 1 or 0 based on the comparison. The `setcc` instructions are perfect for this.
Similarly, the Boolean
By using the above two routines, it is easy to convert any Boolean expression in to ones where bitwise operations can compute the results. However, often we can do better than having to use multiple A Boolean
Similarly, a
Unfortunately, no other Boolean operation are as compact. The reason is that, for example, a bitwise However, if we can cheaply convert one of the inputs to the
The above can be modified in a couple of ways. Firstly, we can obviously toggle the sense of the output
Secondly, we can use a comparison or subtraction to set the carry flag on zero instead of non-zero. This allows us to implement the following operation:
Finally, the above can have its output inverted to yield:
This covers many Boolean operations on two variables. However, there are a couple more interesting ones left. The first is the comparison of two Booleans. In C, this can be expressed as:
The above can be computed by converting to Booleans, then using an `xor` or `cmp` instruction. However, be using a property of addtion, we can create something faster and more compact. (The idea is that addition acts like xor on the lowest bit... and xor acts like an inverted comparison operation.)
Similarly, the result of an inverted Boolean comparison can be obtained:
The above examples show how ordinary Boolean operations can be optimized in C-like languages. How well does your compiler do? ## Booleans with TRUE = -1When TRUE is always -1, we have a different problem. We don't need to worry about doing operations on a Boolean as the bitwise ones will work just as well. We need to think about optimizing the initial comparisons which create Boolean values instead. As shown above, the Testing for (in)equality with zero is easy:
Special cases also exist for signed comparison with zero.
The above can be extended for comparison with arbitrary constants, rather than just zero. In what follows, we'll use the value 137, but almost any other will work. However, be careful in that some edge cases dealing with INT_MIN or INT_MAX may fail. Firstly, equality and inequality:
Next signed inequalities. (Noting that you can easily convert <= and >= into < and > with slightly different constants.)
Finally, unsigned comparison is even simpler:
## The Carry FlagThe above makes use of the carry flag extensively. Due to the existence of the The only problem to worry about is the memory model for your computer language. The following identities assume that the number of writes to a given variable can be changed. This may be true for local automatic variables which have not had their address taken. Global variables are a different matter. Another thread might be reading/writing to them simultaneously with regards to this code. Taking that limitation into account, we can show conditional increments or decrements if a variable is equal to zero:
The above can be slightly altered into the following identities:
Conditional increments or decrements as the result of unsigned comparisons are easy to implement. (Where again we default to testing with the constant 137.)
Unfortunately, doing this with signed comparisons is much more complex. They set the overflow and sign flags instead of the carry flag. Thus, we need a trick to get the result where we want it. We fix things by changing the range of value so that INT_MAX corresponds to 0xffffffff, and INT_MIN to 0 by toggling the sign bit. This can be done by adding 0x80000000 to the integer we wish to compare. (Similarly, xoring or subtracting will also work to toggle the sign bit.) Signed comparisons with zero can be simpler than other values:
Of course, we can also obtain instruction sequences containing comparisons with arbitrary constants. Again, be careful with INT_MIN or INT_MAX, where the following will fail.
## SummaryBooleans are a fundamental part of computation. From the carry flag through to the flexible Booleans of the C programming language, they are used everywhere. This article shows how common expressions can be optimized by using their properties. How many of these does your compiler know? |

About Us | Returns Policy | Privacy Policy | Send us Feedback |

Company Info |
Product Index |
Category Index |
Help |
Terms of Use
Copyright © Lockless Inc All Rights Reserved. |

## Comments

said...