Bug 6343 – std.math.ceilPow2

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() {}

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.

(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?

I figured it was more useful to comment on this existing patch, which is more comprehensive than my hacks...

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

(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.

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.