Thread
-
Off topic 'C' question
Mike Mascari <mascarm@mascari.com> — 2000-07-30T01:38:33Z
I have a quick question. What is the quickest way to determine the next highest power of two which is greater than a given integer in 'C'. For example, given the number 7, I would like to return 8. Given the number 13, I would like to return 16, etc. Is there a gem to do this without shifting a bit value from 1 left up to a maximum of 32 (or 64) iterations? Thanks for any info, Mike Mascari
-
Re: Off topic 'C' question
Alfred Perlstein <bright@wintelcom.net> — 2000-07-30T03:26:22Z
* Mike Mascari <mascarm@mascari.com> [000729 18:40] wrote: > I have a quick question. What is the quickest way to determine > the next highest power of two which is greater than a given > integer in 'C'. For example, given the number 7, I would like to > return 8. Given the number 13, I would like to return 16, etc. Is > there a gem to do this without shifting a bit value from 1 left > up to a maximum of 32 (or 64) iterations? > > Thanks for any info, Think "binary search". -Alfred
-
Re: Off topic 'C' question
Mike Mascari <mascarm@mascari.com> — 2000-07-30T05:05:51Z
Alfred Perlstein wrote: > > * Mike Mascari <mascarm@mascari.com> [000729 18:40] wrote: > > I have a quick question. What is the quickest way to determine > > the next highest power of two which is greater than a given > > integer in 'C'. For example, given the number 7, I would like to > > return 8. Given the number 13, I would like to return 16, etc. Is > > there a gem to do this without shifting a bit value from 1 left > > up to a maximum of 32 (or 64) iterations? > > > > Thanks for any info, > > Think "binary search". > > -Alfred Yeah. Start with 2^16, check if larger. If so, check 2^8, etc. In Graphics Gems II, there's an algorithm by Ken Shoemake for finding the lowest 1-bit set. You take the bit-wise AND of the word and its negative -- that easy. I was hoping something similar existed for finding the highest bit set. If so, I could just shift the result left one. If not, if there's a way to flip the bits in an unsigned integer without barrel shifting, then all I would have to do is: flip take bit-wise AND with negative flip shift left 1 The binary search, is of course, better then brute force, but can be worse than linear for low values. For example, a search for 2^5 would yield: 2^16 2^0 2^8 2^4 2^6 2^5 or 6 iterations instead of 5, plus the actual shifting of the search value. I guess I was hoping for some "bit-magic" out there. Cheers, Mike Mascari
-
Re: Off topic 'C' question
Jan Wieck <janwieck@t-online.de> — 2000-07-30T11:28:38Z
Mike Mascari wrote: > I have a quick question. What is the quickest way to determine > the next highest power of two which is greater than a given > integer in 'C'. For example, given the number 7, I would like to > return 8. Given the number 13, I would like to return 16, etc. Is > there a gem to do this without shifting a bit value from 1 left > up to a maximum of 32 (or 64) iterations? Binary search. I assumed you really mean greater than, so that next_power2(4096) is 8192. For 32 bit values, the function unsigned int next_power2_32 (unsigned int value) { unsigned int comp = 1 << 16; unsigned int off = 8; if (value == 0) return 1; while (off > 0 && comp != value) { if (comp > value) comp >>= off; else comp <<= off; off >>= 1; } if (comp <= value) comp <<= 1; return comp; } is guaranteed to have at maximum 4 loop iterations for any value you want. Should be polished up a little for values >= (1 << 31), but I leave that to you. Obviuosly, looking for 64 bit numbers, the loop max would be 5, and when we have 256 bit integers as standard (in approx. 5-6 years :-) it'll finish with 7 iterations. Jan -- #======================================================================# # It's easier to get forgiveness for being wrong than for being right. # # Let's break this rule - forgive me. # #================================================== JanWieck@Yahoo.com # -
Re: Off topic 'C' question
Louis-David Mitterrand <cunctator@apartia.ch> — 2000-08-11T21:18:23Z
On Sat, Jul 29, 2000 at 09:38:33PM -0400, Mike Mascari wrote: > I have a quick question. What is the quickest way to determine > the next highest power of two which is greater than a given > integer in 'C'. For example, given the number 7, I would like to > return 8. Given the number 13, I would like to return 16, etc. Is > there a gem to do this without shifting a bit value from 1 left > up to a maximum of 32 (or 64) iterations? You could use: pow(x, ((int)(log(x)/log(2)) + 1)); -- Louis-David Mitterrand - ldm@apartia.org - http://www.apartia.org "Poor girl looks as confused as a blind lesbian in a fish market." - Simon R. Green
-
Re: Re: Off topic 'C' question
Louis-David Mitterrand <cunctator@apartia.ch> — 2000-08-12T06:50:54Z
On Fri, Aug 11, 2000 at 11:18:23PM +0200, Louis-David Mitterrand wrote: > On Sat, Jul 29, 2000 at 09:38:33PM -0400, Mike Mascari wrote: > > I have a quick question. What is the quickest way to determine > > the next highest power of two which is greater than a given > > integer in 'C'. For example, given the number 7, I would like to > > return 8. Given the number 13, I would like to return 16, etc. Is > > there a gem to do this without shifting a bit value from 1 left > > up to a maximum of 32 (or 64) iterations? > > You could use: > > pow(x, ((int)(log(x)/log(2)) + 1)); Sorry the correct way is: #include <math.h> #include <stdio.h> #include <stdlib.h> int main(int argc, char ** argv) { int r = atoi(argv[1]); printf("result is %g\n", pow(2, (int)((log(r)/log(2)) + 1))); return 0; } This works for any power, simply replace 2 by the desired exponent. -- Louis-David Mitterrand - ldm@apartia.org - http://www.apartia.org