D issues are now tracked on GitHub. This Bugzilla instance remains as a read-only archive.
Issue 6343 - std.math.ceilPow2
Summary: std.math.ceilPow2
Status: RESOLVED WONTFIX
Alias: None
Product: D
Classification: Unclassified
Component: phobos (show other issues)
Version: D2
Hardware: All All
: P2 enhancement
Assignee: No Owner
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2011-07-18 05:27 UTC by bearophile_hugs
Modified: 2016-04-27 18:32 UTC (History)
3 users (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this issue.
Description bearophile_hugs 2011-07-18 05:27:32 UTC
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() {}
Comment 1 Manu 2014-09-04 06:46:18 UTC
I would also like something like this...
I've needed it on at least 3 occasions, and each time I check to see if it's in the std lib, disappointed it's not, then write my own.
Comment 2 yebblies 2014-09-04 15:17:19 UTC
(In reply to Manu from comment #1)
> I would also like something like this...
> I've needed it on at least 3 occasions, and each time I check to see if it's
> in the std lib, disappointed it's not, then write my own.

Next time, make a pull request?
Comment 3 Manu 2014-09-04 15:27:44 UTC
I figured it was more useful to comment on this existing patch, which is more comprehensive than my hacks...
Comment 5 bearophile_hugs 2015-10-20 19:59:33 UTC
(In reply to Jack Stouffer from comment #4)
> https://github.com/D-Programming-Language/phobos/pull/3755

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

nextPow2(8) needs to be 8.

If you think the name of the function is wrong, then change its name, don't change the semantics :)
Comment 6 bearophile_hugs 2015-10-20 20:01:29 UTC
(In reply to bearophile_hugs from comment #5)

> If you think the name of the function is wrong, then change its name

ceilPow2 sounds OK.
Comment 7 Jack Stouffer 2016-04-27 18:32:54 UTC
No need for a separate function now, you can just do

    nextPow2(w == 0 ? w : w - 1)

for your desired effect. If you still want the name, then you can do

    alias ceilPow2 = (w) => nextPow2(w == 0 ? w : w - 1);

in your code. I am going to mark this as won't fix because adding this function would only take one line and therefore is of questionable value to add to Phobos.