Patent Document

BACKGROUND 
   This invention relates generally to processor-based systems and, particularly, to systems that need to locate a most or least significant bit of a computer word. 
   In a number of circumstances, it is desirable to locate the most or least significant bit of a computer word. For example, in various arithmetic operations this may be desirable. In particular, it is useful to know where the most significant bit is located to estimate the quotient for division, as well as in a variety of other situations. 
   One technique to find a significant bit is to simply look at each bit in order and to stop when the first non-zero bit is found. While this approach is simple, it has a running time proportional to the length of the data. 
   Alternatively, the most significant bit may be located by treating the datum as an integer and performing a binary search for the least power of two which is greater than the datum. This result can then be used to directly compute the index of the most significant bit. Although this algorithm may reduce the computational complexity to the log of the datum size, the overhead for testing and branching is high. 
   Thus, there is a need for better ways to locate significant bits. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a schematic depiction of one embodiment of the present invention; and 
       FIG. 2  is a flow chart for one embodiment of the present invention. 
   

   DETAILED DESCRIPTION 
   Referring to  FIG. 1 , a processor-based system  10  may include a processor  12  coupled to a storage  14 . The storage  14  may be any type of device capable of storing data including a semiconductor memory, a rotatable disk storage device, or logic. 
   The storage  14  may include a plurality of predicate registers  16   a - 16   d . In one embodiment of the present invention, the processor  12  may be capable of implementing parallel operations. A predicate register stores a single binary value. 
   A software program  18  may be stored on the storage  14  in one embodiment of the present invention. In other embodiments, the program  18  may be stored in a storage different from the storage that includes the predicate registers  16 . 
   The software program  18 , shown in  FIG. 2 , begins by defining a plurality of masks as indicated in block  20 . The first mask has alternate bits set to one. A second mask has every other pair of bits set to one. The next mask has every other group of four bits set to one. The next mask has every other set of eight bits set to one, and so on doubling the number of set bits per group in each mask until the number of consecutive set bits is greater than or equal to one-half the length of the datum to be tested. 
   For simplicity, hereafter, an embodiment of the invention is described that operates on sixteen bit data values. However, the present invention is not limited to any particular data size. 
   Next, a shifted value is defined as indicated in block  22 . The original data value that contains the bit being located may be compared to the original value shifted to the right by one. Then, in parallel, each mask is applied to the original value and compared to the shifted value as indicated in block  24 . In other words, each mask is applied in turn to the value under question and compared to the original value shifted right by one in one embodiment. 
   If the mask value is greater than the shifted value, the corresponding predicate register  16  is set to one. Otherwise, the predicate register is set to zero. As shown in  FIG. 2 , the predicate registers  16  may be loaded with the appropriate values as indicated in block  26 . After this has been done for each mask, the predicate registers  16  are moved into a single machine register by using a MOV instruction. The resulting value is the zero-based index of the most significant bit. The same approach may be utilized to find the least significant bit. 
   The following pseudocode may be utilized in an embodiment seeking the most significant bit of a sixteen bit value, producing the zero-based index of the highest non-zero bit (i.e., the leftmost bit): 
   
     
       
             
             
           
             
           
             
             
           
             
           
         
             
                 
                 
             
           
           
             
                 
               /* Constants */ 
             
             
                 
               MaskHi8 = 0xFF00 
             
             
                 
               MaskHi4 = 0xF0F0 
             
             
                 
               MaskHi2 = 0xCCCC 
             
             
                 
               MaskHi1 = 0xAAAA 
             
             
                 
               shifted_value = original_value &gt;&gt; 1 
             
             
                 
               /* Since there are no data dependencies between each 
             
             
                 
               * of the next four lines, they can each be executed 
             
             
                 
               * in parallel 
             
             
                 
               */ 
             
             
                 
               p4 = (MaskHi 8 &amp; original value) &gt; shifted_value 
             
             
                 
               p3 = (MaskHi 4 &amp; original value) &gt; shifted_value 
             
             
                 
               p2 = (MaskHi 2 &amp; original value) &gt; shifted_value 
             
             
                 
               p1 = (MaskHi 1 &amp; original value) &gt; shifted_value 
             
             
                 
               /* The line below may be a single instruction, a 
             
           
        
         
             
               ‘broadside’ load of the predicate registers 
             
           
        
         
             
                 
               */ 
             
             
                 
               HighBitIndex = (p4 &lt;&lt; 3) + (p3 &lt;&lt; 2) + (p2 &lt;&lt; 2) + 
             
           
        
         
             
               (p1) 
             
             
                 
             
           
        
       
     
   
   While the present invention has been described with respect to a limited number of embodiments, those skilled in the art will appreciate numerous modifications and variations therefrom. It is intended that the appended claims cover all such modifications and variations as fall within the true spirit and scope of this present invention.

Technology Category: 3