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
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 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 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 ? x32 ? 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
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 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: 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
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 ? x32 ? 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 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 ? x32 ? core.bitop.bsr(x)+33 :
core.bitop.bsr(x)+1 : 0;
}
}
Re: Number of Bits Needed to Represent a Zero-Offset Integer
On 1/19/15 7:04 AM, Per =?UTF-8?B?Tm9yZGzDtnci?= per.nord...@gmail.com 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 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?
Number of Bits Needed to Represent a Zero-Offset Integer
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
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
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 Mon, 19 Jan 2015 12:04:38 +
via Digitalmars-d-learn digitalmars-d-learn@puremagic.com 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
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, 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 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 1/19/15 10:49 AM, Per =?UTF-8?B?Tm9yZGzDtnci?= per.nord...@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
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 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 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
