How do I best implement a matrix of bits?

Question

I need a matrix that holds only 1 or 0 for each element. What is the least costly way to do this regarding memory and processor usage?

My current direction is an array of arrays with each element as an int(weakly typed). Because each int, is either 32 or 64 bits depending upon the platform, I have 32/64 sub elements per element. Is there a solution that already exists so that I don't have to reinvent the wheel?

You can only optimize this for memory ***OR*** processor usage. Not both. Most memory-efficient is compacting that into a string of \0 and \1 chars. (If it's a 2D matrix, you need to manually manage the offset calculation). Using a normal PHP array is memory-costly regardless of int/boolean values. — mario, May 11 '11 at 23:32
@Yoel You should totally put that as an answer. Duh, make each element a bool. — ghoppe, May 11 '11 at 23:33
@Mario so a bool takes up more than a bit? Can I look up these constants like I can for an int, PHP_INT_SIZE = 4 for example? — , May 11 '11 at 23:53
@Chris. Yes. (You cannot look it up with any constants however). Internally PHP stores only integers. It keeps a separate type specifier. But there is no way to have bitfields with a default PHP installation. -- You can fake one, but it's not going to be very fast: http://stackoverflow.com/questions/5505124/cheating-php-integers/5505643#5505643 — mario, May 11 '11 at 23:56

KingCrunch · Accepted Answer · 2011-05-12T00:05:45.377

0

nxm Bitmask describes as array of int

// setting bit in $ix$j 
$array[$i] = $array[$i] |  pow(2,$j);
// unsetting bit in $ix$j 
$array[$i] = $array[$i] & ~ pow(2,$j);
// test, if bit in $ix$j is set
$array[$i] & pow(2,$j);

Its untested ;)

its something like that you are looking for?

As a bonus its very easy to initialize it

$array = array_fill(0, $n, 0);

edited May 12 '11 at 00:05

answered May 11 '11 at 23:58

KingCrunch

128,817
21
151
173

Actually, switched to C but bitwise logic looks good. Could even add push and pop type functionality with shift operators << >> in C where the unsigned type is available. – May 13 '11 at 22:45

score -1 · Answer 2 · answered May 11 '11 at 23:33

-1

I don't get it...

This is php - easy as pie...

$mat=array();
for ($i=0; $i<10;$i++)
{ 
  $mat[$i]=array();

  for($j=0;$j<10;$j++)
    $mat[$i][$j]=False;
}

Oh, and use boolean - much cheaper

answered May 11 '11 at 23:33

fingerman

2,440
4
19
24

A boolean consumes more than one bit as you can read in the comments of Yoels answer, as well as the comments of the question itself. You should describe, why you think its "much cheaper". – KingCrunch May 12 '11 at 00:09
much cheaper in terms of afterwards checking the array with if($mat[1][1]) :D – fingerman May 12 '11 at 00:47

How do I best implement a matrix of bits?

2 Answers2