Binary power C algorithm
Carlos Portela
I am looking for an efficient algorithm to find the smallest power of 2
that contains a number. For example, given 511 it would return 9
corresponding to 512, and given 33 it would return 6 corresponding to
64.
I remember seeing a macro in a header file for the Mach kernel or maybe
the Linux kernel but I can't find now. As I recall they found the 1's
complement of the number, subtracted 1 from it, and then ...
Thank you in advance!
--
Carlos Portela, Simple Software Solutions, Inc.
e_Db 2.1 - Fast, reliable database engine
e_Fs 2.0 - Portable structured storage
e_Comm 2.0 - Client-server communications
http://www.simple-sw.com
--
comp.lang.c.moderated - cl...@plethora.net
Dann Corbit
int log2est(unsigned long n)
{
register int i = (n & 0xffff0000) ? 16 : 0;
if ((n >>= i) & 0xff00)
i |= 8, n >>= 8;
if (n & 0xf0)
i |= 4, n >>= 4;
if (n & 0xc)
i |= 2, n >>= 2;
return (i | (n >> 1));
}
--
Hypertext C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
C-FAQ ftp: ftp://rtfm.mit.edu, C-FAQ Book: ISBN 0-201-84519-9
Try "C Programming: A Modern Approach" ISBN 0-393-96945-2
Want Software? Algorithms? Pubs? http://www.infoseek.com
Carlos Portela wrote in message ...
--
comp.lang.c.moderated - cl...@plethora.net
wroth
>I am looking for an efficient algorithm to find the smallest power of 2
>that contains a number. For example, given 511 it would return 9
>corresponding to 512, and given 33 it would return 6 corresponding to
>64.
This is what I generally use:
unsigned long mask=1, numBits=1;
while(mask<num) {
mask+=mask;
numBits++;
}
When the loop exits, the number of bits is stored in numBits.
-W. Roth
wr...@cris.com
--
comp.lang.c.moderated - cl...@plethora.net
Charles LaCour
have to provide your own error-checking and limit control.
#include <stdio.h>
int main( void )
{
unsigned int max, num = 33;
for ( max = 1; max < num; max <<= 1 )
;
printf( "The smallest power of 2 larger than %d is: %d\n", num, max );
return 0;
}
--
Increase the Peace!
Charles LaCour
cla...@mci2000.com
Carlos Portela wrote in message ...
>Hi All,
>
>I am looking for an efficient algorithm to find the smallest power of 2
>that contains a number. For example, given 511 it would return 9
>corresponding to 512, and given 33 it would return 6 corresponding to
>64.
>
Lew Pitcher
>Hi All,
>
>I am looking for an efficient algorithm to find the smallest power of 2
>that contains a number. For example, given 511 it would return 9
>corresponding to 512, and given 33 it would return 6 corresponding to
>64.
>
>I remember seeing a macro in a header file for the Mach kernel or maybe
>the Linux kernel but I can't find now. As I recall they found the 1's
>complement of the number, subtracted 1 from it, and then ...
>
>Thank you in advance!
>--
>Carlos Portela, Simple Software Solutions, Inc.
>e_Db 2.1 - Fast, reliable database engine
>e_Fs 2.0 - Portable structured storage
>e_Comm 2.0 - Client-server communications
>http://www.simple-sw.com
>--
>comp.lang.c.moderated - cl...@plethora.net
Although this is not a C question/problem (rather, it's an algorithm question),
a quick answer might suffice...
Think of your number expressed in binary (with hi-order bit on the left).
Number each bit (from right to left), starting at 2
The 'number' of the highest bit will be the smallest power of 2 that corresponds
to the number.
Visually...
decimal 33 = binary 0001 0001
bit mask is.........9876 5432
highest bit is at....../
which is bit 'number' 6
which means that 6 is the smallest power of 2 that contains the number.
Now... express this as a C function, and we'll all be happy
(Hint #1: you can use an if() stmt in a for(;;) loop)
(Hint #2: start at the hi order bit of the number)
Caveat: Your solution can be expressed in platform-independant Standard C with
the use of various C standard header files. Please use them.
Lew Pitcher
System Consultant, Delivery Systems Architecture
Toronto Dominion Bank
(Opinions expressed are my own, not my employer's.)
--
comp.lang.c.moderated - cl...@plethora.net
cbfal...@my-dejanews.com
cpor...@simple-sw.com wrote:
> Hi All,
>
> I am looking for an efficient algorithm to find the smallest power of 2
> that contains a number. For example, given 511 it would return 9
> corresponding to 512, and given 33 it would return 6 corresponding to
> 64.
All you need to find is the bit position of the leftmost 1 bit of the number.
You can certainly find more efficient coding, but in essence:
n = number;
bp = 0;
do
bp++
while (n = (n >> 1));
should do it. Returns 1 for number = 0 or 1, 2 for 2 or 3, 3 for 4..7, etc.
Modify according to the actual truth table you need. If you replace (n>>1)
by integer division by 2 nothing depends on the underlying numeric
representation, as long as it is integral.
--
Chuck Falconer (Charles_...@NOSPAMapsnet.com)
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum
--
comp.lang.c.moderated - cl...@plethora.net
Carlos Portela
> >that contains a number. For example, given 511 it would return 9
> >corresponding to 512, and given 33 it would return 6 corresponding to
> >64.
>
>
> unsigned long mask=1, numBits=1;
> while(mask<num) {
> mask+=mask;
> numBits++;
> }
>
> When the loop exits, the number of bits is stored in numBits.
>
> -W. Roth
> wr...@cris.com
> --
> comp.lang.c.moderated - cl...@plethora.net
Thank you, it works. I was hoping there was a solution that simply
involved bit manipulations like AND. OR, XOR, etc. I was trying to avoid
writing loops but I guess this is the only solution.
Thanks a lot
Carlos Portela
>
> Although this is not a C question/problem (rather, it's an algorithm question),
> a quick answer might suffice...
>
> Think of your number expressed in binary (with hi-order bit on the left).
> Number each bit (from right to left), starting at 2
> The 'number' of the highest bit will be the smallest power of 2 that corresponds
> to the number.
>
> Visually...
>
> decimal 33 = binary 0001 0001
>
> bit mask is.........9876 5432
> highest bit is at....../
> which is bit 'number' 6
> which means that 6 is the smallest power of 2 that contains the number.
>
> Now... express this as a C function, and we'll all be happy
> (Hint #1: you can use an if() stmt in a for(;;) loop)
> (Hint #2: start at the hi order bit of the number)
>
Hi Lew,
Thank you for the explanation and for pointing out my potentially
inappropriate posting.
Regards,
Carlos Portela
>
> There are probably some better algorithms, but this one will work. You'll
> have to provide your own error-checking and limit control.
>
> #include <stdio.h>
>
> int main( void )
> {
> unsigned int max, num = 33;
>
> for ( max = 1; max < num; max <<= 1 )
> ;
>
> printf( "The smallest power of 2 larger than %d is: %d\n", num, max );
>
> >that contains a number. For example, given 511 it would return 9
> >corresponding to 512, and given 33 it would return 6 corresponding to
> >64.
> >
> >the Linux kernel but I can't find now. As I recall they found the 1's
> >complement of the number, subtracted 1 from it, and then ...
> >
Thanks to you and to all who have responded. I still would love to hear
from somebody who has a solution that does not involve a loop, that is,
some sort of macro that ORs and XORs and ANDs, etc. I am pretty sure I
have seen something like that in a header file for either Linux or Mach
kernel.
Thanks a lot!
wroth
>On Tue, 25 Aug 1998 00:30:49 GMT, Carlos Portela <cpor...@simple-sw.com> wrote:
>>that contains a number. For example, given 511 it would return 9
>>corresponding to 512, and given 33 it would return 6 corresponding to
>>64.
>
>
>unsigned long mask=1, numBits=1;
>while(mask<num) {
> mask+=mask;
> numBits++;
> }
Oops, this doesn't quite work. Change it to:
unsigned long mask=2, numBits=1;
while(mask<num) {
mask+=mask;
numBits++;
}
There, that's much better.
Lawrence Kirby
cla...@MCI2000.com "Charles LaCour" writes:
>There are probably some better algorithms, but this one will work. You'll
>have to provide your own error-checking and limit control.
>
>#include <stdio.h>
>
>int main( void )
>{
> unsigned int max, num = 33;
>
> for ( max = 1; max < num; max <<= 1 )
> ;
>
> printf( "The smallest power of 2 larger than %d is: %d\n", num, max );
>
> return 0;
>}
The return value for 33 was specified as 6, not 64. There is also a problem
here for large values of num i.e. where the top bit and at least one other
bit is set: the code goes into an infinite loop.
>Carlos Portela wrote in message ...
>>Hi All,
>>
>>I am looking for an efficient algorithm to find the smallest power of 2
>>that contains a number. For example, given 511 it would return 9
>>corresponding to 512, and given 33 it would return 6 corresponding to
>>64.
So you want the bit position/log value rather than the actual power of 2.
Is this required to work for all possible unsigned int values (i.e.
right up to UINT_MAX)? Do exact powers of 2 ``contain'' themselves (e.g.
is the result for 512 9 rather than 10?). What should the result be for 0?
(0 I guess but it is worth stating the special cases to remove any doubt).
>>I remember seeing a macro in a header file for the Mach kernel or maybe
>>the Linux kernel but I can't find now. As I recall they found the 1's
>>complement of the number, subtracted 1 from it, and then ...
There is a trick for isolating the *lowest* order bit like this:
unsigned num = VALUE;
unsigned lobit;
lobit = value & (~value+1);
which can be simplified to
lobit = value & -value;
So if VALUE is 12 then lobit gets set to 4. There's no simple equivalent
to get the high order bit (there may be platform-specific methods e.g.
making use of specialised processor instructions on that platform).
--
-----------------------------------------
Lawrence Kirby | fr...@genesis.demon.co.uk
Wilts, England | 7073...@compuserve.com
-----------------------------------------
--
comp.lang.c.moderated - cl...@plethora.net
Ben Pfaff
Hi All,
I am looking for an efficient algorithm to find the smallest power of 2
that contains a number. For example, given 511 it would return 9
corresponding to 512, and given 33 it would return 6 corresponding to
64.
I believe that we had a thread about this a while ago. You might want
to search around using DejaNews.
--
comp.lang.c.moderated - cl...@plethora.net
Mathew Hendry
> Thanks to you and to all who have responded. I still would love to hear
> from somebody who has a solution that does not involve a loop, that is,
> some sort of macro that ORs and XORs and ANDs, etc.
#define hi_bit(n)\
((n)>=1<<16?(n)>=1<<24?(n)>=1<<28?(n)>=1<<30?(n)>=1<<31?31:30:(n)>=1<<29?\
29:28:(n)>=1<<26?(n)>=1<<27?27:26:(n)>=1<<25?25:24:(n)>=1<<20?(n)>=1<<22?\
(n)>=1<<23?23:22:(n)>=1<<21?21:20:(n)>=1<<18?(n)>=1<<19?19:18:(n)>=1<<17?\
17:16:(n)>=1<<8?(n)>=1<<12?(n)>=1<<14?(n)>=1<<15?15:14:(n)>=1<<13?13:12:(\
n)>=1<<10?(n)>=1<<11?11:10:(n)>=1<<9?9:8:(n)>=1<<4?(n)>=1<<6?(n)>=1<<7?7:\
6:(n)>=1<<5?5:4:(n)>=1<<2?(n)>=1<<3?3:2:(n)>=1<<1?1:(n)>=1<<0?0:-1)
This turns out to be pretty fast, despite its ugliness. It's a binary search:
5 comparisons.
But if when you said "no loops" you really meant "no conditionals", try,
int
hi_bit23(unsigned long n){
static const int t[]={
-1,0,25,1,22,26,31,2,15,23,29,27,10,-1,12,3,6,16,
-1,24,21,30,14,28,9,11,5,-1,20,13,8,4,19,7,18,17};
return t[(n|=n>>1,n|=n>>2,n|=n>>4,n|=n>>8,n|=n>>16)%37];
}
Not a macro, I'm afraid, but you can't have everything. :)
-- Mat.
--
comp.lang.c.moderated - cl...@plethora.net
Doug Moore
: Hi All,
:
: I am looking for an efficient algorithm to find the smallest power of 2
: that contains a number. For example, given 511 it would return 9
: corresponding to 512, and given 33 it would return 6 corresponding to
: 64.
Provided that your machine uses IEEE floating point and has 32-bit ints,
this code will work. At least, it does on my computer.
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
int lg(int x)
{
float xf = x-1;
return ((*(int*)&xf) >> 23) - 126;
}
main(int argc, char** argv)
{
if (argc != 2) exit(-1);
printf("%d\n", lg(atoi(argv[1])));\
}
The compiled assembly code (on a Sun) is only 8 instructions:
! SUBROUTINE lg
!
! OFFSET SOURCE LINE LABEL INSTRUCTION
.global lg
lg:
/* 000000 */ save %sp,-104,%sp
! FILE hack.c
! 1 !#include <math.h>
! 2 !#include <stdio.h>
! 3 !#include <stdlib.h>
! 5 !int lg(int x)
! 6 !{
! 7 ! float xf = x-1;
/* 0x0004 7 */ sub %i0,1,%o0
/* 0x0008 */ st %o0,[%sp+92]
/* 0x000c */ ld [%sp+92],%f2
/* 0x0010 */ fitos %f2,%f2
/* 0x0014 */ st %f2,[%fp-4]
! 8 ! return ((*(int*)&xf) >> 23) - 126;
/* 0x0018 8 */ ld [%fp-4],%o0
/* 0x001c */ sra %o0,23,%o0
/* 0x0020 */ sub %o0,126,%i0
/* 0x0024 */ ret
/* 0x0028 */ restore %g0,%g0,%g0
/* 0x002c 0 */ .type lg,2
/* 0x002c */ .size lg,(.-lg)
The more usual definition of base 2 log, with "x" replacing "x-1" and "127"
replacing "126" above, requires one fewer instruction.
Doug Moore
(do...@caam.rice.edu)
--
comp.lang.c.moderated - cl...@plethora.net
Lawrence Kirby
do...@caam.rice.edu "Doug Moore" writes:
>Carlos Portela (cpor...@simple-sw.com) wrote:
>: Hi All,
>:
>: I am looking for an efficient algorithm to find the smallest power of 2
>: that contains a number. For example, given 511 it would return 9
>: corresponding to 512, and given 33 it would return 6 corresponding to
>: 64.
>
>Provided that your machine uses IEEE floating point and has 32-bit ints,
>this code will work. At least, it does on my computer.
The code also assumes that the floats and ints are formatted with
``equivalent'' byte orders which the standards don't guarantee.
Gary E. Shay, Jr.
>that contains a number. For example, given 511 it would return 9
>corresponding to 512, and given 33 it would return 6 corresponding to
>64.
Ok, Carlos, I'm going to give this one a shot since I did so well on the
other code problem (see "intractable" above)...
Here's your function.
Private int findPow(int x)
{
return (!x?0:findPow((x>>1))+1);
}
You didn't specify whether 32 would return 5 or 6, so this function returns
6 (32 does not contain itself - it fills it perfectly). In other words, it
gives you the min(2^n)>X. Even a 32 bit number would only require 32 levels
deep of recursion maximum...
exp = findPow(X); /* returns 6 for X=32 */
exp = findPow(X-1); /* returns 5 for X=32 */
This will NOT work for X < 0. You could put a check before the return that
handles negative numbers. You could also use a long int as the parameter -
your choice.
Hope this, at least, isn't too bad - I have a reputation to salvage!
--
+------------------------------------+-------------------------------+
| Gary E. Shay, Jr. | sha...@apci.com |
| Air Products and Chemicals, Inc. | http://www.airproducts.com |
+------------------------------------+-------------------------------+
| Opinions are like brains - everyone's got one, but they're not all |
| intelligent, educated, or enlightened. This one's mine, not AP's. |
+--------------------------------------------------------------------+
--
comp.lang.c.moderated - cl...@plethora.net
Carlos Portela
> Here's your function.
>
> Private int findPow(int x)
> {
> return (!x?0:findPow((x>>1))+1);
> }
>
Hi Gary,
Your reputation has been salvaged!
Thanks for the response.
Peter Seebach
Carlos Portela <cpor...@simple-sw.com> wrote:
>I am looking for an efficient algorithm to find the smallest power of 2
>that contains a number. For example, given 511 it would return 9
>corresponding to 512, and given 33 it would return 6 corresponding to
>64.
Well, for unsigned x, you could use
(x ^ (x & (x - 1))) << 1;
Why?
x & (x - 1)
is "everything in x except the top bit".
x ^ (x & (x - 1))
is thus "the top bit of x".
Therefore, <<'d 1, it's twice the top bit of x, or the next bit over.
Of course, for x=2^n (for integer n), this gives you 2x when you probably
only want x. I leave this as an exercise for the reader; perhaps something
like
if (x & (x - 1))
return (x ^ (x & (x - 1))) << 1;
else
return x ^ (x & (x - 1));
but I'm sure you can improve on this.
-s
--
Copyright 1998, All rights reserved. Peter Seebach / se...@plethora.net
C/Unix wizard, Pro-commerce radical, Spam fighter. Boycott Spamazon!
Seeking interesting programming projects. Not interested in commuting.
Visit my new ISP <URL:http://www.plethora.net/> --- More Net, Less Spam!
--
comp.lang.c.moderated - cl...@plethora.net
Mathew Hendry
wrote:
>In article <clcm-1998...@plethora.net>,
>Carlos Portela <cpor...@simple-sw.com> wrote:
>>I am looking for an efficient algorithm to find the smallest power of 2
>>that contains a number. For example, given 511 it would return 9
>>corresponding to 512, and given 33 it would return 6 corresponding to
>>64.
>
>Well, for unsigned x, you could use
> (x ^ (x & (x - 1))) << 1;
>
>Why?
> x & (x - 1)
>is "everything in x except the top bit".
No, it's "everything in x except the bottom bit". Thus,
x ^ (x & (x - 1))
gives the bottom bit. To find the top bit, you can use (assuming 32
bit unsigned x),
x|=x>>1, x|=x>>2, x|=x>>4, x|=x>>8, x|=x>>16;
x^=x>>1;
Peter Seebach
Peter Seebach <se...@plethora.net> wrote:
>Why?
> x & (x - 1)
>is "everything in x except the top bit".
I'd like to pretend I meant this to be an example, but really, I just screwed
up.
However, I think the way I did it might be instructive.
Behold, a way to emit the bits of a number:
void bprint(unsigned a) {
int i;
for (i = 0; i < 32; ++i) {
printf("%c", (a & 1) + '0');
a >>= 1;
}
}
Now, as will be obvious to the casual student, this will print 32 bits from
'a'. Unfortunately, it prints them in an order that was not the one I tried
to read them in.
Anyway, this serves as a great example of why you should *never* assert
"oh, I don't need to test this, it's just a one-off program". Always check
your work.
Carlos Portela
> Well, for unsigned x, you could use
> (x ^ (x & (x - 1))) << 1;
>
> x & (x - 1)
> is "everything in x except the top bit".
>
> Therefore, <<'d 1, it's twice the top bit of x, or the next bit over.
>
> Of course, for x=2^n (for integer n), this gives you 2x when you probably
> only want x. I leave this as an exercise for the reader; perhaps something
> like
> if (x & (x - 1))
> return (x ^ (x & (x - 1))) << 1;
> else
> return x ^ (x & (x - 1));
>
> but I'm sure you can improve on this.
>
> -s
> --
Thank you Peter!
I will try it tomorrow and let you know...
Regards,
wroth
>>Why?
>> x & (x - 1)
>>is "everything in x except the top bit".
>
Uh, no. x&1 gives the bottom bit. x^(x&(x-1)) does, however, indicate
the bottom bit that is set-a subtle but rather important distinction.
>bit unsigned x),
>
> x|=x>>1, x|=x>>2, x|=x>>4, x|=x>>8, x|=x>>16;
> x^=x>>1;
Are you sure this does something? If so, I can't tell what it is. If we
take x=16, for example, we end up with x=29 after the first line, and
29^14=19 after the second.
Carlos Portela
Hi W.
We tested the above code and it appears to work fine. In all honesty I
have not dedicated any time to understand how it works. I simply plugged
it in and it worked! This is how we are using it:
In the following example req_size contains the size requested by the
user.
We need to conver that to the smallest binary power that includes it,
that is, if they pass 513 we need to arrive to 1024, and if they pass 13
we better come back with 16.
register unsigned int bin_size;
// Determine smallest power of 2 that includes the
// requested size.
bin_size = req_size;
bin_size |= bin_size >> 1,
bin_size |= bin_size >> 2,
bin_size |= bin_size >> 4,
bin_size |= bin_size >> 8,
bin_size |= bin_size >> 16;
bin_size ^= bin_size >> 1;
if (bin_size < req_size)
bin_size <<= 1;
Unless we are missing something this code works fine. We tested all the
boundary cases as well as random cases and they all returned the proper
value. If you see something wrong with it please let me know. By the
way, the assembly code generated by the MS compiler is very efficient
Gary E. Shay, Jr.
Here's an "even better" solution to your question, as it more strictly meets
your original requirement - that the solution is a macro. Here goes:
#define binPow(a,b) for(a=0;((b-1)>>a)>0;a++)
Which is called thus:
...
int i;
...
binPow(i, ###);
...
For all values > 0, "i" will now contain the power of 2 that contains (is
greater than or equal to) ###.
G
--
+------------------------------------+-------------------------------+
| Gary E. Shay, Jr. | sha...@apci.com |
| Air Products and Chemicals, Inc. | http://www.airproducts.com |
+------------------------------------+-------------------------------+
| Opinions are like brains - everyone's got one, but they're not all |
| intelligent, educated, or enlightened. This one's mine, not AP's. |
+--------------------------------------------------------------------+
Gary E. Shay, Jr. wrote in message ...
>>I am looking for an efficient algorithm to find the smallest power of 2
>>that contains a number. For example, given 511 it would return 9
>>corresponding to 512, and given 33 it would return 6 corresponding to
>>64.
>
>Ok, Carlos, I'm going to give this one a shot since I did so well on the
>other code problem (see "intractable" above)...
>
>Here's your function.
>
>Private int findPow(int x)
> {
> return (!x?0:findPow((x>>1))+1);
> }
>
>You didn't specify whether 32 would return 5 or 6, so this function returns
>6 (32 does not contain itself - it fills it perfectly). In other words, it
>gives you the min(2^n)>X. Even a 32 bit number would only require 32
levels
>deep of recursion maximum...
>
>exp = findPow(X); /* returns 6 for X=32 */
>exp = findPow(X-1); /* returns 5 for X=32 */
>
>This will NOT work for X < 0. You could put a check before the return that
>handles negative numbers. You could also use a long int as the parameter -
>your choice.
>
>Hope this, at least, isn't too bad - I have a reputation to salvage!
>--
>+------------------------------------+-------------------------------+
>| Gary E. Shay, Jr. | sha...@apci.com |
>| Air Products and Chemicals, Inc. | http://www.airproducts.com |
>+------------------------------------+-------------------------------+
>| Opinions are like brains - everyone's got one, but they're not all |
>| intelligent, educated, or enlightened. This one's mine, not AP's. |
>+--------------------------------------------------------------------+
>
>
>--
>comp.lang.c.moderated - cl...@plethora.net
--
comp.lang.c.moderated - cl...@plethora.net
Stephen Lee - Post replies please
>wroth wrote:
>> On Wed, 02 Sep 1998 03:56:43 GMT, Mathew Hendry <sca...@dial.pipex.com> wrote:
>> >
>> > x|=x>>1, x|=x>>2, x|=x>>4, x|=x>>8, x|=x>>16;
>> > x^=x>>1;
>>
>> Are you sure this does something? If so, I can't tell what it is. If we
>> take x=16, for example, we end up with x=29 after the first line, and
>> 29^14=19 after the second.
>>
>> -W. Roth
>> wr...@cris.com
>
>have not dedicated any time to understand how it works. I simply plugged
>it in and it worked!
suppose this is x in binary:
0000 0000 1xxx xxxx xxxx xxxx xxxx xxxx where x's are "don't care"s.
x>>1 is:
0000 0000 01xx xxxx xxxx xxxx xxxx xxxx
x|=x>>1 gives:
0000 0000 11xx xxxx xxxx xxxx xxxx xxxx
x|=x>>2 at this point gives:
0000 0000 1111 xxxx xxxx xxxx xxxx xxxx
etc. each expression doubles the number of 1's and propergate it down from
this MS "1" bit in the original number.
At the end of the first line you'd get
0000 0000 1111 1111 1111 1111 1111 1111
x>>1 is
0000 0000 0111 1111 1111 1111 1111 1111
now x^=x>>1 is
0000 0000 1000 0000 0000 0000 0000 0000
or the highest bit in the first number.
Question: for the last step, wouldn't x++ be faster? Except you got 1 for
0, so I guess it depends on what behaviour you expect.
Stephen
--
comp.lang.c.moderated - cl...@plethora.net
Gary E. Shay, Jr.
I am absolutely enamored of this solution. How creative! Brilliant.
Unfortunately, according to my calculations, this method does not work for
"1"! Am I missing something? Thus:
if x=1. and 2^y=x,
0000 0000 0000 0000 0000 0000 0000 0001
x|=x>>anything equals x, or
0000 0000 0000 0000 0000 0000 0000 0001
Then, y = x^=x>>1 STILL equals x, or
0000 0000 0000 0000 0000 0000 0000 0001
Therefore, since 2^y = x and x=1, 2^y = 1 ? Only when y=0 and, from the
calculation above, y=1. Oops. If I recall my math training correctly, to
prove a theorem is true for all x, the first thing you do is prove it for
x=1! I don't remember this problem stating the domain as all x>=2!
G
--
+------------------------------------+-------------------------------+
| Gary E. Shay, Jr. | sha...@apci.com |
| Air Products and Chemicals, Inc. | http://www.airproducts.com |
+------------------------------------+-------------------------------+
| Opinions are like brains - everyone's got one, but they're not all |
| intelligent, educated, or enlightened. This one's mine, not AP's. |
+--------------------------------------------------------------------+
cbfal...@my-dejanews.com
sca...@dial.pipex.com (Mathew Hendry) wrote:
> On Wed, 02 Sep 1998 01:09:29 GMT, se...@plethora.net (Peter Seebach)
> wrote:
> >In article <clcm-1998...@plethora.net>,
> >Carlos Portela <cpor...@simple-sw.com> wrote:
> >>that contains a number. For example, given 511 it would return 9
> >>corresponding to 512, and given 33 it would return 6 corresponding to
> >>64.
> >
> > (x ^ (x & (x - 1))) << 1;
> >
> > x & (x - 1)
> >is "everything in x except the top bit".
>
> No, it's "everything in x except the bottom bit". Thus,
except when x is a power of 2 (assuming 2's complement), when the
original statement applies. Also the 'bottom bit' only applies
when x is odd. Now how about the remainder, not a power of 2 and
even :-)
John Potter
: except when x is a power of 2 (assuming 2's complement), when the
: original statement applies. Also the 'bottom bit' only applies
: when x is odd. Now how about the remainder, not a power of 2 and
: even :-)
I also had problems with the (missing) definitions. Topbit : most
significant one bit. Bottombit : least significant one bit. With
these, both are correct for a power of 2.
John
--
comp.lang.c.moderated - cl...@plethora.net
Mathew Hendry
<sha...@apci.com> wrote:
>Stephen Lee - Post replies please wrote in message ...
>>Carlos Portela <cpor...@simple-sw.com> wrote:
>>>wroth wrote:
>>>> On Wed, 02 Sep 1998 03:56:43 GMT, Mathew Hendry <sca...@dial.pipex.com>
>wrote:
>>>> >
>>>> > x|=x>>1, x|=x>>2, x|=x>>4, x|=x>>8, x|=x>>16;
>>>> > x^=x>>1;
>Unfortunately, according to my calculations, this method does not work for
>"1"! Am I missing something?
Yep. :)
> Thus:
>if x=1. and 2^y=x,
>0000 0000 0000 0000 0000 0000 0000 0001
>x|=x>>anything equals x, or
>0000 0000 0000 0000 0000 0000 0000 0001
>
>Then, y = x^=x>>1 STILL equals x, or
>0000 0000 0000 0000 0000 0000 0000 0001
>
>Therefore, since 2^y = x and x=1, 2^y = 1 ? Only when y=0 and, from the
>calculation above, y=1. Oops. If I recall my math training correctly, to
>prove a theorem is true for all x, the first thing you do is prove it for
>x=1! I don't remember this problem stating the domain as all x>=2!
What you're missing is that the algorithm isn't trying to find y; it's
trying to find 2^y. Along similar lines, you can find y using (again
assuming 32 bit unsigned x),
int find_y(unsigned x){
int y;
static const int tab[]={
-1,0,25,1,22,26,31,2,15,23,29,27,10,-1,12,3,6,16,
-1,24,21,30,14,28,9,11,5,-1,20,13,8,4,19,7,18,17};
unsigned t=x;
t|=t>>1,t|=t>>2,t|=t>>4,t|=t>>8,t|=t>>16;
y=tab[t%37];
if(x&&x>1<<y) ++y;
return y;
}
but there are much faster ways of doing this. The following is the
fastest I've found,
int find_y_fast(unsigned x){
static const int tab[]={
-1,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7};
int y;
if(x>=1<<15){
if(x>=1<<23) y=24+tab[x>>24];
else y=16+tab[x>>16];
}else{
if(x>=1<<8) y=8+tab[x>>8];
else y=tab[x];
}
if(x&&x>1<<y) ++y;
return y;
}
Both of these functions return y == -1 for x == 0.
Note that the original algorithm fails if x > 1<<31, but since 1<<32
isn't representable in 32 bits, this isn't exactly surprising. :)
--
comp.lang.c.moderated - cl...@plethora.net
Mathew Hendry
<nob...@nowhere.net> wrote:
>Carlos Portela <cpor...@simple-sw.com> wrote:
>>wroth wrote:
>>> On Wed, 02 Sep 1998 03:56:43 GMT, Mathew Hendry <sca...@dial.pipex.com> wrote:
>>> >
>>> > x|=x>>1, x|=x>>2, x|=x>>4, x|=x>>8, x|=x>>16;
>>> > x^=x>>1;
>>>
>Question: for the last step, wouldn't x++ be faster?
Probably, yes, but it will give different results.
> Except you got 1 for 0,
... and 2 for 1, and 4 for 2, and 4 for 3, ...
For Carlos's application (which requires "lowest containing power of
two", rather than "most signficant set bit") it might be better to
use,
{
unsigned t=x;
t|=t>>1, t|=t>>2, t|=t>>4, t|=t>>8, t|=t>>16;
if (++t>>1==x) t>>=1;
x=t;
}
which gives 0 for 0, 1 for 1, 2 for 2, 4 for 3, ...
(However, it will break for x == 1<<31.)
Gary E. Shay, Jr.
>trying to find 2^y. Along similar lines, you can find y using (again
>assuming 32 bit unsigned x),
I see that now. Duh. <sounds of mouth-breathing and drool hitting
keyboard>
(Note to self - think first, type second)
Hold the phone, though - if that's what the algorithm's doing, then it
doesn't fit the original criteria of the problem. The original statment was
to find "y" in min(2^y) >= x.
>Carlos Portela (cpor...@simple-sw.com) wrote:
>: Hi All,
>:
>: I am looking for an efficient algorithm to find the smallest power of 2
>: that contains a number. For example, given 511 it would return 9
>: corresponding to 512, and given 33 it would return 6 corresponding to
>: 64.
>but there are much faster ways of doing this. The following is the
>fastest I've found,
What about:
#define powBin(a) (a<=0?-1:findPow(a-1))
Private int findPow(int x)
{
return (!x?0:findPow((x>>1))+1);
}
G
--
comp.lang.c.moderated - cl...@plethora.net
GaryHC
Carlos Portela said
>I am looking for an efficient algorithm to find the smallest power of 2
>that contains a number. For example, given 511 it would return 9
>corresponding to 512, and given 33 it would return 6 corresponding to
>64.
>
>I remember seeing a macro in a header file ...
A coworker once asked to solve a similar problem:
Given a positive integer n (a constant known at compile time),
how many bits does it take to to represent all integers 0
through n, inclusive?
This was for automatically allocating the width of bitfields,
so a constant expression was needed.
My solution was something like this:
#define BITS_NEEDED_FOR(n) ( \
1 + \
((n) >= 2) + \
((n) >= 4) + \
((n) >= 8) + \
((n) >= 0x10) + \
((n) >= 0x20) + \
((n) >= 0x40) + \
((n) >= 0x80) + \
((n) >= 0x100) + \
((n) >= 0x200) + \
((n) >= 0x400) + \
((n) >= 0x800) + \
((n) >= 0x1000) + \
... skipping some, as the pattern should be obvious by now ...
((n) >= 0x40000000) + \
((n) >= 0x80000000) )
If n is a constant, the compiler ends up doing all the math
and coming up with another constant, so it can be used for
things like this:
#define MAX_CURRENCY_ID 9
/* ... */
struct thingy {
/* ... */
unsigned which_currency : BITS_NEEDED(MAX_CURRENCY_ID);
/* ... */
};
The comment explaining the purpose of this macro warned never
to use it with a variable argument, because it generated an
unacceptably large amount of code. (We didn't have much
memory, which is why we were packing many of the data in our
database structures into bitfields in the first place.)
It also evaluates its argument 31 times, so an argument with
side effects is a _very_ bad idea.
Most of the other proposed solutions are better for a variable
argument. (Not the proposals that are wrong, of course).
Most of the proposed solutions, including mine above, have a
portability problem: they're designed for 32-bit numbers, and
won't work with anything larger. The following function will
work for unsigned longs with _any_ number of bits, x, provided
that x <= INT_MAX. (Changing the "int"s to "unsigned long"s
would remove even this restriction).
/*
Calculate the minimum number of bits required to represent the
argument (unsigned).
Returns: result of calculation.
*/
int
bits_required(
unsigned long n)
{
int required = 1;
while (n >>= 1) {
required++;
}
return (required);
}
It's not clear to me whether the original poster wanted an
argument of 2 to the m power to give a result of m or m+1.
E.g., should 512 give 9 or 10; should 1 give 0 or 1? Both
the solutions above give m+1 (e.g., 512 gives 10; 1 gives 1).
Both can easily be modified to give m.
In the macro, change all the ">=" to ">", and change the line
1 + \
to
((n) > 1) + \
In the function, change the comments and replace the body with:
{
int required = 0;
if (n--) {
while (n) {
required++;
n >>= 1;
}
}
/* else n was 0,
so required's initial value of 0 seems appropriate.
*/
return (required);
}
I admit I didn't compile and run these, so if you're going
to use them, test them first.
--
comp.lang.c.moderated - cl...@plethora.net
Mathew Hendry
>Most of the proposed solutions, including mine above, have a
>portability problem: they're designed for 32-bit numbers, and
>won't work with anything larger.
True, but most can easily be adapted to be more portable, so long as
we have a quick way to find out the number of bits in an unsigned
long. Here's one method, which will work for ULONG_BIT <= 64 (assuming
that no implementation limits are hit), but may be expanded for larger
values,
static const int ULONG_BIT_MIN = 32;
static const int ULONG_BIT_MAX = 64;
#define ULONG_BIT_ \
(((1UL<<31)<<1)?((1UL<<32)<<1)?((1UL<<33)<<1)?((1UL<<34)<<1)\
?((1UL<<35)<<1)?((1UL<<36)<<1)?((1UL<<37)<<1)?((1UL<<38)<<1)\
?((1UL<<39)<<1)?((1UL<<40)<<1)?((1UL<<41)<<1)?((1UL<<42)<<1)\
?((1UL<<43)<<1)?((1UL<<44)<<1)?((1UL<<45)<<1)?((1UL<<46)<<1)\
?((1UL<<47)<<1)?((1UL<<48)<<1)?((1UL<<49)<<1)?((1UL<<50)<<1)\
?((1UL<<51)<<1)?((1UL<<52)<<1)?((1UL<<53)<<1)?((1UL<<54)<<1)\
?((1UL<<55)<<1)?((1UL<<56)<<1)?((1UL<<57)<<1)?((1UL<<58)<<1)\
?((1UL<<59)<<1)?((1UL<<60)<<1)?((1UL<<61)<<1)?((1UL<<62)<<1)\
?64:63:62:61:60:59:58:57:56:55:54:53:52:51:50:49:48:47:46:45\
:44:43:42:41:40:39:38:37:36:35:34:33:32)
/* number of bits required to represent ULONG_MAX */
static const int ULONG_BIT = ULONG_BIT_;
#define ULONG_BIT_BIT_ \
(6+(ULONG_BIT>0x20))
/* number of bits required to represent ULONG_BIT */
static const int ULONG_BIT_BIT = ULONG_BIT_BIT_;
Now we can change, say,
/* find smallest containing power of two for n,
assuming ULONG_BIT == 32 */
unsigned long
pow2_32(unsigned long n){
unsigned long p=n;
return p|=p>>1,p|=p>>2,p|=p>>4,p|=p>>8,p|=p>>16,p^=p>>1,p<<=p<n;
}
to the more portable,
/* find smallest containing power of two for n,
for ULONG_BIT_MIN <= ULONG_BIT <= ULONG_BIT_MAX */
unsigned long
pow2_any(unsigned long n){
unsigned long p=n,s=1,i;
for(i=0;i<ULONG_BIT_BIT-1;++i)
p|=p>>s,s<<=1;
return p^=p>>1,p<<=p<n;
}
Since ULONG_BIT_BIT is a constant, any decent compiler (e.g. gcc) will
happily unroll this loop for us and generate code identical to the
original. :)
BTW, here's a method which doesn't require any conditionals,
/* find smallest containing power of two for n,
assuming ULONG_BIT == 32 */
unsigned long
pow2_nocond(unsigned long n){
unsigned long p=n;
return
p|=p>>1,p|=p>>2,p|=p>>4,p|=p>>8,p|=p>>16,p^=p>>1,p<<=p-n>>31;
}
(32 bits only this time, but also trivial to portableify.)
Mathew Hendry
#define ULONG_BIT_BIT_ \
(6+(ULONG_BIT>0x20))
I made at least two mistakes. I should have written,
#define ULONG_BIT_BIT_ \
(6+(ULONG_BIT_>0x3f))