Algorithm for finding the smallest power of two that’s greater or equal to a given value [duplicate]

by

Here’s my favorite. Other than the initial check for whether it’s invalid (<0, which you could skip if you knew you’d only have >=0 numbers passed in), it has no loops or conditionals, and thus will outperform most other methods. This is similar to erickson’s answer, but I think that my decrementing x at the beginning and adding 1 at the end is a little less awkward than his answer (and also avoids the conditional at the end).

/// Round up to next higher power of 2 (return x if it's already a power
/// of 2).
inline int
pow2roundup (int x)
{
    if (x < 0)
        return 0;
    --x;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x+1;
}

More Related Contents:

  1. How to find number of words in a phrase with spaces removed by checking v. dictionary
  2. How to remove “noise” from GCC/clang assembly output?
  3. What is the efficient way to count set bits at a position or lower?
  4. Why does this function push RAX to the stack as the first operation?
  5. Fast exact bigint factorial
  6. Generating combinations in c++
  7. How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag’s value]?
  8. Lock-free Progress Guarantees in a circular buffer queue
  9. Finding duplicates in O(n) time and O(1) space
  10. Fast String Hashing Algorithm with low collision rates with 32 bit integer [closed]
  11. Emulate “double” using 2 “float”s
  12. How to get a random element from a C++ container?
  13. LRU cache design
  14. How to disassemble a binary executable in Linux to get the assembly code?
  15. c++ sort keeping track of indices [duplicate]
  16. Determining if a number is prime
  17. How to add two numbers without using ++ or + or another arithmetic operator
  18. Are there any better methods to do permutation of string?
  19. Reorder vector using a vector of indices [duplicate]
  20. Converting epoch time to “real” date/time
  21. Function to mangle/demangle functions
  22. CPUID implementations in C++
  23. Address of function is not actual code address
  24. What is the safe way to fill multidimensional array using std::fill?
  25. Calculate system time using rdtsc
  26. Address of labels (MSVC)
  27. How to find and replace all occurrences of a substring in a string?
  28. How is floating point conversion actually done in C++?(double to float or float to double)
  29. Finding square root without using sqrt function?
  30. How to force GCC to assume that a floating-point expression is non-negative?

Leave a Comment