2

I just wonder if there exists better (i.e. faster?) way to get the next power of 2 for a given number than the following one (maybe some better sort of "bit-twiddling" hack is possible?) ...

static size_t
npow2(size_t n)
{
        n--;
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        return n + 1;
}

Thanks for your ideas.

Improve this question
5
  • Unclear what help you need. Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it’s hard to tell what problem you are trying to solve or what aspect of your approach needs to be corrected or explained. See the How to Ask page for help clarifying this question.
    – gnat
    Commented Feb 6, 2014 at 15:33
  • 1
    I think this question would be better suited for SO, since it is about specific implementation details in C.
    – Doc Brown
    Commented Feb 6, 2014 at 15:44
  • 1
    @gnat: The question is pretty clear and unambiguous, I think.
    – Pi Delport
    Commented Feb 6, 2014 at 17:29
  • @DocBrown: The mathematics of bit manipulation should make this question algorithmic enough to be suited for here; particularly if you go by the "SO for when you're in front of a compiler/editor, Programmers for when you're in front of a whiteboard" test.
    – Pi Delport
    Commented Feb 6, 2014 at 17:32
  • It's worth noting that the given npow2 function won't work on a system where size_t is larger than 32-bits.
    – skeggse
    Commented Jan 5, 2015 at 1:42

1 Answer 1

Reset to default
3

According to Sean Eron Anderson's collection of Bit Twiddling Hacks, that's probably the fastest way.

The alternatives are an IEEE float casting hack, which involves fewer C operations but ends up slower, and directly using the x86 BSR (bit scan reverse) machine instruction, but in Anderson's testing that didn't end up significantly faster than the above OR-ing trick.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.