As a follow-up to

http://forum.dlang.org/thread/fdfwrdtjcawprvvkoqas@forum.dlang.org#post-qxudiyoygnvvbovhjfgt:40forum.dlang.org

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

value-set => bits
=================
0,1 => 1 (*)
0,1,2 => 2
0,1,2,3 => 2 (*)
0,1,2,3,4 => 3
0,1,2,3,4,5 => 3
0,1,2,3,4,5,6 => 3
0,1,2,3,4,5,6,7 => 3 (*)
0,1,2,3,4,5,6,7,8 => 4
...

(*) means full bit usage

On Monday, January 19, 2015 12:04:38 via Digitalmars-d-learn wrote:
> As a follow-up to
>
> http://forum.dlang.org/thread/fdfwrdtjcawprvvkoqas@forum.dlang.org#post-qxudiyoygnvvbovhjfgt:40forum.dlang.org
>
> I'm looking for a function that figures out the number of bits that are needed to represent a zero-based integer:
>
> value-set => bits
> =================
> 0,1 => 1 (*)
> 0,1,2 => 2
> 0,1,2,3 => 2 (*)
> 0,1,2,3,4 => 3
> 0,1,2,3,4,5 => 3
> 0,1,2,3,4,5,6 => 3
> 0,1,2,3,4,5,6,7 => 3 (*)
> 0,1,2,3,4,5,6,7,8 => 4
> ...
>
> (*) means full bit usage

I had this lying around in one of my projects:

/++
  Log₂ with integral values rather than real.
  +/
ulong lg(ulong n)
{
    return n == 1 ? 0 : 1 + lg(n / 2);
}

/++
    Returns the minimum number of bits required to hold the given value.
  +/
size_t bitsRequired(ulong value)
{
    import std.math;
    return value == 0 ? 1 : cast(size_t)lg(value) + 1;
}

unittest
{
    import std.string, std.typetuple;
    ulong one = 1;

    assert(bitsRequired(0) == 1);
    foreach(bits; 0 .. 31)
    {
        assert(bitsRequired(one << bits) == bits + 1,
               format("bits [%s], result [%s]", bits, bitsRequired(bits)));
    }

    foreach(T; TypeTuple!(ubyte, ushort, uint, ulong))
    {
        ulong value;
        foreach(bits; 0 .. T.sizeof * 8)
        {
            value <<= 1;
            value |= 1;
        }
        assert(bitsRequired(T.min) == 1);
        assert(bitsRequired(T.max) == T.sizeof * 8,
               format("Type [%s], result [%s]", T.stringof, bitsRequired(T.max)));
    }
}

- Jonathan M Davis

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

On Mon, 19 Jan 2015 12:04:38 +0000
via Digitalmars-d-learn <digitalmars-d-learn@puremagic.com> wrote:

> As a follow-up to
> 
> http://forum.dlang.org/thread/fdfwrdtjcawprvvkoqas@forum.dlang.org#post-qxudiyoygnvvbovhjfgt:40forum.dlang.org
> 
> I'm looking for a function that figures out the number of bits that are needed to represent a zero-based integer:
> 
> value-set => bits
> =================
> 0,1 => 1 (*)
> 0,1,2 => 2
> 0,1,2,3 => 2 (*)
> 0,1,2,3,4 => 3
> 0,1,2,3,4,5 => 3
> 0,1,2,3,4,5,6 => 3
> 0,1,2,3,4,5,6,7 => 3 (*)
> 0,1,2,3,4,5,6,7,8 => 4
> ...
> 
> (*) means full bit usage

  template minbits (uint n) {
    import std.math : log2;
    enum minbits = (n ? cast(int)(log2(n))+1 : 1);
  }

  template btest (uint n) {
    static if (n <= 64) {
      import std.conv;
      pragma(msg, to!string(n)~"="~to!string(minbits!n));
      enum btest = btest!(n+1);
    } else {
      enum btest = 666;
    }
  }

  enum t = btest!0;

On 1/19/15 7:04 AM, "Per =?UTF-8?B?Tm9yZGzDtnci?= <per.nordlow@gmail.com>" wrote:
> As a follow-up to
>
> http://forum.dlang.org/thread/fdfwrdtjcawprvvkoqas@forum.dlang.org#post-qxudiyoygnvvbovhjfgt:40forum.dlang.org
>
>
> I'm looking for a function that figures out the number of bits that are
> needed to represent a zero-based integer:
>
> value-set => bits
> =================
> 0,1 => 1 (*)
> 0,1,2 => 2
> 0,1,2,3 => 2 (*)
> 0,1,2,3,4 => 3
> 0,1,2,3,4,5 => 3
> 0,1,2,3,4,5,6 => 3
> 0,1,2,3,4,5,6,7 => 3 (*)
> 0,1,2,3,4,5,6,7,8 => 4
> ....
>
> (*) means full bit usage

http://dlang.org/phobos/core_bitop.html#.bsr

It's actually an intrinsic, reduces to an instruction. Mind the requirements for 0.

-Steve

On Monday, 19 January 2015 at 13:30:47 UTC, Steven Schveighoffer wrote:
> http://dlang.org/phobos/core_bitop.html#.bsr
>
> It's actually an intrinsic, reduces to an instruction. Mind the requirements for 0.
>
> -Steve

Nice. Is this intrinsic supported for all DMD/GCD/LDC supported platforms or do we have to supply fallback logic when bsr is not available?

On Monday, January 19, 2015 08:30:47 Steven Schveighoffer via Digitalmars-d-learn wrote:
> http://dlang.org/phobos/core_bitop.html#.bsr
>
> It's actually an intrinsic, reduces to an instruction. Mind the requirements for 0.

Sadly, I don't think that it have occurred to me from just reading the docs that that function would tell you how many bits it took to hold the value - though I don't know what else you'd use it for. In any case, thanks for the tip.

- Jonathan M Davis

On 1/19/15 12:35 PM, Jonathan M Davis via Digitalmars-d-learn wrote:
> On Monday, January 19, 2015 08:30:47 Steven Schveighoffer via Digitalmars-d-learn wrote:
>> http://dlang.org/phobos/core_bitop.html#.bsr
>>
>> It's actually an intrinsic, reduces to an instruction. Mind the
>> requirements for 0.
>
> Sadly, I don't think that it have occurred to me from just reading the docs
> that that function would tell you how many bits it took to hold the value -
> though I don't know what else you'd use it for. In any case, thanks for the
> tip.
>
> - Jonathan M Davis
>

It tells you the most significant bit that is set. That is what you are looking for, no?

Code:

import core.bitop;
import std.stdio;

void main()
{
    foreach(x; 1..100)
        writefln("x=%s, bsr(x)=%s", x, bsr(x)+1);
}

From the examples:

> value-set => bits
> =================
> 0,1 => 1 (*)
> 0,1,2 => 2
> 0,1,2,3 => 2 (*)
> 0,1,2,3,4 => 3
> 0,1,2,3,4,5 => 3
> 0,1,2,3,4,5,6 => 3
> 0,1,2,3,4,5,6,7 => 3 (*)
> 0,1,2,3,4,5,6,7,8 => 4

Output from test program:

x=1, bsr(x)=1
x=2, bsr(x)=2
x=3, bsr(x)=2
x=4, bsr(x)=3
x=5, bsr(x)=3
x=6, bsr(x)=3
x=7, bsr(x)=3
x=8, bsr(x)=4
...

Looks the same to me.

If you want the extra info of whether it's the full set (i.e. the * elements above), then you can do simple x & (x+1) == 0.

-Steve

On 1/19/15 10:49 AM, "Per =?UTF-8?B?Tm9yZGzDtnci?= <per.nordlow@gmail.com>" wrote:
> On Monday, 19 January 2015 at 13:30:47 UTC, Steven Schveighoffer wrote:
>> http://dlang.org/phobos/core_bitop.html#.bsr
>>
>> It's actually an intrinsic, reduces to an instruction. Mind the
>> requirements for 0.
>>
>
> Nice. Is this intrinsic supported for all DMD/GCD/LDC supported
> platforms or do we have to supply fallback logic when bsr is not available?

I'm fairly certain it's supported as an intrinsic there. BSR is an X86 instruction. You'd have to disassemble to be sure on the target platform.

But it is definitely supported regardless, as it's part of the API.

-Steve

On Monday, January 19, 2015 13:37:12 Steven Schveighoffer via Digitalmars-d-learn wrote:
> On 1/19/15 12:35 PM, Jonathan M Davis via Digitalmars-d-learn wrote:
> > On Monday, January 19, 2015 08:30:47 Steven Schveighoffer via Digitalmars-d-learn wrote:
> >> http://dlang.org/phobos/core_bitop.html#.bsr
> >>
> >> It's actually an intrinsic, reduces to an instruction. Mind the requirements for 0.
> >
> > Sadly, I don't think that it have occurred to me from just reading the docs that that function would tell you how many bits it took to hold the value - though I don't know what else you'd use it for. In any case, thanks for the tip.
> >
> > - Jonathan M Davis
> >
>
> It tells you the most significant bit that is set. That is what you are looking for, no?

Yes. But if I'm looking for a function that tells me how many bits are required to hold a value, I'm thinking about how many bits are required, not what the most significant bit is. Ultimately, it's the same thing, but it's looking at it from a different perspective, so I don't think that I would have caught it.

- Jonathan M Davis