Re: Best way to emulate BSR?


"randyhyde@xxxxxxxxxxxxx" <spamtrap@xxxxxxxxxx> schrieb im Newsbeitrag
news:1156306664.096217.41660@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Jim Leonard wrote:
I have a need to determine the minimum number of bits to hold a certain
number, and BSR looks like a great way to do that. Unfortunately, the
target platform for this project does not support 386 instructions like
BSR. Is there a bitwise trick on emulating BSR?


Emulating BSR involves 2 steps:

Step I. Finding the next power of 2
Step II. Count the number of trailing zeroes

____


Step I. Finding the next power of 2

The minimum number of needed bits is the next power of 2 of your maximum
number. Because 2**n-1 is of the

form 0...01...1b, you can add 1 to get the next power of 2. The immediate
goal is to convert your number

into the form 0...01...1b.

Shifting any number to the right and ORing with the previous result, you get
more or the same number of set

bits to the right of the MSB, but the left of the MSB remains clear. Doing
this with a shift width of

1,2,4,8... bits leaves you with the desired form 0...01...1b.

(Sample bitstreams)
(a) (b) (c)
B := A (1000 1001 1111)
B rightshift 1 (0100 0100 0111)
A or B (1100 1101 1111)

B := A
B rightshift 2 (0011 0011 0011)
A or B (1111 1111 1111)

(etc., repeat with rightshift values 4, 8, 16 for 32 bit values; also with
32 if you have 64 bit values)

Now it's easy to get the next power of 2:

A + 1 (10000 = next power of 2)

Note, that you will have an overflow if Bit 31 was set prior the addition.
That does no harm, as A will contain 0 then, which is OK for the input into
step II.

Also note, that there are other ways to find the next power of 2. E.g.:
http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2Float

____


Step II. Count the number of trailing zeroes.

There is a variety of ways to do so. Check out 5 possibilities at
http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel

Hope it helped
//Herbert Glarner

.