[Issue 6343] New: std.math.nextPow2

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=6343

           Summary: std.math.nextPow2
           Product: D
           Version: unspecified
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody at puremagic.com
        ReportedBy: bearophile_hugs at eml.cc


--- Comment #0 from bearophile_hugs at eml.cc 2011-07-18 05:27:32 PDT ---
I'd like a function like this in Phobos. One of my use case is for fixed-sized
arrays like:

size_t w = 6;
int[w][6] mat;

Sometimes I use this to increase code performance (if rows are a power of 2,
the matrix indexing is faster):

size_t w = 6;
int[nextPow2(w)][6] mat;

------------------------

import core.bitop: bsr;
import std.typetuple: TypeTuple;

/**
Given n, it returns the next (bigger or equal) power of 2 of n,
(the first integer 2^^m such that 2^^m >= n).

Example:
nextPow2(9) ==> 16
nextPow2(size_t.max - 10) ==> 0
*/
size_t nextPow2(in size_t n) pure nothrow { // bsr() is not @safe
    if (n == 0)
        return 1;

    if (!__ctfe) {
        // get first bit set, starting with most significant.
        int first_bit_set = bsr(n);

        // If already equal to a power of two
        if (( (cast(size_t)1) << first_bit_set) == n)
            return n;
        return (cast(size_t)2) << first_bit_set;
    } else {
        // http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
        size_t x = n;
        x--;
        x |= x >> 1;
        x |= x >> 2;
        x |= x >> 4;
        x |= x >> 8;
        x |= x >> 16;
        static assert(size_t.sizeof == 4 || size_t.sizeof == 8);
        static if (x.sizeof == 8)
            x |= x >> 32;
        x++;
        return x;
    }
}

version(X86) {
    /// ditto
    ulong nextPow2(in ulong n) pure nothrow @safe {
        if (n == 0)
            return 1;
        // http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2

        ulong x = n;
        x--;
        x |= x >> 1;
        x |= x >> 2;
        x |= x >> 4;
        x |= x >> 8;
        x |= x >> 16;
        x |= x >> 32;
        x++;
        return x;
    }
}

unittest { // nextPow2
    // compile-time tests ----------------
    foreach (i, r; TypeTuple!(1,1,2,4,4,8,8,8,8,16,16,16,16,16,16,16,16))
        static assert(nextPow2(i) == r);

    version(X86)
        alias TypeTuple!(4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048,
        4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576,
        2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728,
        268435456, 536870912, 1073741824, 2147483648) ctdata1;
    else
        alias TypeTuple!(4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048,
        4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576,
        2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728,
        268435456, 536870912, 1073741824,2147483648, 4294967296, 8589934592,
        17179869184, 34359738368, 68719476736, 137438953472, 274877906944,
        549755813888, 1099511627776, 2199023255552, 4398046511104,
        8796093022208, 17592186044416, 35184372088832, 70368744177664,
        140737488355328, 281474976710656, 562949953421312, 1125899906842624,
        2251799813685248, 4503599627370496, 9007199254740992,
        18014398509481984, 36028797018963968, 72057594037927936,
        144115188075855872, 288230376151711744, 576460752303423488,
        1152921504606846976, 2305843009213693952, 4611686018427387904) ctdata1;

    foreach (d; ctdata1) {
        static assert(nextPow2(d-1) == d);
        static assert(nextPow2(d) == d);
    }

    foreach (i, d; ctdata1[0 .. $ - 1])
        static assert(nextPow2(d+1) == ctdata1[i+1]);

    alias TypeTuple!(20, 30,31,32,100,1000,1023,1024,1025,
                     32768,262143,262144) ctdata2;
    const results2 = [32, 32,32,32,128,1024,1024,1024,2048,
                      32768,262144,262144];
    foreach (i, d; ctdata2)
        static assert(nextPow2(d) == results2[i]);

    static assert(nextPow2(size_t.max - 10) == 0);
    static assert(nextPow2(size_t.max - 1) == 0);
    static assert(nextPow2(size_t.max) == 0);
    static assert(nextPow2(6_000_000_000UL) == (1UL << 33));

    // run-time tests ----------------
    const results1 = [1,1,2,4,4,8,8,8,8,16,16,16,16,16,16,16,16];
    foreach (i, r; results1)
        assert(nextPow2(i) == r);

    foreach (i; 2 .. (8 * size_t.sizeof)) {
        size_t p = 1 << i;
        assert(nextPow2(p-1) == p);
        assert(nextPow2(p) == p);
    }

    foreach (i; 2 .. (8 * size_t.sizeof - 1)) {
        size_t p = 1 << i;
        assert(nextPow2(p+1) == (1U << (i+1)));
    }

    const data = [20, 30,31,32,100,1000,1023,1024,1025,32768,
                  262143,262144];
    foreach (i, d; data)
        assert(nextPow2(d) == results2[i]);

    assert(nextPow2(size_t.max - 10) == 0);
    assert(nextPow2(size_t.max - 1) == 0);
    assert(nextPow2(size_t.max) == 0);
    assert(nextPow2(6_000_000_000UL) == (1UL << 33));
}

void main() {}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------