Thread: Bit Manipulation in Matrix

Here's my code. It's supposed to take an array of bits (size MAX, whatever I want MAX to be) and arrange them into a MAX-by-MAX two-dimensional array for printing to screen. I can't tell which of my functions (or the if/printf itself) is causing the current odd behavior.

Initially, I zero out the entire array, make the matrix based on the array, and then display both. Then, I invert the entire array (change all 0's to 1's - and theoretically vice versa, but I've only got 0's to start with), and make the matrix and display again. Only not all the entries in the new matrix are 1's. The example with MAX = 6 is shown below, after the code.

Code:

#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <limits.h>		/* for CHAR_BIT */

#define MAX 6
#define BITMASK(b) (1 << ((b) % CHAR_BIT))
#define BITSLOT(b) ((b) / CHAR_BIT)
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
#define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))
#define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)

void increment(char* bitarray, int n);
int test_all_zero(char* bitarray, int n);
void one_diag(char [][BITNSLOTS(MAX)], int n);
void make_matrix(char [][BITNSLOTS(MAX)], char* U_array, int n);
void invert(char* bitarray, int n);
void display(char [][BITNSLOTS(MAX)], int n);

main(){
       char bitarray[MAX][BITNSLOTS(MAX)];
       int i,j;
       for (i=0; i<MAX; i++){
           memset(bitarray[i], 0, BITNSLOTS(MAX));
           }
       
       char U_array[BITNSLOTS(MAX*(MAX-1)/2)];
       memset(U_array, 0, BITNSLOTS(MAX*(MAX-1)/2));

       /* TEST CODE START */
       char test_array[BITNSLOTS(MAX*(MAX-1)/2)];
       memset(test_array, 0, BITNSLOTS(MAX*(MAX-1)/2));
       
       char test_matrix[10][BITNSLOTS(MAX)];
       for (i=0; i<MAX; i++){
           memset(test_matrix[i], 0, BITNSLOTS(MAX));
           }
       
       printf("Starting:\n");
       
       for (i=0; i<(MAX*(MAX-1)/2); i++){
           if (BITTEST(test_array, i)){
              printf("1");
              }
           else{
                printf("0");
                }
           }
       printf("\n");
       
       make_matrix(test_matrix, test_array, MAX);
       display(test_matrix, MAX);
          
       printf("Inverting:\n");
       
       while (test_all_zero(test_array, MAX*(MAX-1)/2)){
             invert(test_array, MAX*(MAX-1)/2);
             }
       
       for (i=0; i<(MAX*(MAX-1)/2); i++){
           if (BITTEST(test_array, i)){
              printf("1");
              }
           else{
                printf("0");
                }
           }
       printf("\n");
       
       make_matrix(test_matrix, test_array, MAX);
       one_diag(test_matrix, MAX);
       display(test_matrix, MAX);  
       /* TEST CODE END */

       getch();
}

void increment(char* bitarray, int n){
     int i = 0;
     while (i < n){
           if (!BITTEST(bitarray, i)){
              BITSET(bitarray, i);
              i = n;
              }
           else{
                BITCLEAR(bitarray, i);
                i++;
                }
           }
}
                
int test_all_zero(char* bitarray, int n){
    int i;
    int counter = 0;
    for (i=0; i<n; i++){
        if (!BITTEST(bitarray, i)){
           counter++;
           }
        }
    if (counter == n){
       return 1;
       }
    else{
         return 0;
         }
}

void one_diag(char bitarray[][BITNSLOTS(MAX)], int n){
     int i,j;
     for (i=0; i<n; i++){
         for (j=0; j<n; j++){
             if (i == j){
             BITSET(bitarray[i], j);
             }
         }
     }
}

void invert(char* bitarray, int n){
     int i;
     for (i=0; i<n; i++){
         if (BITTEST(bitarray, i)){
            BITCLEAR(bitarray, i);
            }
         else{
              BITSET(bitarray, i);
              }
         }
}

void make_matrix(char bitarray[][BITNSLOTS(MAX)], char* U_array, int n){
     int i,j,k;
     for (i=0,j=i+1,k=0; k<((n*(n-1))/2); j++,k++){
         if (j > n){
            i++;
            j = i+1;
            }
         if (BITTEST(U_array, k)){
            BITSET(bitarray[i], j);
            BITSET(bitarray[j], i);
            }
         else{
              BITCLEAR(bitarray[i], j);
              BITCLEAR(bitarray[j], i);
              }
         }
}

void display(char bitarray[][BITNSLOTS(MAX)], int n){
     int i, j;
     for (i=0; i<n; i++){
         for (j=0; j<n; j++){
             if (BITTEST(bitarray[i], j)){
                printf("1");
                }
             else{
                  printf("0");
                  }
             }
         printf("\n");
         }
     printf("\n");
}

Here's the output of MAX = 6:

Code:

Starting:
000000000000000
000000
000000
000000
000000
000000
000000

Inverting:
111111111111111
111111
111111
111111
111100
111010
111001

The second matrix should be all 1's. What's going on?

Your test_array would appear to have 15 bits in it (6*5/2 is 15). How do you expect to turn 15 bits into a 6x6 array? Why wouldn't you want 36 bits in your test_array?

Originally Posted by tabstop

Your test_array would appear to have 15 bits in it (6*5/2 is 15). How do you expect to turn 15 bits into a 6x6 array? Why wouldn't you want 36 bits in your test_array?

The test_array only creates the "upper" or "U" part of the matrix. The matrix itself should be symmetric along the diagonal (entry[i][j] == entry[j][i]), and since I want the diagonal to be all 1's, I can set those myself. Thus, I only need half the remaining spots, or (36-6)/2 = 15 elements in my array.

Make sense?

Originally Posted by DonFord81

The test_array only creates the "upper" or "U" part of the matrix. The matrix itself should be symmetric along the diagonal (entry[i][j] == entry[j][i]), and since I want the diagonal to be all 1's, I can set those myself. Thus, I only need half the remaining spots, or (36-6)/2 = 15 elements in my array.

Make sense?

Your U_array needs 15 bits, yes. That doesn't have any relationship with the size of your test_array, though.

Originally Posted by tabstop

Your U_array needs 15 bits, yes. That doesn't have any relationship with the size of your test_array, though.

I probably shouldn't have included the main bitarray or main U_array, as they are not called in the test code.

test_array is the test version of U_array, and test_matrix is the test version of bitarray.

test_all_zero():

Looping through each individual bit is not the optimal way to check if all bits are zero... Plus, you don't need to keep looping if you find out one of the bits isn't zero.

one_diag():

You are going to loop through every element in the matrix just to set the diagonal? There's no need, just loop along the diagonal.

invert():

Once again, looping through each individual bit is slow when you consider the XOR operator can perform this on an entire char in one operation.

Regarding the problem you're having:

Code:

void make_matrix(char bitarray[][BITNSLOTS(MAX)], char* U_array, int n){
     int i,j,k;
     for (i=0,j=i+1,k=0; k<((n*(n-1))/2); j++,k++){
         if (j > n){
            i++;
            j = i+1;
            }

When j == n it is also out of bounds, but you only check if j > n. This is most likely your problem. It will cause an undetected off-by-one error because the extra one will just wrap around to the next row.

Thank you! I'll try them...

If you do take the suggestions for test_all_zero() and invert(), keep in mind that the last char in your bitarray will most likely be an exception unless the number of bits in your bitarray is an exact multiple of CHAR_BIT.

You can use fast bitwise operation on all the other chars in your array, but the very last char may need special handling.

Code:

A bit array storing 10 bits:

Char 1    Char 2
00101101  00??????

You probably don't want to test char2 against zero, because those unknown bits might throw things off.

Including the "=" in "if (j > n)" solved the problem with the matrix.

My new question is: how would I go about using XOR? Wouldn't I have to make an entire array of 1's to do (bitarray ^ 1), or at least cycle through every bit?

You would cycle through every char, not every bit.

Code:

invert:
   foreach char b in bitarray
      b ^= 0xFF

This immediately cuts the number of operations you need to perform by a factor of CHAR_BIT. Actually, its better than that, since you are avoiding all those bitshifts and modulus operations inherent in single-bit operations.