Example: Efficiently Small Positive Whole Numbers make your programs conume less memory.

[qwijibow 0]

The Smallest about of addressable space in a computer is one byte (8 bits)
Even if you are using a boolean (True or False) which only needs one Bit, you must assign a whole byte to that variable.

in most programs this waste is nothing to worry about.

but i recently had to write an artificial intelligence Tic Tac Toe Game.
the basic way AI (artificial intelligence works) is by playing the whole game taking every possible combination of every possible moves (minus duplivcate moves)

for the example of Tic Tac Toe, there is a Grid of 9 spaces, each space contains either a "O" an "X" or a blank space. You only need 2 bits to represent this data. however, because of the minimal address space, you need to declaire one byte for each space, 9 bytes for each board. and there are thousands of possible moves that need to be loaded into memory.

in an exhaustive AI search. there are 9*8X7X6X5X4X3X2 (9!) possible moves... which = 362880 boards * 9 squares... You would NEED 8665920 bytes ! in other words, 8.25 Megabytes !

if it was possible to address individual Bits, then you would only need to use 2 bits of memory per space. no waste. this way you would only need 2 megabytes.

In otherwords, In Tic Tac Toe, you NEED 2 megabytes of memory to do an exhaustive game.
but because the minimal addresssable space is 1 byte (8 bits) you need to decalire over 8 megabytes.

SOOOOOO...........
Its had a HUGE buildup.... here it is.

Here is a Class written in C++ that allows you to Address memory Bit by Bit.
it acts like a normal array with a twist.

You Declaire an array of type csmall and specify the number of bits to each so called small variable. and you declaire the length of the array... and it efficinatly stores it in memory.

for example.....
i need an array to hold days of the week....(0 to 6)
to store this range i need a variable with 3 bits
and i need to store one of there are each day in a year (365)

the class will then create an array of 365 which only occupies 137 bytes of main memory.
using a char variable would need 365, or an integer would need even more !

here is an example of you to use the csmall class

int main() {        // create an array of 14 objects.        // where each object holds 3 bits only.	csmall mySmall(3,14);	        // fill the array with data	for(int n=0; n<14; n++) {  mySmall[n] = n%8;	}	        // print out the array.        // the int() function is used to force the char to be printed as a number instead of a character	for(int n=0; n<14; n++) {  cout << int(mySmall[n]) << endl;	}		return 0;}

and here is the code to this class

// This Code is Published under the GNU General Public License// basically, you can do anything with it, EXCEPT take credit for writing it.// also, any program which uses this code, must also be publiched under the GNU General Public Licence.#include<iostream>using namespace std;const int DEFAULT_BITS = 1;const int    DEFAULT_ARRAY_SIZE=1;class csmall {private:	int myArraySize;	char myBits;	char *memory; 		int oldIndex;	char Temp;		void smallinit(char bits, int arraysize) {  myBits=bits;  myArraySize=arraysize;    // make room for the array.  if ((bits * arraysize) % 8 == 0) { 	 memory = new char[(bits * arraysize) / 8];  }  else { 	 memory = new char[((bits * arraysize) / 8) + 1];  }    oldIndex=-1;  Temp=-1;	}		char power2(char n) {  //function to return 2^n  // whats the point in wasting cpu cycles doing the math when we only need 0<n<9  switch(n) {  case 1: return -128;  case 2: return 64;  case 3: return 32;  case 4: return 16;  case 5: return 8;  case 6: return 4;  case 7: return 2;  case 8: return 1;  default: return 0;  }	}		void char2bool(char n, bool *b, char blen) {  // convert char n into a bit array b.  // use only blen bools in the array.    // so we only need to call power2 once for each x  char p;    if(blen==8) { 	 // converting a whole byte 	 // special case :1st bit is a negative ! dealing with signed chars 	 if(n<0) { n+=128; *(b) = true; } 	 else      { *(b) = false; }  }    // x=(blen==0) a clever way of starting from x=1 if the special case above was executed.  for(int x=(blen==8);x<blen;x++) { 	 p=power2(9-blen+x); 	 if(n>=p) { *(b+x) = true; n-=p; } 	 else         { *(b+x) = false; }  }	}		char bool2char(bool *b, char blen) {  //convert a bool array into a char.  //blen = number of bits to convert.    char result=0;    for(int x=0;x<blen;x++) { 	 if(*(b+x)) { result+=power2(9-blen+x); }  }	  return result;	}		bool valid(int index) {  if(index < 0 || index >= myArraySize) { 	 cout << "csmall: Array out of bounds error. index " << index << endl; 	 return false;  }  return true;	}		bool valid(char value, int index) {    //minimum value is 0;  //maximum value is 2^myBits - 1  char max;    //using power2, special case is 7 bits (power2 returns -128 !)  if (myBits == 7) { max = 127; }  else                    { max = power2(8-myBits) -1; }    return (valid(index) && value <= max);	}		char GetSet(char value,int index, bool get) {  //the get and set functions are similar so ive merged them  // if get==true then were getting (and ignoreing the 'value' variable), if get==false then were putting		  if(!valid(value,index)) { return 0; }    // this returns the number stored at this index.  // first, calculate the REAL bytes address,  int realAddress = ((index * myBits) / 8);    // calculate the place within the bool array that our small variable starts.  char offset=(index * myBits) % 8;    // it is possible that some of the bits from this index overflow  // into the next REAL address space, test for this.  bool overflow = ((offset + myBits) > 8);    // retrieve the byte, and if needed, the overflow byte.  bool realChar[16];  char2bool(*(memory + realAddress), &realChar[0], 8);  if(overflow) { char2bool(*(memory + realAddress + 1), &realChar[8], 8); }  // convert the correct part of the realChar array to a number, and return it.  if(get) {     return bool2char(&realChar[offset], myBits);   }  else    { 	 //this is the only part Put differs from Get.. (a sign of a well thought out code ?) 	  	 // convert value into a bool aray 	 bool bvalue[myBits]; 	 char2bool(value,&bvalue[0],myBits); 	  	 // inject bvalue into the correct part of realChar 	 for (int x=0; x<myBits; x++) { realChar[x + offset] = bvalue[x]; } 	  	 // convert the first 8 bits of realchar into a byte (and the second 8 bits if an overflow occured) 	 // and insert them into the real char array 'memory' 	 *(memory + realAddress) = bool2char(&realChar[0], 8); 	 if (overflow) { *(memory + realAddress + 1) = bool2char(&realChar[8],8); } 	  	 // since we are putting, the return value is ignored, but we need to return somthing. 	 return 1;  }	}		char Get(int n) {  return GetSet(0,n,true);	}		void Set(char v, int n) {  GetSet(v,n,false);	}	public:		csmall()    {smallinit(DEFAULT_BITS, DEFAULT_ARRAY_SIZE); }	csmall(char b, int s) {  if (b>=1 && b<=7 && s>=1) { smallinit(b,s); }  else                                          { smallinit(DEFAULT_BITS, DEFAULT_ARRAY_SIZE); }	}	~csmall() { delete[] memory; }		char &operator [](int n) {	  // the problem with this type of access, is we dont know if its being used to  // read a variable, or write to it.  // so we need to make it return a refernce to a tempory variable,  // and monitor any changes to it that were not carried out internally by this class.    // was a change made to Temp after the last execution of this function ?  // if so, update the array.  if(Temp != Get(oldIndex) && Temp != -1 && Temp !=-1) { Set(Temp,oldIndex); }    // Get the value requested by the parameter of this function  if(Temp!=-1) {Temp = Get(n); }    // Remember the index  oldIndex = n;    // Return a reference to temp.  // it might just be read from, it may be written to.  // if it is wirtten to, make the change on the next call of this function.  return Temp;	}};

im quite prowed of this program, if anyone uses it, please let me know what you think.

[vptr 0]

hi,i havent checked the program because i dont program c++ but i think it works well. So...isn't it easier to do something like this:struct bit_array{ unsigned char bit8:1; unsigned char bit7:1; unsigned char bit6:1; unsigned char bit5:1; unsigned char bit4:1; unsigned char bit3:1; unsigned char bit2:1; unsigned char bit1:1;};struct bit_array array[2];and then you can easely manipulate bits like this:// first byte first bit is onarray[0].bit1=1;// second byte third bit is offarray[1].bit3=0;

[qwijibow 0]

Each of those structures needs to be 1 byte long, if each eliment in the array has a number of bits that does not devide exactly into 8, then bits will be wasted.plus my code allows the user to treat these so called small variables as number variables, not bit arrays.Arrays of small numbers seems easyer and cleaner than an array of arrays of bits.in other words.. no i dont think so.