Re: Number of Bits Needed to Represent a Zero-Offset Integer
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.
Re: Number of Bits Needed to Represent a Zero-Offset Integer
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.
Re: Number of Bits Needed to Represent a Zero-Offset Integer
H. S. Teoh: So it could be called ilog2? Perhaps floorIlog2? Isn't ilog2 a different function? Bye, bearophile
Re: Number of Bits Needed to Represent a Zero-Offset Integer
On Fri, Feb 13, 2015 at 07:54:32PM +, 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.
Re: Number of Bits Needed to Represent a Zero-Offset Integer
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
Re: Number of Bits Needed to Represent a Zero-Offset Integer
H. S. Teoh: Maybe that could be the basis of a better name? Right. Bye, bearophile
Re: Number of Bits Needed to Represent a Zero-Offset Integer
On Fri, Feb 13, 2015 at 12:28:23PM +, 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.
Re: Number of Bits Needed to Represent a Zero-Offset Integer
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
Re: Number of Bits Needed to Represent a Zero-Offset Integer
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?
Re: Number of Bits Needed to Represent a Zero-Offset Integer
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; } }
Re: Number of Bits Needed to Represent a Zero-Offset Integer
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.
Re: Number of Bits Needed to Represent a Zero-Offset Integer
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
Re: Number of Bits Needed to Represent a Zero-Offset Integer
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 :)
Re: Number of Bits Needed to Represent a Zero-Offset Integer
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
Re: Number of Bits Needed to Represent a Zero-Offset Integer
On 1/19/15 10:49 AM, "Per =?UTF-8?B?Tm9yZGzDtnci?= " 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
Re: Number of Bits Needed to Represent a Zero-Offset Integer
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
Re: Number of Bits Needed to Represent a Zero-Offset Integer
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
Re: Number of Bits Needed to Represent a Zero-Offset Integer
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?
Re: Number of Bits Needed to Represent a Zero-Offset Integer
On 1/19/15 7:04 AM, "Per =?UTF-8?B?Tm9yZGzDtnci?= " wrote: As a follow-up to http://forum.dlang.org/thread/fdfwrdtjcawprvvko...@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
Re: Number of Bits Needed to Represent a Zero-Offset Integer
On Mon, 19 Jan 2015 12:04:38 + via Digitalmars-d-learn wrote: > As a follow-up to > > http://forum.dlang.org/thread/fdfwrdtjcawprvvko...@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; signature.asc Description: PGP signature
Re: Number of Bits Needed to Represent a Zero-Offset Integer
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 = [ 0xUL, 0xUL, 0xFF00UL, 0x00F0UL, 0x000CUL, 0x0002UL]; 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
Re: Number of Bits Needed to Represent a Zero-Offset Integer
On Monday, January 19, 2015 12:04:38 via Digitalmars-d-learn wrote: > As a follow-up to > > http://forum.dlang.org/thread/fdfwrdtjcawprvvko...@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