Bit Manipulation in Matrix

This is a discussion on Bit Manipulation in Matrix within the C Programming forums, part of the General Programming Boards category; Here's my code. It's supposed to take an array of bits (size MAX, whatever I want MAX to be) and ...

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    38

    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?

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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?

  3. #3
    Registered User
    Join Date
    Nov 2008
    Posts
    38
    Quote Originally Posted by tabstop View Post
    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?

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by DonFord81 View Post
    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.

  5. #5
    Registered User
    Join Date
    Nov 2008
    Posts
    38
    Quote Originally Posted by tabstop View Post
    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.

  6. #6
    Registered User
    Join Date
    Jan 2008
    Posts
    287
    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.

  7. #7
    Registered User
    Join Date
    Nov 2008
    Posts
    38
    Thank you! I'll try them...

  8. #8
    Registered User
    Join Date
    Jan 2008
    Posts
    287
    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.

  9. #9
    Registered User
    Join Date
    Nov 2008
    Posts
    38
    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?

  10. #10
    Registered User
    Join Date
    Jan 2008
    Posts
    287
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C - access violation
    By uber in forum C Programming
    Replies: 2
    Last Post: 07-08-2009, 01:30 PM
  2. bit manipulation
    By dsupriya in forum C Programming
    Replies: 8
    Last Post: 03-05-2009, 08:36 AM
  3. Replies: 16
    Last Post: 11-23-2007, 12:48 PM
  4. bit manipulation
    By cblix in forum C Programming
    Replies: 6
    Last Post: 11-29-2005, 05:37 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21