3

I want to create a matrix representation for a graph algorithm using the least memory possible.

So I decided to try using a bit representation of the values of the matrix, but I also know that doing this by C is (AFAIK) impossible, because a bit is not addressable.

Then I read a post here suggesting to use a struct that can help me do so by using, e.g., an int (4 bytes, so 32-bit) and, with some magic and bitshifts, use it as an "array" of bits.

Got that, but I can't really realize how exactly I could do this. I got confused...

I'm thinking about using a structure to store a int/void pointer to n bytes corresponding to the least number of bytes to the 'n' number of bits allocated and the 'k' number of bits in that representation, something such as that.

So I thought you could help me realize what's the best approach for this kind of solution.

Note: Why I'm so confused? I'm still graduating in Computer Science and I just started to study graphs. Also just finished a laboratory project on that (implemented it as a matrix but used some mathemagic to alloc only half of the matrix and represented it as symectrical), but I'm trying to extend the matter. Also because I got extremely curious :)

Thanks all.

P.S.: almost forgot, I'm programming this in C, but I can understand C++, .Net languages and Java very well. Thanks again.

0

2 Answers 2

1

There are a couple of tricky bits here: working on individual bits within a large array; and simulating a 2-dimensional array with a 1-dimensional one. It's best to solve these separately at first.

Start with some helper functions that let you work on individual bits. Something like:

typedef unsigned int BYTE;  /* Int type to use for data. */
#define BYTE_SIZE (sizeof(BYTE)*8)   /* How many bits in each one. */

void set_bit(BYTE *data, int pos, int value)
{
    int index = pos / BYTE_SIZE;   /* Which byte to adjust. */
    int offset = pos % BYTE_SIZE;  /* Which bit within it. */
    /* 1 << offset turns into the place value for the bit at offset. */
    /* x | 1 << offset sets the bit there (an OR operation);
       ~(1 << offset) gets something with all bits except that bit set, and
       x & ~(1 << offset) clears the bit with an AND operation on x. */
    if (value)
        data[index] = data[index] | (1 << offset);
    else
        data[index] = data[index] & ~(1 << offset);
}

int test_bit(int *data
{
    int index = pos / BYTE_SIZE;
    int offset = pos % BYTE_SIZE;
    /* An AND operation to see if the bit is set, then compare against 0
       so that 1 or 0 is returned instead of the place value. */
    return (data[index] & (1 << offset)) != 0;
}

You then move up a level with a structure to hold the array of bytes, and some data about the dimensions. A 2-dimensional array can be simulated with a 1-d one, by translating a an operation on bit (x,y) to one on bit y*width+x.

struct BITMATRIX
{
    BYTE *data;
    int width;
    int height;
}

void set_bit_matrix(struct BITMATRIX *bm, int x, int y, int value)
{
    int pos = y * bm->width + x;
    set_bit(bm->data, pos, value);
}

/* Etc. */
3
  • 2
    Both answers do the job (already tested!), but this one actually gives me some of the algorithms I was trying to find. Thanks, Edmund :)
    – Giuliano
    Nov 21, 2010 at 17:30
  • 1
    this answer deserves a lot of upvotes... Strictly speaking, your answer was great!!! Jul 21, 2020 at 7:37
  • github.com/Abhishekghosh1998/SO/blob/master/bit_matrix.c my implementation based on the concept stated by @Edmund Jul 21, 2020 at 10:21
1

Just a comment on bit structs in C - take a look here:

These should be good pointers on how you should use bit structs.

5
  • Interesting! Didn't know that operator ':', so I don't need to be a bit-wizard then, haha. But, Unfortunatelly, as described in C99 Standards: "The operand of the unary & operator shall be either a function designator, the result of a [] or unary * operator, or an lvalue that designates an object that is not a bit-field and is not declared with the register storage-class specifier." So bit-fields are one possible answer, but I can't make arrays or matrixes from them. By the way, loved to know I can work with bits that way, Thanks! :D
    – Giuliano
    Nov 20, 2010 at 22:18
  • Glad it's useful. Rusty on C, so not saying it's not true, but not sure I follow the restriction from what you said. The above is just a restriction on & operator (i.e. you cannot do a.b & c, where a.b is a bit-field), but I don't think this says you cannot make an array of a. Nov 20, 2010 at 22:30
  • You can, but of the struct, not the type. Yet it suffices. What I was trying to show on that restriction is that you cannot extract an address from one bit. The & operator acts giving you an address, and it says you can't use it on bit-fields. So bit-fields cannot be directly declared as arrays. It's almost a corollary =)
    – Giuliano
    Nov 21, 2010 at 4:40
  • That's true, but I suppose it's going to allow you to make a helper function rather easy. If your struct is byte-oriented, then you need a get/set function part that just divides the address by 8 and then a simple switch to get/set the appropriate bit. Of course, your appetites might be greater :) Nov 21, 2010 at 4:44
  • You are welcome - hope it's going to work out well one way or another. Nov 21, 2010 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.