2d boolean array using n^2 bits of space

Question

I need a 2d n by n boolean array that uses as close to n^2 bits of memory as possible. The operations I need are to be able quickly to set and read individual bits indexed by their (x,y) coordinate. Is there a nice way to do this in python and/or numpy?

@DhruvPathak That's nice. To make it 2d and be able to access a bit easily, what is the simplest way? — marshall, Nov 28 '13 at 18:52
@marshall You can use any 1d array as a 2d array (of fixed dimensions) by doing something like `a[x + y * w]`, where `x` and `y` begin at zero and the 2d array has constant width `w` (by "constant width" I mean each row has the same width), and where the 1d array `a` has size `w * h` (where `h` is the height of the 2d array) — alecbz, Nov 28 '13 at 19:17

score 2 · Accepted Answer · answered Nov 28 '13 at 20:06

If you want a DIY solution with numpy, the following could be a starting point:

a = np.zeros((n, (n-1)//8+1), dtype=np.uint8)
# to set to zero
a[x, y//8] &= 255 - (1 << (y%8))
# to set to one
a[x, y//8] |= (1 << (y%8))
#to read
(a[x, y//8] >> (y % 8)) & 1

2d boolean array using n^2 bits of space

1 Answers1