• d-bugmail puremagic.com (139/139) Jul 18 2011 http://d.puremagic.com/issues/show_bug.cgi?id=6343

d-bugmail puremagic.com writes:

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 puremagic.com
        ReportedBy: bearophile_hugs eml.cc



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: -------