Comment #0 by bearophile_hugs — 2010-04-24T16:26:12Z
A toString() method for std.bitmanip.BitArray is useful. It can use a simple representation like the Python bitarray:
0101001010100001
Or as java.util.BitSet (but I prefer the Python version):
{1, 3, 6, 8, 10, 15}
Other methods useful for BitArray:
- reset all bits
- set all bits
- are all bit set?
- are all bit reset?
- count set bits (there are _very_ efficient algorithms to do this).
- set n-th bit (this can be a little more efficient than bs[n]=1;)
- reset n-th bit (this can be a little more efficient than bs[n]=1;)
- flip n-th bit
I think the sort() method of BitArray is not commonly useful.
Comment #1 by bearophile_hugs — 2011-10-13T11:22:06Z
Maybe the usefulness of isSet(), set(), and reset() methods is visible with two benchmarks. They implement the same algorithm (a simple sieve), the first uses a BitArray, and the second a manually implemented bit array. On my 32 bit system the second program is about two times faster than the first one.
import std.stdio, std.algorithm, std.range, std.math, std.bitmanip, std.datetime;
uint[] primes(uint n) {
if (n < 2) return [];
BitArray F;
F.length = n + 1;
F[0] = true;
F[1] = true;
foreach (i; 2 .. cast(uint)sqrt(n))
if (!F[i])
for (uint j = i * i; j <= n; j += i)
F[j] = true;
return array(filter!((i){ return !F[i]; })(iota(n+1)));
}
void main() {
StopWatch sw;
sw.start();
primes(30_000_000);
sw.stop();
writeln(sw.peek().msecs / 1000.0);
}
import std.stdio, std.algorithm, std.range, std.math, std.datetime;
size_t[] primes(in size_t n) {
enum size_t bpc = size_t.sizeof * 8;
auto F = new size_t[n / bpc + 1];
F[] = size_t.max;
bool isSet(in size_t i) nothrow {
immutable size_t offset = i / bpc;
immutable size_t mask = 1 << (i % bpc);
return (F[offset] & mask) != 0;
}
void clear(in size_t i) nothrow {
immutable size_t offset = i / bpc;
immutable size_t mask = 1 << (i % bpc);
if ((F[offset] & mask) != 0)
F[offset] = F[offset] ^ mask;
}
clear(0);
clear(1);
foreach (i; 2 .. cast(size_t)sqrt(n))
if (isSet(i))
for (uint j = i * i; j <= n; j += i)
clear(j);
return array(filter!isSet(iota(n + 1)));
}
void main() {
StopWatch sw;
sw.start();
size_t n = primes(30_000_000).length;
sw.stop();
writeln(sw.peek().msecs / 1000.0);
writeln("n primes: ", n);
}
Comment #2 by andrej.mitrovich — 2013-01-25T11:50:14Z
It can use a simple
representation like the Python bitarray:
0101001010100001
What about this instead:
0101_0010_1010_0001
I think it would also be useful to be able to initialize a bitarray with an integral literal, e.g.:
BitArray bta = bitArray!0101_0010_1010_0001;
It would statically check that all digits are 0 or 1 (is there a bit twiddling trick for this?).
Comment #3 by andrej.mitrovich — 2013-01-25T11:50:35Z
(In reply to comment #2)
> It can use a simple
> representation like the Python bitarray:
> 0101001010100001
That should have been a quote.
Comment #4 by andrej.mitrovich — 2013-02-17T17:03:02Z
Comment #5 by bearophile_hugs — 2013-02-17T17:24:18Z
(In reply to comment #4)
> It would help if you didn't make multiple feature requests in a single entry.
When I am asking things like this for a single struct of Phobos:
- reset all bits
- set all bits
Is it right to create two different enhancement requests for those two things?
Comment #6 by andrej.mitrovich — 2013-02-17T17:28:06Z
(In reply to comment #5)
> (In reply to comment #4)
> > It would help if you didn't make multiple feature requests in a single entry.
>
> When I am asking things like this for a single struct of Phobos:
>
> - reset all bits
> - set all bits
>
> Is it right to create two different enhancement requests for those two things?
One would be enough since they're highly related. toString is largely unrelated to this though.
Comment #7 by github-bugzilla — 2013-06-01T07:32:37Z
Comment #8 by bearophile_hugs — 2013-06-01T20:04:36Z
(In reply to comment #7)
> Commits pushed to master at https://github.com/D-Programming-Language/phobos
>
> https://github.com/D-Programming-Language/phobos/commit/4f5079e4f8d38e1d469e4b28303553f36f49e33b
> Fixes Issue 4124 - Implement toString for BitArray.
>
> https://github.com/D-Programming-Language/phobos/commit/9d331e2dc43a590c486c1b4862c0b1173b2f6799
> Merge pull request #1144 from AndrejMitrovic/Fix4124
>
> Issue 4124 - Implement toString for BitArray.
Thank you. This introduces a good toString for BitArray. Then I will move elsewhere the missing things.
I think this stuff can go in a single enhancement request because they are easy and short to implement:
- reset all bits
- set all bits
- are all bit set?
- are all bit reset?
- set n-th bit (this can be a little more efficient than bs[n]=1;)
- reset n-th bit (this can be a little more efficient than bs[n]=1;)
- flip n-th bit
Maybe it's better to move this into a separated ER because it looks simple but implementing a pop count very efficiently is not so easy:
- count set bits
----------------
Now (unlike "%s") "%b" produces a string output that's not usable to build a new BitArray, maybe this is another worth enhancement request:
import std.stdio, std.bitmanip, std.conv, std.string;
void main() {
BitArray b1;
b1.init([0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]);
writefln("%b", b1); // Prints: 00001111_00001111
BitArray b2;
// Error: function std.bitmanip.BitArray.init (bool[] ba)
// is not callable using argument types (string)
b2.init("00001111_00001111");
}
Comment #9 by bearophile_hugs — 2013-06-02T04:59:14Z