Thread: Bit shifting with matrices

  1. #1
    Registered User OnionKnight's Avatar
    Join Date
    Jan 2005
    Posts
    555

    Bit shifting with matrices

    This time I've read the FAQ before posting!
    Alright, so I have a part in my code that looks like this:
    Code:
    for (i = 0; i < size; i++) {
    	snakepos[size - i][0] = snakepos[size - (i + 1)][0];
    	snakepos[size - i][1] = snakepos[size - (i + 1)][1];
    }
    It moves the snake's bodyparts X and Y position backwards in the matrix. Later, the new position for the head is added but I didn't include that part.
    I noticed that on slower computer (e.g. thos in my school) the game started to lag a bit as the snake got longer which I can understand.
    So I wanted to optimize a bit and replace it with something and I remembered that bit shifting moves stuff backwards and forwards.
    I tried replacing it with something like:
    Code:
    snakepos[0][0]>>16;
    snakepos[0][1]>>16;
    snakepos[0][0] = snakepos[1][0];
    snakepos[0][1] = snakepos[1][1];
    It's shifted by 16 bits because snakepos is declared as a short. I've done some mixing by excluding some of the things like snakepos[0][1] because I though snakepos[0][0]>>16 shifted the whole matrix but neither way worked.
    Code:
    snakepos[0][0] = snakepos[1][0];
    snakepos[0][1] = snakepos[1][1];
    Are there because I use plus and minus to change position and thus it would be bad if those were empty all the time (meaning that the snake would constantly be in one place the whole time)

    So is this possible or should I stick with the for loop? Or is there some other way?

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    No. It doesn't shift the array. It simply finds whatever value is at "snake[0][0]" and shifts it.

    You could always do something like a double linked list, with a pointer to the head and tail, and just pop the end off and add a new head. Then you just change whatever position is stored in the "tail" back to a space.

    If you were using something like the curses library, all it would ever do is redraw 2 tiles at a time, instead of redrawing the whole thing.

    Or, if you don't want to use a linked list, use a single array that is maximum_snake_size pieces long, and a pair of pointers to walk through the array, keeping track of the head and tail, as you would with the linke list. Either use an array of structures which contain the x and y coordinates, or a pair of arrays, each one being one of the two dimensions. If the pointer you're inrementing or decrementing would run off the end of the array, you position it to the other end. (Basicly like a 'stack' implementation using an array.)

    Quzah.
    Last edited by quzah; 02-04-2005 at 06:21 PM.
    Hope is the first step on the road to disappointment.

  3. #3
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    No. It doesn't shift the array. It simply finds whatever value is at "snake[0][0]" and shifts it.
    This would get around that, if you can change those size - i statments to reference the column instead of the row.
    Code:
    long * p1 = &snakepos[0][size - i];
    long * p2 = &snakepos[1][size - i];
    
    *p2 >>= 16; 
    *p1 >>= 16;
    if you can't achieve that, which you very well may not depending on what results you want, you can always try unrolling the loop (if this is indeed what is slowing down the application).

    edit: changing the matrix so that the size - i statement can control the column reference may make it faster as is, simply because it would make cache happier. Again though, it depends if that still produces the desired effect.
    Last edited by skorman00; 02-05-2005 at 09:45 AM.

  4. #4
    Registered User OnionKnight's Avatar
    Join Date
    Jan 2005
    Posts
    555
    quzah: I don't even know what a linked list is :/

    skorman00: How does it differ from what I tried? Apart from the >>= which I missed.

  5. #5
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    You were bit shifting a short, which is 16 bits. It doesn't shift it into the next column, the extra 1's and 0's just go away. I made the compiler think it was a long, which is 32 bits, so the value in the next column is included in the shift.

    let's say this is your matrix mat[3][3]

    [ 0 ] [ 1 ] [ 2 ]
    [ 3 ] [ 4 ] [ 5 ]
    [ 4 ] [ 5 ] [ 6 ]
    Code:
    short * pShort = &mat[0][0];
    long  * pLong = (long *)&mat[0][0];
    
    printf ("short = %d \nlong = %d", *pShort, *pLong);
    
    <output>
    short = 0   
    long = 4
    The pShort only references the first element, but pLong references the first two. When you combine their bit patterns, it comes out to be 4 (if you're on a little endian system).

    Code:
       
    values      binary (short)        binary (long)
    [0] [1] = [00 00] [01 00] =   [00 00 01 00] = 4
    You can learn about endian-ness (if that's a word) easily on these forums, but it won't effect the behavior of your bit shift. It would only effect the output of printf() call I have in that example. The point is is that when you convert it to a long, you are dealing with more bits. I believe this will give you what you want.

    Like I said, that only works if you're dealing with the column as the variable instead of the row. That's because in memory, the matrix above looks like this:
    Code:
    [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 4 ] [ 5 ] [ 6 ]
    So you wouldn't be able to use the bitshift trick if your trying to swap values that are in different rows.

    PS: Good way to go about optimizing. You only thought about it when it presented a problem (slow on older machines), and I'm assuming you found that this section of code is what's taking the most time. If you didn't, it does seem like a good place to start.
    Last edited by skorman00; 02-06-2005 at 02:22 PM.

  6. #6
    Registered User OnionKnight's Avatar
    Join Date
    Jan 2005
    Posts
    555
    Didn't the first two elements contain 0 and 1? How could it become 4? Even more confusing, when I tried it out I got:

    short = 0
    long = 65536

    And the code looked like this, in case I did something wrong:
    Code:
    #include <stdio.h>
    
    short mat[3][3] = {{0,1,2},{3,4,5},{4,5,6}};
    short *pShort;
    long  *pLong;
    
    int main()
    {
    	pShort = &mat[0][0];
    	pLong = (long *)&mat[0][0];
    	printf("short = %d \nlong = %d", *pShort, *pLong);
    	return 0;
    }

  7. #7
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by skorman00
    endian system).

    Code:
       
    values      binary (short)        binary (long)
    [0] [1] = [00 00] [01 00] =   [00 00 01 00] = 4
    I agree with your conclusions, but there is an error here.

    Since the array type is short, if we access two (16-bit) shorts by a pointer to short, here's what gets into the registers (values in hex):

    Code:
    [0000] [0001]

    If we access four bytes in memory for a little-endian machine, we see that this is the data:

    Code:
    [00] [00] [01] [00]
    If we access one (32-bit) int by a pointer to int, here's what gets into the register:

    Code:
    [00010000]
    (Decimal value = 65536)

    Regards,

    Dave

  8. #8
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Here's an illustration of how movemement might work with a linked list:
    Code:
    itsme@dreams:~/C$ cat snake.c
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node_s
    {
      int num;
      struct node_s *next;
    } NODE;
    
    // Make a snake consisting of 5 segments
    // We'll call segment 1 the head
    // Make it circular for optomization
    void make_snake(NODE **snake)
    {
      NODE *n, *tail;
      int i;
    
      for(i = 0;i < 5;++i)
      {
        if(!(n = malloc(sizeof(NODE))))
        {
          puts("Memory allocation error");
          exit(1);
        }
    
        n->num = i+1;
    
        n->next = *snake;
        *snake = n;
        if(!i)
          tail = n;
      }
    
      tail->next = *snake;
    }
    
    void show_snake(NODE *snake)
    {
      NODE *start = snake;
    
      do
      {
        printf("%d ", snake->num);
        snake = snake->next;
      }  while(start != snake);
      putchar('\n');
    }
    
    // Make the snake look like it's moving by detaching its tail and
    // reattaching it as the new head
    void move_snake(NODE **snake)
    {
      *snake = (*snake)->next;
    }
    
    void free_snake(NODE *snake)
    {
      NODE *n, *nnext;
    
      for(n = snake;n != snake;n = nnext)
      {
        nnext = n->next;
        free(n);
      }
    }
    
    int main(void)
    {
      NODE *snake = NULL;
    
      make_snake(&snake);
    
      show_snake(snake);
      move_snake(&snake);
      show_snake(snake);
      move_snake(&snake);
      show_snake(snake);
      move_snake(&snake);
      show_snake(snake);
    
      free(snake);
    
      return 0;
    }
    Code:
    itsme@dreams:~/C$ ./snake
    5 4 3 2 1
    4 3 2 1 5
    3 2 1 5 4
    2 1 5 4 3
    So you can see that it's very simple to move the snake along just by simply moving the head pointer around the circular list. You could add more information to each node of the list such as the coords of that body segment. At any rate, the benefit is that you don't need to touch every segment of the snake. You only need to update the head and tail.
    Last edited by itsme86; 02-07-2005 at 01:51 PM.
    If you understand what you're doing, you're not learning anything.

  9. #9
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    Thanks for correcting me there Mr. Evans. The reason why it became 65536 has to do with the way a number is represented in binary/hex, and the fact that the bytes are reversed on little endian processors. These link may help if you're not familiar with either:

    http://www.math.grin.edu/~rebelsky/C...nt-binary.html
    http://people.ee.ethz.ch/~oetiker/we...n_dec_hex.html

    these may answer some questions you have on what endian means:

    http://www.cs.umass.edu/~verts/cs32/endian.html
    http://www.noveltheory.com/techpapers/endian.asp

    I apoligize for any confusion my last post gave you, and thank you again Mr. Evans for pointing out my error.

  10. #10
    Registered User OnionKnight's Avatar
    Join Date
    Jan 2005
    Posts
    555
    I understand, but this stuff is still above my level so I guess I'll have to read some before I do something about that loop.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 11-23-2007, 01:48 PM
  2. A Question About Unit Testing
    By Tonto in forum C++ Programming
    Replies: 2
    Last Post: 12-14-2006, 08:22 PM
  3. porting application from 32 bit to 64 bit error
    By gandalf_bar in forum Linux Programming
    Replies: 1
    Last Post: 09-14-2005, 09:20 AM
  4. Copy bit to bit
    By Coder2Die4 in forum C Programming
    Replies: 15
    Last Post: 06-26-2003, 09:58 AM
  5. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-25-2001, 11:45 PM