## digitalmars.D.bugs - [Issue 6343] New: std.math.nextPow2

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

--- Comment #0 from bearophile_hugs 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: -------
```
Jul 18 2011