11.8 Searching for a Bit


11.8 Searching for a Bit

A very common bit operation is to locate the end of some run of bits. A very common special case of this operation is to locate the first (or last) set or clear bit in a 16- or 32-bit value. In this section we'll explore ways to accomplish this.

Before describing how to search for the first or last bit of a given value, perhaps it's wise to discuss exactly what the terms "first" and "last" mean in this context. The term "first set bit" means the first bit in a value, scanning from bit zero toward the high order bit, which contains a one. A similar definition exists for the "first clear bit." The "last set bit" is the first bit in a value, scanning from the high order bit toward bit zero, which contains a one. A similar definition exists for the last clear bit.

One obvious way to scan for the first or last bit is to use a shift instruction in a loop and count the number of iterations before you shift out a one (or zero) into the carry flag. The number of iterations specifies the position. Here's some sample code that checks for the first set bit in EAX and returns that bit position in ECX:

           mov( -32, ecx );      // Count off the bit positions in ECX. TstLp:shr( 1, eax );            // Check to see if current bit position contains           jc Done               // a one; exit loop if it does.           inc( ecx );           // Bump up our bit counter by one.           jnz TstLp;            // Exit if we execute this loop 32 times. Done:     add( 32, cl );        // Adjust loop counter so it holds the bit posn. // At this point, ECX contains the bit position of the first set bit. // ECX contains 32 if EAX originally contained zero (no set bits). 

The only thing tricky about this code is the fact that it runs the loop counter from -32 up to zero rather than 32 down to zero. This makes it slightly easier to calculate the bit position once the loop terminates.

The drawback to this particular loop is that it's expensive. This loop repeats as many as 32 times depending on the original value in EAX. If the values you're checking often have lots of zeros in the L.O. bits of EAX, this code runs rather slow.

Searching for the first (or last) set bit is such a common operation that Intel added a couple of instructions on the 80386 specifically to accelerate this process. These instructions are bsf (bit scan forward) and bsr (bit scan reverse). Their syntax is as follows:

           bsr( source, destReg );           bsf( source, destReg ); 

The source and destinations operands must be the same size, and they must both be 16- or 32-bit objects. The destination operand has to be a register. The source operand can be a register or a memory location.

The bsf instruction scans for the first set bit (starting from bit position zero) in the source operand. The bsr instruction scans for the last set bit in the source operand by scanning from the H.O. bit toward the L.O. bit. If these instructions find a bit that is set in the source operand then they clear the zero flag and put the bit position into the destination register. If the source register contains zero (i.e., there are no set bits) then these instructions set the zero flag and leave an indeterminate value in the destination register. Note that you should test the zero flag immediately after the execution of these instructions to validate the destination register's value. Examples:

           mov( SomeValue, ebx );      // Value whose bits we want to check.           bsf( ebx. eax );            // Put position of first set bit in EAX.           jz NoBitsSet;               // Branch if SomeValue contains zero.           mov( eax, FirstBit );       // Save location of first set bit.            .            .            . 

You use the bsr instruction in an identical fashion except that it computes the bit position of the last set bit in an operand (that is, the first set bit it finds when scanning from the H.O. bit toward the L.O. bit).

The 80x86 CPUs do not provide instructions to locate the first bit containing a zero. However, you can easily scan for a zero bit by first inverting the source operand (or a copy of the source operand if you must preserve the source operand's value). If you invert the source operand, then the first "1" bit you find corresponds to the first zero bit in the original operand value.

The bsf and bsr instructions are complex 80x86 instructions (i.e., they are not a part of the 80x86 "RISC core" instruction set). Therefore, these instructions may be slower than other instructions. Indeed, in some circumstances it may be faster to locate the first set bit using discrete instructions. However, because the execution time of these instructions varies widely from CPU to CPU, you should first test the performance of these instructions prior to using them in time critical code.

Note that the bsf and bsr instructions do not affect the source operand. A common operation is to extract the first (or last) set bit you find in some operand. That is, you might want to clear the bit once you find it. If the source operand is a register (or you can easily move it into a register) and then you can use the btr (or btc) instruction to clear the bit once you've found it. Here's some code that achieves this result:

           bsf( eax, ecx );      // Locate first set bit in EAX.           if( @nz ) then        // If we found a bit, clear it.                btr( ecx, eax ); // Clear the bit we just found.           endif; 

At the end of this sequence, the zero flag indicates whether we found a bit (note that btr does not affect the zero flag). Alternately, you could add an else section to the if statement above that handles the case when the source operand (EAX) contains zero at the beginning of this instruction sequence.

Because the bsf and bsr instructions only support 16- and 32-bit operands, you will have to compute the first bit position of an 8-bit operand a little differently. There are a couple of reasonable approaches. First, of course, you can usually zero extend an 8-bit operand to 16 or 32 bits and then use the bsf or bsr instructions on this operand. Another alternative is to create a look-up table where each entry in the table contains the number of bits in the value you use as an index into the table; then you can use the xlat instruction to "compute" the first bit position in the value (note that you will have to handle the value zero as a special case). Another solution is to use the shift algorithm appearing at the beginning of this section; for an eight-bit operand, this is not an entirely inefficient solution.

One interesting use of the bsf and bsr instructions is to "fill in" a character set with all the values from the lowest-valued character in the set through the highest-valued character. For example, suppose a character set contains the values {‘A,’ ‘M,’ ‘a’..‘n,’ ‘z’}; if we filled in the gaps in this character set we would have the values {‘A’..‘z’}. To compute this new set we can use bsf to determine the ASCII code of the first character in the set and bsr to determine the ASCII code of the last character in the set. After doing this, we can feed those two ASCII codes to the cs.rangeChar function to compute the new set.

You can also use the bsf and bsr instructions to determine the size of a run of bits, assuming that you have a single run of bits in your operand. Simply locate the first and last bits in the run (as above) and the compute the difference (plus one) of the two values. Of course, this scheme is only valid if there are no intervening zeros between the first and last set bits in the value.




The Art of Assembly Language
The Art of Assembly Language
ISBN: 1593272073
EAN: 2147483647
Year: 2005
Pages: 246
Authors: Randall Hyde

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net