tag:blogger.com,1999:blog-2032635359859599977.post7096014988743489069..comments2012-03-15T10:46:26.975-07:00Comments on Acius' Snippets: Calculating the next power of 2Adam Helpshttps://plus.google.com/103345826169309515886noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-2032635359859599977.post-89014414150881852002012-03-14T22:09:24.487-07:002012-03-14T22:09:24.487-07:00Just a note to @Clemens -- Yes, that method should...Just a note to @Clemens -- Yes, that method should work, but how fast is it? You're going to take a speed hit for moving into and out of the floating point registers. I haven't checked, but I'm guessing the method in the post is going to win on speed.<br /><br />Also: This is a very, very late reply (four years later!)Adam Helpshttps://www.blogger.com/profile/06811952192778510355noreply@blogger.comtag:blogger.com,1999:blog-2032635359859599977.post-13027582542125166942011-08-16T08:50:02.628-07:002011-08-16T08:50:02.628-07:00@Clemens - You can use bit shifting to avoid the c...@Clemens - You can use bit shifting to avoid the call to pow. int next_pow = 1 << ceil(log2((double)val));Wallacoloohttps://www.blogger.com/profile/08935819590865336014noreply@blogger.comtag:blogger.com,1999:blog-2032635359859599977.post-70561654827107388512010-12-18T22:53:04.729-08:002010-12-18T22:53:04.729-08:00Also, to explain his final notes to those not fami...Also, to explain his final notes to those not familiar with how computers store numbers and/or do math:<br /><br />I'll convert math down to the bit-level. I assume that you know C's bitwise operators. I'm using an imaginary primitive to represent bits and an imaginary macro to get a bit from any integer. For those with no imagination, I have included macros to make them real.<br /><br />#if (YOU_HAVE_NO_IMAGINATION)<br /> #define bit int<br /> #define getbit(var, num) (((var)&1<<(num))>>(num))<br />#endif<br /> <br />bit subbits(bit a, bit b, bit* carry)<br />{<br /> /* The difference between the bits */<br /> bit diff = (a ^ b);<br /> /* Factor in the carry */<br /> bit result = (diff ^ *carry);<br /> /* Calculate the next carry */<br /> *carry = ((~a & b) | (~diff & carry));<br /> return result;<br />}<br /><br />byte subbytes(byte a, byte b)<br />{<br /> /* carry is intially zero */<br /> bit carry = 0;<br /> byte result = 0;<br /> /* each bit in the byte */<br /> for(int i = 0; i < 8; ++i)<br /> {<br /> /* get the corresponding bit */<br /> bit ba = getbit(a, i);<br /> bit bb = getbit(b, i);<br /> /* do the subtraction */<br /> result |= subbits(a, b, &carry) << i;<br /> }<br /> return result;<br />}<br /><br />bit addbits(bit a, bit b, bit* carry)<br />{<br /> /* The difference between the bits */<br /> bit diff = (a ^ b);<br /> /* Factor in the carry */<br /> bit result = (diff ^ *carry);<br /> /* Calculate the next carry */<br /> *carry = ((a & b) | (diff & carry));<br /> return result;<br />}<br /><br />byte addbytes(byte a, byte b)<br />{<br /> /* carry is intially zero */<br /> bit carry = 0;<br /> byte result = 0;<br /> /* each bit in the byte */<br /> for(int i = 0; i < 8; ++i)<br /> {<br /> /* get the corresponding bit */<br /> bit ba = getbit(a, i);<br /> bit bb = getbit(b, i);<br /> /* do the subtraction */<br /> result |= addbits(a, b, &carry) << i;<br /> }<br /> return result;<br />}<br /><br />If you build and run these functions (assuming of course they build; haven't tested, but it should be suitable as example still), you'll notice that adding 1 to 11111111 will produce 0 and subtracting 1 from 0 will produce 11111111. You'll also notice that the variable named "carry" is ignored after the 8th bit (i==7). Computer hardware does the same thing, it ignores the carry bit (in the case of intel processors, its actually a bit in the EFLAGS register). When you do math in your head, you can carry beyond the original number of digits in the number. The computer is not capable of carrying beyond the number of bits in the number. In Java, I believe the result would be an overflow exception. In C and C++, however, the number's value silently shifts from 0 to 11111111 or vice-verse.<br /><br />...perhaps the code snippet is not required for the explanation? Oh well. :Pnfries88https://www.blogger.com/profile/05426788959714931989noreply@blogger.comtag:blogger.com,1999:blog-2032635359859599977.post-51576639224676569112010-12-18T21:00:35.785-08:002010-12-18T21:00:35.785-08:00Sayantan, use the unfinished one to get the result...Sayantan, use the unfinished one to get the results you want.nfries88https://www.blogger.com/profile/05426788959714931989noreply@blogger.comtag:blogger.com,1999:blog-2032635359859599977.post-46258077216803408302010-11-04T09:58:16.991-07:002010-11-04T09:58:16.991-07:00This algorithm doesn't work if the input numbe...This algorithm doesn't work if the input number is already a power of 2.<br /><br />E.g. if input number is 32, i would expect 64 as the output. But it always returns 32.Sayantanhttps://www.blogger.com/profile/07687902434612760169noreply@blogger.comtag:blogger.com,1999:blog-2032635359859599977.post-25015540819175146592009-11-29T03:13:34.372-08:002009-11-29T03:13:34.372-08:00@Clemens
Thank you, thats what im looking for :D@Clemens<br /><br />Thank you, thats what im looking for :DNiklashttps://www.blogger.com/profile/01329401197334102295noreply@blogger.comtag:blogger.com,1999:blog-2032635359859599977.post-17426017793181439282008-05-18T21:57:00.000-07:002008-05-18T21:57:00.000-07:00Hey, another possibility is to first convert the n...Hey, <BR/><BR/>another possibility is to first convert the number to a double, then doing <BR/><BR/>double vald = (double)val;<BR/>int next_pow = (int)pow(ceil(log2(vald)),2);<BR/><BR/>The idea is: We compute the 2-base logarithm of our number, say it's x. Then we now pow(2,x) will give the number itself. Rounding x to the next integer with ceil(x), pow will give the next integer power of 2. Yay :)Clemenshttps://www.blogger.com/profile/15559142083757563826noreply@blogger.com