digitalmars.D.learn - Number of Bits Needed to Represent a Zero-Offset Integer
- "Per =?UTF-8?B?Tm9yZGzDtnci?= <per.nordlow gmail.com> (16/16) Jan 19 2015 As a follow-up to
- Jonathan M Davis via Digitalmars-d-learn (41/57) Jan 19 2015 I had this lying around in one of my projects:
- bearophile (31/33) Jan 19 2015 //
- ketmar via Digitalmars-d-learn (17/37) Jan 19 2015 xudiyoygnvvbovhjfgt:40forum.dlang.org
- Steven Schveighoffer (6/22) Jan 19 2015 http://dlang.org/phobos/core_bitop.html#.bsr
- "Per =?UTF-8?B?Tm9yZGzDtnci?= <per.nordlow gmail.com> (5/9) Jan 19 2015 Nice. Is this intrinsic supported for all DMD/GCD/LDC supported
- Steven Schveighoffer (6/14) Jan 19 2015 I'm fairly certain it's supported as an intrinsic there. BSR is an X86
- Jonathan M Davis via Digitalmars-d-learn (6/9) Jan 19 2015 Sadly, I don't think that it have occurred to me from just reading the d...
- Steven Schveighoffer (26/46) Jan 19 2015 It tells you the most significant bit that is set. That is what you are
- Jonathan M Davis via Digitalmars-d-learn (7/23) Jan 19 2015 Yes. But if I'm looking for a function that tells me how many bits are
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (5/8) Jan 19 2015 This works for me
- Steven Schveighoffer (4/11) Jan 19 2015 Cool. I would point out that the commented code suggests you should be
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (5/8) Jan 19 2015 I believe that should trigger a failing static assert with a good
- Dominikus Dittes Scherkl (18/26) Jan 20 2015 I would recommend to use something like this:
- bearophile (5/22) Feb 13 2015 Is this good to be added to Phobos? Perhaps with a more
- H. S. Teoh via Digitalmars-d-learn (7/27) Feb 13 2015 [...]
- bearophile (4/5) Feb 13 2015 Right.
- "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= (3/6) Feb 13 2015 integer log2:
- H. S. Teoh via Digitalmars-d-learn (5/11) Feb 13 2015 So it could be called ilog2?
- bearophile (4/5) Feb 13 2015 Perhaps floorIlog2? Isn't ilog2 a different function?
- "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= (12/17) Feb 14 2015 I think the naming depends on use context, so it is reasonable to
- "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= (6/10) Feb 14 2015 Oops, I meant fls(x)... I just woke up :-P. It is a bad name
- "Per =?UTF-8?B?Tm9yZGzDtnci?= <per.nordlow gmail.com> (3/6) Feb 13 2015 Should I do a Phobos PR for this? If so where should I put it?
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
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 usageI 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
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
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 usagetemplate 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
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 usageIt's actually an intrinsic, reduces to an instruction. Mind the requirements for 0. -Steve
Jan 19 2015
On Monday, 19 January 2015 at 13:30:47 UTC, Steven Schveighoffer wrote:It's actually an intrinsic, reduces to an instruction. Mind the requirements for 0. -SteveNice. 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
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: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. -SteveIt'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?
Jan 19 2015
On Monday, January 19, 2015 08:30:47 Steven Schveighoffer via Digitalmars-d-learn wrote: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
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: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: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 Davisvalue-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 => 4Output 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
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: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 DavisOn Monday, January 19, 2015 08:30:47 Steven Schveighoffer via Digitalmars-d-learn wrote:It tells you the most significant bit that is set. That is what you are looking for, no?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
On Monday, 19 January 2015 at 13:30:47 UTC, Steven Schveighoffer wrote: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
On 1/19/15 3:46 PM, "Nordlöw" wrote:On Monday, 19 January 2015 at 13:30:47 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) -SteveIt'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
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
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: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; } }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 20 2015
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
On Fri, Feb 13, 2015 at 12:28:23PM +0000, bearophile via Digitalmars-d-learn wrote:Dominikus Dittes Scherkl:[...] 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.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?
Feb 13 2015
H. S. Teoh:Maybe that could be the basis of a better name?Right. Bye, bearophile
Feb 13 2015
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
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:So it could be called ilog2? T -- Being able to learn is a great learning; being able to unlearn is a greater learning.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:So it could be called ilog2?Perhaps floorIlog2? Isn't ilog2 a different function? Bye, bearophile
Feb 13 2015
On Friday, 13 February 2015 at 22:39:10 UTC, bearophile wrote:H. S. Teoh: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.So it could be called ilog2?Perhaps floorIlog2? Isn't ilog2 a different function? Bye, bearophile
Feb 14 2015
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
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