Question

How to round a number to the nearest power of 2 in C

Answer 1

#include <stdio.h>

/*
    roundToNearestPowerOf2(n)
    -------------------------
    Rounds an unsigned integer *n* to the nearest power of 2.

    Why this algorithm?
        • Uses only integer arithmetic and bit shifting.
        • Avoids floating‑point math (important for embedded systems).
        • Very efficient: at most 31 loop iterations on 32‑bit systems.
        • Fully portable C — no compiler-specific builtins.

    Strategy:
        1. If n == 0 → return 0 (no meaningful power of 2).
        2. Find the largest power of 2 <= n:
               prevPower = 1, then repeatedly shift left.
        3. Compute the next power of 2:
               nextPower = prevPower << 1
        4. Compare distances:
               n - prevPower   vs   nextPower - n
           Return whichever is closer.
*/
unsigned int roundToNearestPowerOf2(unsigned int n) {
    if (n == 0)
        return 0;  // Special case: zero has no meaningful nearest power of 2.

    unsigned int prevPower = 1;

    // Find the highest power of 2 that is <= n.
    // Each left shift multiplies by 2.
    while ((prevPower << 1) <= n) {
        prevPower <<= 1;
    }

    // The next power of 2 above n.
    unsigned int nextPower = prevPower << 1;

    // Choose whichever power of 2 is closer to n.
    return (n - prevPower < nextPower - n) ? prevPower : nextPower;
}

int main() {
    unsigned int values[] = {
        1, 2, 3, 5, 7, 12, 20, 37, 70,
        129, 255, 300, 513, 1025
    };

    int count = sizeof(values) / sizeof(values[0]);

    for (int i = 0; i < count; i++) {
        unsigned int v = values[i];
        printf("round_to_nearest_pow2(%u) = %u\n",
               v, roundToNearestPowerOf2(v));
    }

    return 0;
}


/*
run:

round_to_nearest_pow2(1) = 1
round_to_nearest_pow2(2) = 2
round_to_nearest_pow2(3) = 4
round_to_nearest_pow2(5) = 4
round_to_nearest_pow2(7) = 8
round_to_nearest_pow2(12) = 16
round_to_nearest_pow2(20) = 16
round_to_nearest_pow2(37) = 32
round_to_nearest_pow2(70) = 64
round_to_nearest_pow2(129) = 128
round_to_nearest_pow2(255) = 256
round_to_nearest_pow2(300) = 256
round_to_nearest_pow2(513) = 512
round_to_nearest_pow2(1025) = 1024

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <stdio.h>
#include <math.h>

/*
    round_to_nearest_pow2(n)
    ------------------------
    Rounds the integer *n* to the nearest power of 2.

    What is a power of 2?
        A number of the form 2^k:
        1, 2, 4, 8, 16, 32, 64, ...

    Efficient strategy:
        • If n <= 1 → nearest power of 2 is 1.
        • Otherwise:
              k      = log2(n)
              lower  = 2^floor(k)
              upper  = 2^ceil(k)
          Then choose whichever is closer to n.

    Why this algorithm?
        • Uses O(1) math operations.
        • log2() and pow() are built‑in C functions from <math.h>.
        • Avoids loops and bit‑twiddling tricks for clarity.
*/

int round_to_nearest_pow2(int n) {
    if (n <= 1) {
        // Defensive programming: for non-positive or tiny values,
        // the nearest power of 2 is defined as 1.
        return 1;
    }

    // Compute base‑2 logarithm.
    double k = log2((double)n);

    // Compute nearest lower and upper powers of 2.
    int lower = (int)pow(2.0, floor(k));
    int upper = (int)pow(2.0, ceil(k));

    // Choose whichever is closer to n.
    int diff_lower = n - lower;
    int diff_upper = upper - n;

    return (diff_lower <= diff_upper) ? lower : upper;
}

/*
    main
*/
int main(void) {
    int values[] = {1, 2, 3, 5, 7, 12, 20, 37, 70, 129, 255, 300, 513, 1025};
    int count = sizeof(values) / sizeof(values[0]);

    for (int i = 0; i < count; i++) {
        int v = values[i];
        printf("round_to_nearest_pow2(%d) = %d\n", v, round_to_nearest_pow2(v));
    }

    return 0;
}


/*
run:

round_to_nearest_pow2(1) = 1
round_to_nearest_pow2(2) = 2
round_to_nearest_pow2(3) = 2
round_to_nearest_pow2(5) = 4
round_to_nearest_pow2(7) = 8
round_to_nearest_pow2(12) = 8
round_to_nearest_pow2(20) = 16
round_to_nearest_pow2(37) = 32
round_to_nearest_pow2(70) = 64
round_to_nearest_pow2(129) = 128
round_to_nearest_pow2(255) = 256
round_to_nearest_pow2(300) = 256
round_to_nearest_pow2(513) = 512
round_to_nearest_pow2(1025) = 1024

*/

 

70+ SQL courses for beginners and professionals