## digitalmars.D.learn - Number of Bits Needed to Represent a Zero-Offset Integer

"Per =?UTF-8?B?Tm9yZGzDtnci?= <per.nordlow gmail.com> writes:
```As a follow-up to

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
```
Jan 19 2015
Jonathan M Davis via Digitalmars-d-learn writes:
```On Monday, January 19, 2015 12:04:38 via Digitalmars-d-learn wrote:
As a follow-up to

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
```
Jan 19 2015
"bearophile" <bearophileHUGS lycos.com> writes:
```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
```
Jan 19 2015
ketmar via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
```On Mon, 19 Jan 2015 12:04:38 +0000
via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> wrote:

As a follow-up to
=20

xudiyoygnvvbovhjfgt:40forum.dlang.org
=20
I'm looking for a function that figures out the number of bits=20
that are needed to represent a zero-based integer:
=20
value-set =3D> bits
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
0,1 =3D> 1 (*)
0,1,2 =3D> 2
0,1,2,3 =3D> 2 (*)
0,1,2,3,4 =3D> 3
0,1,2,3,4,5 =3D> 3
0,1,2,3,4,5,6 =3D> 3
0,1,2,3,4,5,6,7 =3D> 3 (*)
0,1,2,3,4,5,6,7,8 =3D> 4
...
=20
(*) means full bit usage

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

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

enum t =3D btest!0;
```
Jan 19 2015
Steven Schveighoffer <schveiguy yahoo.com> writes:
```On 1/19/15 7:04 AM, "Per =?UTF-8?B?Tm9yZGzDtnci?=
<per.nordlow gmail.com>" wrote:
As a follow-up to

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
```
Jan 19 2015
"Per =?UTF-8?B?Tm9yZGzDtnci?= <per.nordlow gmail.com> writes:
```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?
```
Jan 19 2015
Steven Schveighoffer <schveiguy yahoo.com> writes:
```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
```
Jan 19 2015
Jonathan M Davis via Digitalmars-d-learn writes:
```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
```
Jan 19 2015
Steven Schveighoffer <schveiguy yahoo.com> writes:
```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
```
Jan 19 2015
Jonathan M Davis via Digitalmars-d-learn writes:
```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
```
Jan 19 2015
=?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
```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.

This works for me

https://github.com/nordlow/justd/blob/master/traits_ex.d#L406

:)
```
Jan 19 2015
Steven Schveighoffer <schveiguy yahoo.com> writes:
```On 1/19/15 3:46 PM, "Nordlöw" 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.

This works for me

https://github.com/nordlow/justd/blob/master/traits_ex.d#L406

Cool. I would point out that the commented code suggests you should be
handling the 0 case, but you are not (when T.min == T.max)

-Steve
```
Jan 19 2015
=?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
```On Monday, 19 January 2015 at 20:54:50 UTC, Steven Schveighoffer
wrote:
Cool. I would point out that the commented code suggests you
should be handling the 0 case, but you are not (when T.min ==
T.max)

I believe that should trigger a failing static assert with a good
error message as it doesn't make any sense to call the function
in that case. Thanks.
```
Jan 19 2015
"Dominikus Dittes Scherkl" writes:
```On Monday, 19 January 2015 at 21:23:47 UTC, Nordlöw wrote:
On Monday, 19 January 2015 at 20:54:50 UTC, Steven
Schveighoffer wrote:
Cool. I would point out that the commented code suggests you
should be handling the 0 case, but you are not (when T.min ==
T.max)

I believe that should trigger a failing static assert with a
good error message as it doesn't make any sense to call the
function in that case. Thanks.

I would recommend to use something like this:

/// returns the number of the highest set bit +1 in the given
value or 0 if no bit is set
size_t bitlen(T)(const(T) a) pure  safe  nogc nothrow
if(isUnsigned!T)
{
static if(T.sizeof <= size_t.sizeof) // doesn't work for ulong
on 32bit sys
{
return x ? core.bitop.bsr(x)+1 : 0;
}
else static if(T.sizeof == 8) // ulong if size_t == uint
{
return x ? x>>32 ? core.bitop.bsr(x)+33 :
core.bitop.bsr(x)+1 : 0;
}
}
```
Jan 20 2015
"bearophile" <bearophileHUGS lycos.com> writes:
```Dominikus Dittes Scherkl:

I would recommend to use something like this:

/// returns the number of the highest set bit +1 in the given
value or 0 if no bit is set
size_t bitlen(T)(const(T) a) pure  safe  nogc nothrow
if(isUnsigned!T)
{
static if(T.sizeof <= size_t.sizeof) // doesn't work for
ulong on 32bit sys
{
return x ? core.bitop.bsr(x)+1 : 0;
}
else static if(T.sizeof == 8) // ulong if size_t == uint
{
return x ? x>>32 ? core.bitop.bsr(x)+33 :
core.bitop.bsr(x)+1 : 0;
}
}

Is this good to be added to Phobos? Perhaps with a more
descriptive name?

Bye,
bearophile
```
Feb 13 2015
"H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
```On Fri, Feb 13, 2015 at 12:28:23PM +0000, bearophile via Digitalmars-d-learn
wrote:
Dominikus Dittes Scherkl:

I would recommend to use something like this:

/// returns the number of the highest set bit +1 in the given value
/// or 0 if no bit is set
size_t bitlen(T)(const(T) a) pure  safe  nogc nothrow if(isUnsigned!T)
{
static if(T.sizeof <= size_t.sizeof) // doesn't work for ulong on 32bit sys
{
return x ? core.bitop.bsr(x)+1 : 0;
}
else static if(T.sizeof == 8) // ulong if size_t == uint
{
return x ? x>>32 ? core.bitop.bsr(x)+33 : core.bitop.bsr(x)+1 : 0;
}
}

Is this good to be added to Phobos? Perhaps with a more descriptive
name?

[...]

Isn't it essentially floor(log_2(a)), mathematically speaking? Maybe
that could be the basis of a better name?

T

--
Lawyer: (n.) An innocence-vending machine, the effectiveness of which depends
on how much money is inserted.
```
Feb 13 2015
"bearophile" <bearophileHUGS lycos.com> writes:
```H. S. Teoh:

Maybe that could be the basis of a better name?

Right.

Bye,
bearophile
```
Feb 13 2015
"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
```On Friday, 13 February 2015 at 15:14:44 UTC, H. S. Teoh wrote:
Isn't it essentially floor(log_2(a)), mathematically speaking?
Maybe
that could be the basis of a better name?

integer log2:
https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogFloat
```
Feb 13 2015
"H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
```On Fri, Feb 13, 2015 at 07:54:32PM +0000, via Digitalmars-d-learn wrote:
On Friday, 13 February 2015 at 15:14:44 UTC, H. S. Teoh wrote:
Isn't it essentially floor(log_2(a)), mathematically speaking? Maybe
that could be the basis of a better name?

integer log2:
https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogFloat

So it could be called ilog2?

T

--
Being able to learn is a great learning; being able to unlearn is a greater
learning.
```
Feb 13 2015
"bearophile" <bearophileHUGS lycos.com> writes:
```H. S. Teoh:

So it could be called ilog2?

Perhaps floorIlog2? Isn't ilog2 a different function?

Bye,
bearophile
```
Feb 13 2015
"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
```On Friday, 13 February 2015 at 22:39:10 UTC, bearophile wrote:
H. S. Teoh:

So it could be called ilog2?

Perhaps floorIlog2? Isn't ilog2 a different function?

Bye,
bearophile

I think the naming depends on use context, so it is reasonable to
land on different names in different domains. Maybe the standard
notation should be ffs(x):

http://en.wikipedia.org/wiki/Find_first_set

I like to think of it as position of most significant bit,
msbpos(x), but the trouble with non "log2" names is that you have
to decide wether to count from 0 or 1...

The advantage with counting from 1 is that ffs(0) could be 0,
whereas with counting from 0 you need to return -1 or fail...

Maybe one should have both, "log2" that fails and a msb-counting
one that does not fail.
```
Feb 14 2015
"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
```On Saturday, 14 February 2015 at 08:01:27 UTC, Ola Fosheim
I think the naming depends on use context, so it is reasonable
to
land on different names in different domains. Maybe the standard
notation should be ffs(x):

Oops, I meant fls(x)... I just woke up :-P. It is a bad name
anyway... first and last, left or right...?

"msb position" or "integer log2" in some form is better... Just
```On Monday, 19 January 2015 at 20:54:50 UTC, Steven Schveighoffer