Thread: power_of_two function

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    242

    power_of_two function

    What's the best way to write a function with the following prototype:

    unsigned power_of_two(const unsigned &max);

    where the function should return the largest power of 2 that is < max.

    You can of course do it the old-fashioned way:
    Code:
    unsigned power_of_two(const unsigned &max) {
      unsigned result = 1;
      while (result < max) {
        result *= 2;
      }
      result /= 2;
      return result;
    }
    Or you can do this:
    Code:
    unsigned power_of_two(const unsigned &max) {
    
                  unsigned result = max;
    	--result;
    	result |= result >> 1;
    	result |= result >> 2;
    	result |= result >> 4;
    	result |= result >> 8;
    	result |= result >> 16;	// now all bits are set up to the most significant bit in _size
    	++result;		// result is now the nearest power of 2 greater than or equal to _size
    	result = result >> 1; // result < _size
    	return result;
    Or, in the same spirit as the second, and presumably slightly slower but more straightforward:

    Code:
    unsigned power_of_two(const unsigned &max) {
      unsigned result = 1;
      while (result < max) {
        result = result << 1;
      }
      result = result >> 1;
      return result;
    }

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    I would simply use log2 to get the power of 2 to get max. Then take the integer and raise 2 to that power.
    Otherwise, I'd prefer the first.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    My first step would be to drop the const reference and just pass by value.
    Next I would not name the parameter 'max'.

    Then, much like your second code snippet, I would lose the extra variable and just write it like this:
    Code:
    unsigned int power_of_two(unsigned int val) {
        --val;
        val |= val >> 16;
        val |= val >>  8;
        val |= val >>  4;
        val |= val >>  2;
        val |= val >>  1;
        return val ^ (val >> 1);
    }
    Or if I wasn't already familiar with this technique, I would look something up from this site.

    I also question whether you are after a power of two strictly less than the input, or whether you actually want a power of two that is less than or equal. E.g. For most purposes I would expect that passing in 16 would return 16. In which case you can lose the --val; part. This would also allow it to return a sensible value when passed in zero. Otherwise I'd feel it necessary to throw an exception or just assert, when the input parameter is zero.

    Note also that all of the methods you posted fail when given input greater than or equal to 2^31, the first and third one going into an infinite loop, with the second one simply giving the wrong answer. As a minimum I would expect an author of such code to document this limitation.
    This issue is fixed with the code I just posted, as it also would be with Elysia's suggestion.
    Last edited by iMalc; 09-22-2010 at 01:51 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    One silly note - this code is non portable.
    I would probably use the first (but modified) version.

    Or, in the same spirit as the second, and presumably slightly slower but more straightforward:
    Code:
    unsigned power_of_two(const unsigned &max) {
      unsigned result = 1;
      while (result < max) {
        result = result << 1;
      }
      result = result >> 1;
      return result;
    }
    This is the same as the first, isn't it?
    Last edited by kmdv; 09-22-2010 at 08:02 AM.

  5. #5
    Registered User
    Join Date
    May 2009
    Posts
    242
    it is the same result as the first for sure, but i like it better.

    as to dropping const and &: if you drop the "const" will it work if you pass it a constant? if so, then i agree with you that it's ridiculous to add the extra baggage when one is copying it anyway.

    then on the input > 2^31: you're right, but an easy fix is to make it:
    Code:
    while (result && result < max) { ... }
    i'll have to think a little about your technique for modifying 2).

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Quote Originally Posted by Aisthesis View Post
    as to dropping const and &: if you drop the "const" will it work if you pass it a constant? if so, then i agree with you that it's ridiculous to add the extra baggage when one is copying it anyway.
    Yes, it will work. A function like this
    Code:
    void func(unsigned x);
    can be passed an unsigned int or a const unsigned int, because a copy of the number will be made. It's quite customary to pass small data structures and especially primitives by value unless there's a reason to do something else.

    (For more complicated data structures, it might be expensive to copy the object, or the object might not even have a copy constructor, in which case you start seeing constant references being used.)
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by dwks View Post
    Yes, it will work. A function like this
    Code:
    void func(unsigned x);
    can be passed an unsigned int or a const unsigned int, because a copy of the number will be made. It's quite customary to pass small data structures and especially primitives by value unless there's a reason to do something else.

    (For more complicated data structures, it might be expensive to copy the object, or the object might not even have a copy constructor, in which case you start seeing constant references being used.)
    I actually consider it fairly good practice to pass things as const reference, with the exception of built-in types... It won't ever hurt...

  8. #8
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Sure. With the exception of built-in types. Although . . . I sometimes pass small things like Points by value, but not much else.

    And it can hurt, if you try to generalize the practice outside of parameters.
    Code:
    const Object &getAnObject() { return Object(); }  // oops
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Aisthesis View Post
    it is the same result as the first for sure, but i like it better.

    as to dropping const and &: if you drop the "const" will it work if you pass it a constant? if so, then i agree with you that it's ridiculous to add the extra baggage when one is copying it anyway.
    I think this has been answered now.

    Quote Originally Posted by Aisthesis View Post
    then on the input > 2^31: you're right, but an easy fix is to make it:
    Code:
    while (result && result < max) { ... }
    ).
    That would do it. I was thinking of putting a specific check for the input being >= 2^31 at the start of the function so as to not impact the performance of the loop.
    Quote Originally Posted by Aisthesis View Post
    i'll have to think a little about your technique for modifying 2).
    How it works:
    After all the |= lines, val is made up of some number of consecutive zeros bits starting from the high end, followed by some number of ones.
    E.g. 31 =
    0x00, 0x00, 0x00, 00011111
    Right shifted, this gives us:
    0x00, 0x00, 0x00, 00001111
    XOR them and you get:
    0x00, 0x00, 0x00, 00010000
    Using subtraction would work just as well, but in such cases I always use the logically simpler operation, such that when the technique is generalised to bigint class type etc, it is faster.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Registered User
    Join Date
    May 2009
    Posts
    242
    i'm not terribly worried about the strictly less than or less than in this case.

    my only problem with version 2) or your improvement is that you're locked into a 32-bit representation of int, which it should be, but it's kind of nice to have it apply more generally just in case.

    i hope the falling takes care of all the pitfalls discussed and still does things pretty fast:

    Code:
    unsigned power_of_two(unsigned const &max) {  // since we don't need a copy
      result = 1;
      while (result && result < max) {
        result <<= 1;
      }
      // only remaining problem is that result could be 0 if max has its most significant bit set
      --result;
      result >>= 1;
      ++result;
    }
    for numbers ~< 2^12 this should even be faster than the 16, 8, 4, ... method (since the loop stops quickly, although slower for bit integers. i also feel more comfortable with it doesn't depend on integers being 32 bits long.

    should work every time, too, i think--or does this one still break down in some cases?

  11. #11
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Why not just shift the value left until a 1 bit appears in the MSB?

    Code:
    unsigned int power_of_two(unsigned int max)
    {
        const unsigned int mask = ~(~0U>>1);
        unsigned int result = mask;
        assert(max != 0);
        while(!(max & mask))
        {
            result >>= 1;
            max <<= 1;
        }
        return result;
    }
    No assumptions made about how many bits in an unsigned int, no weird corner cases.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  12. #12
    Registered User
    Join Date
    May 2009
    Posts
    242
    beautiful idea! can't we simplify further like this:

    Code:
    unsigned power_of_two(const unsigned &max) {
      assert(max != 0);  // also a nice addition
      unsigned result = ~(~0U >> 1);
      while(!(result & max)) result >>= 1;
      return result;
    }

  13. #13
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Aisthesis View Post
    beautiful idea! can't we simplify further like this:

    Code:
    unsigned power_of_two(const unsigned &max) {
      assert(max != 0);  // also a nice addition
      unsigned result = ~(~0U >> 1);
      while(!(result & max)) result >>= 1;
      return result;
    }
    Yes, good spotting.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  14. #14
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Haven't validated the theory behind this, but it should work:
    Code:
    unsigned power_of_two(unsigned i) {
      while(i & (i-1))
        i &= i-1;
      return i;
    }
    I am pretty sure that (i & (i-1)) always eliminates the least significant set bit of the number. Also, if the compiler is smart, this should compile down to something like:
    Code:
    ; assume ebx holds i
    repeat:
      mov eax, ebx
      dec eax
      and ebx, eax
      jnz repeat
      inc eax
      ret
    Of course, if we're at that low level, it's easier to do this:
    Code:
    return 1 << (sizeof(unsigned)*CHAR_BIT - 1) - clz(i)
    where clz is the count leading zeros instruction many architectures have. x86 has BSF, bit scan forward. Its performance over time has varied greatly in various CPUs, but as of the Core2, it's fast again, and will easily beat every loop.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Aisthesis View Post
    my only problem with version 2) or your improvement is that you're locked into a 32-bit representation of int, which it should be, but it's kind of nice to have it apply more generally just in case.
    Yes absolutely, that is the caveat.


    Quote Originally Posted by Aisthesis View Post
    for numbers ~< 2^12 this should even be faster than the 16, 8, 4, ... method (since the loop stops quickly, although slower for bit integers. i also feel more comfortable with it doesn't depend on integers being 32 bits long.
    It might be less operations, but it has conditional branches. If one those are mispredicted, which is highly likely, then it probably wont end up faster.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Compiling C in Visual Studio 2005
    By emanresu in forum C Programming
    Replies: 3
    Last Post: 11-16-2009, 04:25 AM
  2. Compiling sample DarkGDK Program
    By Phyxashun in forum Game Programming
    Replies: 6
    Last Post: 01-27-2009, 03:07 AM
  3. Seg Fault in Compare Function
    By tytelizgal in forum C Programming
    Replies: 1
    Last Post: 10-25-2008, 03:06 PM
  4. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  5. const at the end of a sub routine?
    By Kleid-0 in forum C++ Programming
    Replies: 14
    Last Post: 10-23-2005, 06:44 PM