Browse Prior Art Database

SEARCH FIRST BIT SET

IP.com Disclosure Number: IPCOM000036983D
Original Publication Date: 1989-Nov-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Harper, RW: AUTHOR

Abstract

The invention disclosed identifies a method to find the bit number of the most significant bit set in a word. It utilizes the fixed-to- float instruction found on many processors. To find the bit number of the most significant bit set in a 16-bit word, for example, the following steps are performed: 1. Assume the most significant bit (MSB) is numbered 0 and least significant bit (LSB) is numbered 15. Note: If the bits are numbered in the reverse order, see the alternate method below. 2. If the input value is positive (bit 0 is not set), then a. Convert input value to floating point number. b. Exclusive-OR resulting exponent with 1s (i.e., 0000 1111 for 16-bit word, 0001 1111 for 32-bit word, etc. c. Continue normal processing.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 62% of the total text.

Page 1 of 2

SEARCH FIRST BIT SET

The invention disclosed identifies a method to find the bit number of the most significant bit set in a word. It utilizes the fixed-to- float instruction found on many processors. To find the bit number of the most significant bit set in a 16-bit word, for example, the following steps are performed: 1. Assume the most significant bit (MSB) is numbered

0 and least significant bit (LSB) is numbered 15.

Note: If the bits are numbered in the reverse

order, see the alternate method below.

2. If the input value is positive (bit 0 is not set),

then

a. Convert input value to floating point number.

b. Exclusive-OR resulting exponent with 1s

(i.e., 0000 1111 for 16-bit word, 0001 1111

for 32-bit word, etc.

c. Continue normal processing. Result is in

register.

3. If the input value is negative (bit 0 set), then

a. Set register to bit number of MSB (=0).

b. Continue normal processing. Result is in

register.

4. If the input value is zero, then

a. Indicate no bits set in input value (i.e.,

set register to -1).

b. Continue normal processing. Indication that

no bits set is in register.

Example: In this example, bit 0 is the MSB and bit 15 is the LSB. Find the highest bit set in the word 0000 0000 0011 1010. First check if the word is negative. If it had been, bit 0 would have been the most significant bit set. Otherwise, obtain the floating-point exponent (normalize the value), resulting in a mantissa of 1110 1000 0000 0000 with an exponent equal to 0000 0110.

Now perform the exclusive-OR (XOR) of the exponent with 0000 1111, and this results in 0000 1001. Add 1 and the result is 0000 1010, which is equal to
10.

This means that bit position 10 in the 16-bit input word is the location of the highest bit set in the word. Sample Implementation SEARCH FIRST BIT SET

** EXAMPLE FOR 1750A MIL-STD PROCESSOR

**

CNTO CSECT

**

** ASSUME R1 HAS INPUT FIELD

** ASSUME R1 IS OUTPUT COUNT OR NO BIT SET IF NEGATIVE

** ASSUME R0 IS TRASHED

**

BEGIN EQU *

1

Page 2 of 2

LR R1,R1 SET CONDITION CODES FOR INPUT VALUE

BLE LEQZERO BRANCH IF NEGATIVE OR ZERO

FLT R0,R1 CONVERT INPUT VALUE TO FLOATING POINT

XORM R1,15...