www.digitalmars.com         C & C++   DMDScript  

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

reply "Per =?UTF-8?B?Tm9yZGzDtnci?= <per.nordlow gmail.com> writes:
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
Jan 19 2015
next sibling parent 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

 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
Jan 19 2015
prev sibling next sibling parent "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
prev sibling next sibling parent 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
 http://forum.dlang.org/thread/fdfwrdtjcawprvvkoqas forum.dlang.org#post-q=
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
prev sibling parent reply 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

 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
Jan 19 2015
next sibling parent reply "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
parent 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
prev sibling next sibling parent reply 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
parent reply 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
parent 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
prev sibling parent reply =?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
parent reply 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
next sibling parent reply =?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
parent reply "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
parent reply "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
parent reply "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
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
H. S. Teoh:

 Maybe that could be the basis of a better name?
Right. Bye, bearophile
Feb 13 2015
prev sibling parent reply "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
parent reply "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
parent reply "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
parent reply "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
parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Saturday, 14 February 2015 at 08:01:27 UTC, Ola Fosheim
Grøstad wrote:
 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 "floor log2" with overloading might be good enough.
Feb 14 2015
prev sibling parent "Per =?UTF-8?B?Tm9yZGzDtnci?= <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)
Should I do a Phobos PR for this? If so where should I put it?
Feb 13 2015