Re: is this portable?

[=?iso-8859-1?Q?=D8yvind_R=F8tvold?=]

"copx" <co**@gazeta.plwrites:

"Thad Smith" <Th*******@acm.orgschrieb im Newsbeitrag
news:48***********************@auth.newsreader.oct anews.com...

>copx wrote:

[ ... ]

>>
for (p2 = 1; p2 && p2 <= x; p2 *= 2) ;

Yes, that is a straight forward and safe way to do it, but I want this to
work really fast. That's the reason why I searched for some bit vodoo in the
first place.

What Thad is getting at here is that this the solution you found
simply does not fit your requirements, whether it is portable or
effective is thus irrelevant, tell us wheter your requirements are :

"to round up any given integer to the next power of two"

As you initially state, or :

"to round a number (x) to the next multiple of "a", where "a" is a
power of 2"
As indicated by the solution you found, those two are not the same.
If the first are your requirements you would probably need to isolate
the most significant bit set in x, this is a O(log N) operation, and
then shift that left.

Thad's solution is O(N)

Something like (for 32 bit):

a = x&0xffff0000 ; if (a) x=a; /* in upper half? */
a = x&0xff00ff00 ; if (a) x=a; /* in upper half of that */
( The rest is left as an excercise for the reader :-)
x = x << 1;

This is straight from the back of my head so don't take it at face
value. If it works at all it will be for unsigned only.

I'm not sure if this qualifies as woodoo though.

--
... __o Øyvind
... _`\(, http://www.darkside.no/olr/
... (_)/(_) ... biciclare necesse est ...

[=?iso-8859-1?Q?=D8yvind_R=F8tvold?=]

ol*@218.80-202-60.ne (Øyvind Røtvold) writes:

[ ... ]

>
a = x&0xffff0000 ; if (a) x=a; /* in upper half? */
a = x&0xff00ff00 ; if (a) x=a; /* in upper half of that */
( The rest is left as an excercise for the reader :-)
x = x << 1;

I suppose I should mention the singularities her:

If x has MSB set the result will be shifted out (if x is a 32 bit
type) leaving the result 0.

If x is already a power of two it will still be rounded up to the next
power of two, this is what the spec says, but may not be what is
intended, subtract 1 at the start if thats the case.

If x is 0, result will be 0, the correct result should probably be 1

--
... __o Øyvind
... _`\(, http://www.darkside.no/olr/
... (_)/(_) ... biciclare necesse est ...

[orotvold]

On Apr 12, 9:20*am, [e-mail] (Øyvind Røtvold) wrote:
[snip]

[snip]

*"to round up any given integer to the next power of two"

[ snip ]

Something like (for 32 bit):

a = x&0xffff0000 ; if (a) x=a; */* in upper half? */
a = x&0xff00ff00 ; if (a) x=a; */* in upper half of that */
( The rest is left as an excercise for the reader :-)
x = x << 1;

This is straight from the back of my head so don't take it at face
value. *If it works at all it will be for unsigned only.

at : http://graphics.stanford.edu/~seande...tml#IntegerLog

You can find some solutions, this:

x |= x >1; // first round down to power of 2
x |= x >2;
x |= x >4;
x |= x >8;
x |= x >16;
x += 1;

Should do the trick, and don't involve any branching.

--
.. __o Øyvind
.. _`\(, http://www.darkside.no/olr/
.. (_)/(_) ... biciclare necesse est ...