Various small improvements for std.bitmanip.BitArray

[dlangBugzillaToGithub]

bearophile_hugs reported this on 2013-06-02T05:08:32Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=10238

Description

Split from Issue 4124.

I suggest to add some useful methods to BitArray:
- 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


After Issue 4124 "%b" (unlike "%s") produces a string output that's not usable to build a new BitArray, this is another enhancement request (underscores and leading-trailing whitespace should be ignored):


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");
}

- - - - - - - - - -

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);
}

[dlangBugzillaToGithub]

bearophile_hugs commented on 2013-06-02T05:11:01Z

See also Issue 10239