Sometimes, you need to be able to verify the existence of just one high bit in a word. This ability can be useful, for example, to verify whether just one bit in a mask of mutually exclusive flags is set or if an incongruence exists in a word representing a set of input contacts. The most obvious way to implement this verification is to use a loop and a counter. You test the bits in a word one at a time and increment the counter when you find a high bit. The following listing shows a C routine for the verification function:

int HasOne(int value) {
 int nOnes=0;
 while(value) {
 if(value<0) ++nOnes; } return nOnes="=1;" }

The problem with the foregoing approach is low speed. You must test each bit in the word, so that the loop executes eight, 16, or 32 times, depending on the size of the word. You can implement a faster test by using a look-up table. You initialize each element in the table once, using the code "lookUpTable[[val]]=HasOne(val)." After you initialize the table, you can quickly test a value by reading the contents of the look-up table, indexed by the value (unsigned in this case) you're checking. The obvious problem with this second approach is the size of the look-up table. With a 16-bit value, for example, you need a capacity of 64 kbytes.

An alternative allows you to perform the test quickly and without extra memory. The method is based on a simple mathematical operation that allows you to check whether a word has more than one bit high. Consider the expression "value AND (value-1)." If "value" has only one bit high (ie, the bit is a power of two), then subtracting one turns that bit low and all the less-significant bits high (Figure 1). The result of ANDing these two values is zero. It's easy to verify that the ANDing result is zero for any position of the high bit and is also zero if "value" is zero.

If "value" has more than one bit high, then the subtraction does not modify the most significant high bit, which remains high. The ANDing of the two values gives a non-zero result. So, to verify that a word has exactly one bit high, it suffices to test that the value of the word is not zero and that the ANDing result is zero. You can code the operation in a C macro for maximum speed and code readability:

#define HasOne1(value) ((value ((value)&(value-1)))

The macro works for any size of value. (DI #1879)