Number of Bits Needed to Represent a Zero-Offset Integer

bearophile via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Mon Jan 19 04:24:49 PST 2015


Per Nordlöw:

> I'm looking for a function that figures out the number of bits 
> that are needed to represent a zero-based integer:


// 
http://stackoverflow.com/questions/3272424/compute-fast-log-base-2-ceiling

uint ceilLog2(ulong x) pure nothrow @safe @nogc
in {
     assert(x > 0);
} body {
     static immutable ulong[6] t = [
         0xFFFFFFFF00000000UL,
         0x00000000FFFF0000UL,
         0x000000000000FF00UL,
         0x00000000000000F0UL,
         0x000000000000000CUL,
         0x0000000000000002UL];

     uint y = (((x & (x - 1)) == 0) ? 0 : 1);
     uint j = 32;

     foreach (immutable uint i; 0 .. 6) {
         immutable k = (((x & t[i]) == 0) ? 0 : j);
         y += k;
         x >>= k;
         j >>= 1;
     }

     return y;
}

void main() {
     import std.stdio;

     foreach (immutable uint i; 1 .. 18)
         writeln(i, " ", i.ceilLog2);
}


Bye,
bearophile


More information about the Digitalmars-d-learn mailing list