3.4 Useful Bit Operations

Although bit operations may seem a bit abstract, they are quite useful for many non-obvious purposes. The following subsections describe some of their useful properties of using the logical operations in various languages.

3.4.1 Testing Bits in a Bit String Using AND

You can use the bitwise AND operator to test individual bits in a bit string to see if they are zero or one. If you logically AND a value with a bit string that contains a one in a certain bit position, the result of the logical AND will be zero if the corresponding bit contains a zero, and the result will be nonzero if that bit position contains one. Consider the following C/C++ code that checks an integer value to see if it is odd or even by testing if bit zero of the integer:

 IsOdd = (ValueToTest & 1) != 0;

In binary form, here's what this bitwise AND operation is doing:

 xxxx_xxxx_xxxx_xxxx_xxxx_xxxx_xxxx_xxxx  // Assuming ValueToTest is 32 bits  0000_0000_0000_0000_0000_0000_0000_0001  // Bitwise AND with the value one  --------------------------------------- 0000_0000_0000_0000_0000_0000_0000_000x  // Result of bitwise AND

The result is zero if the LO bit of ValueToTest contains a zero in bit position zero. The result is one if ValueToTest contains a one in bit position one. This calculation ignores all other bits in ValueToTest .

3.4.2 Testing a Set of Bits for Zero/Not Zero Using AND

You can also use the bitwise AND operator to check a set of bits to see if they are all zero. For example, one way to check to see if a number is evenly divisible by 16 is to see if the LO four bits of the value are all zeros. The following Delphi/Kylix statement uses the bitwise AND operator to accomplish this:

 IsDivisibleBy16 := (ValueToTest and $f) = 0;

In binary form, here's what this bitwise AND operation is doing:

 xxxx_xxxx_xxxx_xxxx_xxxx_xxxx_xxxx_xxxx  // Assuming ValueToTest is 32 bits  0000_0000_0000_0000_0000_0000_0000_1111  // Bitwise AND with $F  --------------------------------------- 0000_0000_0000_0000_0000_0000_0000_xxxx  // Result of bitwise AND

The result is zero if and only if the LO four bits of ValueToTest are all zero, because ValueToTest is evenly divisible by 16 only if its LO four bits all contain zero.

3.4.3 Comparing a Set of Bits Within a Binary String

The AND and OR operations are particularly useful if you need to compare a subset of the bits in a binary value against some other value. For example, you might want to compare two 6-bit values found in bits 0, 1, 10, 16, 24, and 31 of a pair of 32-bit values. The trick is to set all the uninteresting bits to zero and then compare the two results. ^[1]

Consider the following three binary values; the 'x' bits denote bits whose values we don't care about:

 %1xxxxxx0xxxxxxx1xxxxx0xxxxxxxx10  %1xxxxxx0xxxxxxx1xxxxx0xxxxxxxx10  %1xxxxxx1xxxxxxx1xxxxx1xxxxxxxx11

If we compare the first and second binary values (assuming we're only interested in bits 31, 16, 10, 1, and 0), we should find that the two values are equal. If we compare either of the first two values against the third value, we'll find that they are not equal. Furthermore, if we compare either of the first two values against the third, we should discover that the third value is greater than the first two. In C/C++ and assembly, this is how we could compare these values:

 // C/C++ example      if((value1 & 0x81010403) == (value2 & 0x81010403))      {          // Do something if bits 31, 24, 16, 10, 1, and 0 of          //  value1 and value2 are equal      }      if((value1 & 0x81010403) != (value3 & 0x81010403))      {          // Do something if bits 31, 24, 16, 10, 1, and 0 of          //  value1 and value3 are not equal      }  // HLA/x86 assembly example:      mov(value1, eax);       // EAX = value1      and(01_0403, eax);   // Mask out unwanted bits in EAX      mov(value2, edx);       // EDX = value2      and(01_0403, edx);   // Mask out the same set of unwanted bits in EDX      if(eax = edx) then      // See if the remaining bits match           // Do something if bits 31, 24, 16, 10, 1, and 0 of           //  value1 and value2 are equal      endif;      mov(value1, eax);       // EAX = value1      and(01_0403, eax);   // Mask out unwanted bits in EAX      mov(value3, edx);       // EDX = value2      and(01_0403, edx);   // Mask out the same set of unwanted bits in EDX           if(eax <> edx) then     // See if the remaining bits do not match               // Do something if bits 31, 24, 16, 10, 1, and 0 of          // value1 and value3 are not equal      endif;

3.4.4 Creating Modulo-n Counters Using AND

The AND operation lets you create efficient modulo-n counters . A modulo-n counter counts from zero ^[2] to some maximum value and then resets to zero. Modulo-n counters are great for creating repeating sequences of numbers such as 0, 1, 2, 3, 4, 5, . . . n ˆ’ 1, 0, 1, 2, 3, 4, 5, . . . n ˆ’ 1, 0, 1, . . . . You can use such sequences to create circular queues and other objects that reuse array elements upon encountering the end of the data structure. The normal way to create a modulo-n counter is to add one to the counter, divide the result by n, and then keep the remainder. The following code examples demonstrate the implementation of a modulo-n counter in C/ C++, Pascal, and Visual Basic:

 cntr = (cntr + 1) % n;    // C/C++  cntr := (cntr + 1) mod n;  // Pascal/Delphi/Kylix  cntr = (cntr + 1) Mod n    ` Visual Basic

The problem with this particular implementation is that division is an expensive operation, requiring far more time to execute than operations such as addition. In general, you'll find it more efficient to implement modulo-n counters using a comparison rather than the remainder operator. Here's a Pascal example:

 cntr := cntr + 1;     // Pascal example  if(cntr >= n) then      cntr := 0;

For certain special cases, however, you can increment a modulo-n counter more efficiently and conveniently using the AND operation. You can use the AND operator to create a modulo-n counter when n is a power of two. To create such a modulo-n counter, increment your counter and then logically AND it with the value n = 2 ^m ˆ’ 1 (2 ^m ˆ’ 1 contains ones in bit positions 0.. m ˆ’ 1 and zeros everywhere else). Because the AND operation is usually much faster than a division, AND-driven modulo-n counters are much more efficient than those using the remainder operator. Indeed, on most CPUs, using the AND operator is quite a bit faster than using an if statement. The following examples show how to implement a modulo-n counter for n = 32 using the AND operation:

 //Note: 0x3f = 31 = 2 ⁵   1, so n = 32 and m = 5      cntr = (cntr + 1) & 0x3f;    // C/C++ example      cntr := (cntr + 1) and f;  // Pascal/Delphi/Kylix example      cntr = (cntr + 1) And &h3f   ` Visual Basic example

The assembly language code is especially efficient:

 inc(eax);               // Compute (eax + 1) mod 32  and(f, eax);

^[1] It's also possible to set all the uninteresting bits to ones via the OR operation, but the AND operator is often more convenient .

^[2] Actually, they could count down to zero as well, but usually they count up.