Fast 2D matrix of bits

[Josh Simmons]

On Tue, Sep 20, 2011 at 10:24 AM, bearophile <bearophileHUGS at lycos.com> wrote:
> Timon Gehr:
>
>> The implementation uses int and uint everywhere. I think it is not 64
>> bit aware?
>
> I have not even tried it on a 64 bit system.
>
>
>>  > // sizex_, sizey_ are signed to catch negative arguments bugs.
>>
>> There would be no negative arguments if they were unsigned.
>
> For me a huge unsigned value that I can't catch in the ctor precondition is worse than a negative value that I am able to catch. I don't need to create a 2D matrix with sides bigger than int.max.
> I agree that all the other methods are probably better with size_t arguments. I'll fix it.
>
>
>> Why is it slower?
>
> Ask it to LDC1 developers :-)
> Adding that method is easy, if you want it. And I agree it's handy, with syntax mat[x,y] = true/false.
> But note the preferred methods to use this matrix are set/reset, because they are faster than the assign. I'll think about it.
>
>
>> But the signedness of index makes some
>> straightforward optimizations very hard to carry out for the compiler.
>> [...] but it has to emit something more to cope with (im)possible negative values)
>
> Right, index needs to be uint or size_t. I'll fix it.
>
> Thank you for your suggestions and notes,
> bye,
> bearophile
>

Zero is a power of two too :(

You could also just...

uint32_t next_pow_2(uint32_t n)
{
    n -= 1;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}