Bit shifting for log of 2

R

Rick

Hi,

I'm working on an implementation of a garbage collector (inside a write
barrier) where I can't use while or for loops.. I need to calculate the
log_2 of a number without using loops. Currently I was using a while
loop for counting the number of bits in a number, while bit shifting it
to the right. Is there some way to calculate log_2 without using a loop
of any kind? Thanks


Rick
 
R

Rick

To be precise.. I'm basically calculating the bounding logarithmic value
under which the number falls. For example, the number 0 falls under 2^1
(2).. similarly, the value 10 falls under 2^4 (16). Can I do this
wihtout using a while loop?

Thanks

Rick
 
A

Arthur J. O'Dwyer

To be precise.. I'm basically calculating the bounding logarithmic value
under which the number falls. For example, the number 0 falls under 2^1
(2).. similarly, the value 10 falls under 2^4 (16). Can I do this
wihtout using a while loop?

Why on earth would you want to do anything without using loops?

Hint: Use a lookup table.

-Arthur
 
C

Christian Bau

"Arthur J. O'Dwyer said:
Why on earth would you want to do anything without using loops?

Hint: Use a lookup table.

log2 = 0;
if (x >= 65536) { x >>= 16; log2 += 16; }
if (x >= 256) { x >>= 8; log2 += 8; }
log2 += table [x];

Modify to your requirements.
 
R

Rick

Why on earth would you want to do anything without using loops?

The write barrier needs to stay un-interrupted, and using loops allows
the scheduler to run different threads, which I dont want. The only way
around this is to do something that doesn't use a loop and a lookup
table is going to be too much work for a small write barrier :(


Rick
 
K

Keith Thompson

Rick said:
The write barrier needs to stay un-interrupted, and using loops allows
the scheduler to run different threads, which I dont want. The only
way around this is to do something that doesn't use a loop and a
lookup table is going to be too much work for a small write barrier :(

Does the scheduler distinguish between a backward branch (i.e., a
loop) and a forward branch (e.g., an if/else)? If you can't use
conditional branches, there may not be a good solution.

(The details of how your scheduler words are probably off-topic; I'm
just trying to nail down your requirements.)
 
M

Martijn

Rick said:
The write barrier needs to stay un-interrupted, and using loops allows
the scheduler to run different threads, which I dont want. The only
way around this is to do something that doesn't use a loop and a
lookup table is going to be too much work for a small write barrier :(

I think you have to use semaphores anyway. I don't know anything about your
implementation, but unless you are really coding this in assembler, there is
no way of knowing whether your operation is "atomic", i.e. can not be
interrupted.
 
M

Mathew Hendry

To be precise.. I'm basically calculating the bounding logarithmic value
under which the number falls. For example, the number 0 falls under 2^1
(2).. similarly, the value 10 falls under 2^4 (16). Can I do this
wihtout using a while loop?

/* for unsigned 32-bit n, n <- 2^ceil(lg(n)) */
n--;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n++;

-- Mat.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,480
Members
44,900
Latest member
Nell636132

Latest Threads

Top