2

I'm working with limited memory and need to quickly access a single bit in an array char s[80][10], which effectively gives me an 80x80 array with each index only being a single bit.

This is how I'm currently setting, clearing, and checking individual bits:

s[(row)][(col) >> 3] |= (0x80 >> ((col) & 0x07)); //set bit at s[row][col]
s[(row)][(col) >> 3] &= ~(0x80 >> ((col) & 0x07)); //clear bit at s[row][col]
int bit = (s[row][(col) >> 3] & (0x80 >> ((col) & 0x07)) ? 1 : 0); // read bit at s[row][col] into int bit

Is there some simplification to make these perform faster?

Thanks!

Chrosominop
  • 21
  • 2

2 Answers2

3
s[row][col]  |=  (1 << bit);     // set bit
s[row][col]  &= ~(1 << bit);     // clear bit
(s[row][col] &   (1 << bit))!=0  // read bit

This is the fastest possible as far as C goes. Further optimizations will rely on system-specific things and have to be done by the compiler.

Lundin
  • 195,001
  • 40
  • 254
  • 396
0

As single operations, you can't really do much better. But within a larger algorithm, you could factor-out part of the addressing by using coherency.

That is, with a two dimensional array [M][N], accessing element [i][j] is the same as accessing [i*N+j] of the equivalent 1-dimensional array. That's a multiplication which can be factored out of an inner loop if it changes less often.

luser droog
  • 18,988
  • 3
  • 53
  • 105