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?

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.

Quote:

---

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.

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.

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.

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;
}

---

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

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.

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.

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.