Thread: power_of_two function

  1. #16
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by CornedBee View Post
    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;
    }
    That's an interesting solution which appears to work correctly, returning a power of two not greater than the input.

    Quote Originally Posted by CornedBee View Post
    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.
    I totally forgot to mention that instruction though I did think of it when I started writing my first post. I figured there'd be an intrinsic for it now.
    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"

  2. #17
    Registered User
    Join Date
    May 2009
    Posts
    242
    Code:
    unsigned power_of_two(unsigned i) {
      while(i & (i-1))
        i &= i-1;
      return i;
    }
    very nice!
    i do think the modified brewbuck solution will be faster (fewer iterations) if i is often a random (half the bits set) number between 2^21 and 2^32 (or is > 2^16 but for some reason will have all or most bits set).

  3. #18
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by CornedBee View Post
    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.
    I was going to mention BSF/BSR. I used those instructions recently to implement a 1M entry bitmap with constant time lookup of the first non-zero bit -- on my machine, it could search a 1M bit array for the first non-zero bit in under 22 nanoseconds.

    Of course, BSF isn't enough on its own to get that speed -- I used a hierarchical data structure to accelerate the search to constant time.

    EDIT: here's code to do it using gcc:

    Code:
    unsigned int power_of_two(unsigned int max)
    {
        int bit;
        __asm__("bsr %1, %0" : "=g" (bit) : "g" (max));
        return 1 << bit;
    }
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  4. #19
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    That's an interesting solution which appears to work correctly, returning a power of two not greater than the input.
    That depends on what the original poster really wants.

    Different people have posted different solution sets.

    One set of solutions always returns a power of two less than the target value.

    One set of solutions always returns a power of two less than or equal to the target value.



    very nice! i do think the modified brewbuck solution will be faster if i is often a random number between 2^21 and 2^32.
    Try the `power_of_twoe' function below with the code provided by CornedBee.

    Depending on your processor, with an expected uniform distribution, it will be at least as fast as the code provided by iMalc.

    Depending on your processor, with an expected uniform distribution, you can use the `power_of_twoe' function below with a 256 byte table and it will be at least as fast as the code provided by iMalc.

    Soma

    Code:
    unsigned int power_of_twoe
    (
        unsigned int i
    )
    {
        int l(i & (i-1));
        if(!l)
        {
            return(i >> 1);
        }
        if((1 << 16) > i)
        {
            if((1 << 8) > i)
            {
                return(power_of_two(i));
            }
            return(power_of_two(i >> 8) << 8);
        }
        if((1 << 24) > i)
        {
            return(power_of_two(i >> 16) << 16);
        }
        return(power_of_two(i >> 24) << 24);
    }

  5. #20
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Also, check out this cool list of bit hacks:

    Bit Twiddling Hacks
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

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