9 bits crammed in to 8 bits space...

[felixnielsen@hotmail.com]

imagine a hollow cube.
every wall can have one of two states: open or closed. This would take
6 bits to represent.
Now, i allso neew to know whitch way i entered the room, this could be
representet with a integer from 0 to 5 = 3 bits.
As 2^6*6-1 = 383 and an 8 bit integer can hold a max value of 255, we
ofcourse have to do some creative thinking, it is however, not as hard
as it sounds, because the wall/door/direction in witch i entered the
room doesnt need a state, so now we are at 2^5*6-1 = 191 and thats a
great deal lower than 255.
However, with this aproach one problem remains.
The walls/doors no longer have a fixes position in the bit field, fx.
if the direction from witch the room was entered is 5 and therefor
wall/door no. 6 will be represented by bit no. 8 (as the 6th wall/door
doesnt need to be represented), if the direction ID is 4, the 5th
wall/door, will not be represented, it doesnt have to be. If the the
direction ID is 3 the 5th wall/door will be representet by the 7th bit,
ect.

This is all a bit confusing and im not quite sure i have explained it
good enough, however i have written a "class" that in my oppinion
should work, but dont(it compiles fine though, but the result is
wrong). maybe that could give some inspiration.

@code start
class Stack {
private:
std::vector<uns igned char> P_Stack;
unsigned char T_Stack;
public:
Stack() {
T_Stack = 0;
}
~Stack() {}
bool Put_Dir(int a) { // should work
T_Stack = (a >= 0 && a < 6) ? a : T_Stack;
}
void Put_Door(int a) { // should work
if (a >= 0 && a < 6) {
if (a >= (T_Stack & 7)) {
a--;
}
T_Stack |= (1 << a);
}
}
unsigned int Get_Dir() { //doesnt work
return (T_Stack & 7);
}
bool Get_Door(int a) { // seems to work, but missing door = 1
implementation is missing.
if (a >= 0 && a < 6) {
if (a >= (T_Stack & 7)) {
a--;
}
return (T_Stack & (1 << a));
}
}
bool Dead_End() { // probably doesnt work
if (T_Stack & (31 << 3)) {
return 1;
}
else {
return 0;
}
}
void Next() { // should work
P_Stack.push_ba ck(T_Stack);
T_Stack = 0;
}
void Pop() { // should work
P_Stack.pop_bac k();
T_Stack = P_Stack.back();
}
};
class Grid {};
int main() {
Stack stack;
stack.Put_Dir(0 );
stack.Put_Door( 1);
stack.Put_Door( 2);
stack.Put_Door( 3);
stack.Put_Door( 4);
stack.Put_Door( 5);
std::cin.get();
// when i ask for direction the result should be 0.
// when i ask for door 0 the result should be 1, but this information
isnt stored in the bitfield.
// when i ask for door 1-5 the result in thiscase should allso be 1,
but only because i have set them, otherwise the should be 0;
}
@code end

Regards
Felix Zacariaz Bloutarski

[fandoras]

Re: 9 bits crammed in to 8 bits space...


felixnielsen@ho tmail.com schrieb:
[color=blue]
> void Put_Door(int a) { // should work
> if (a >= 0 && a < 6) {
> if (a >= (T_Stack & 7)) {
> a--;
> }
> T_Stack |= (1 << a);
> }
> }
> unsigned int Get_Dir() { //doesnt work
> return (T_Stack & 7);
> }[/color]
[color=blue]
> bool Get_Door(int a) { // seems to work, but missing door = 1
> implementation is missing.
> if (a >= 0 && a < 6) {
> if (a >= (T_Stack & 7)) {
> a--;
> }
> return (T_Stack & (1 << a));
> }
> }[/color]


the "<<" ignores the 3 bits used for the "comming from direction"

[Tomás]

Re: 9 bits crammed in to 8 bits space...

posted:
[color=blue]
> imagine a hollow cube.
> every wall can have one of two states: open or closed. This would take
> 6 bits to represent.[/color]

Six sides, each of two possible states, so 6 bits.

I agree.
[color=blue]
> Now, i allso neew to know whitch way i entered the room, this could be
> representet with a integer from 0 to 5 = 3 bits.[/color]

There are six possible combinations for which side you used to enter the
room.

A 3-Bit number has eight possible combinations.

You're wasting the last two of the combinations.

[color=blue]
> As 2^6*6-1 = 383 and an 8 bit integer can hold a max value of 255, we
> ofcourse have to do some creative thinking, it is however, not as hard
> as it sounds, because the wall/door/direction in witch i entered the
> room doesnt need a state, so now we are at 2^5*6-1 = 191 and thats a
> great deal lower than 255.[/color]


Good thinking.

So let's say you entered the room through the side 2:

Bit 0: side 0 = closed
Bit 1: side 1 = open
Bit 2: side 3 = closed //We've omitted side 2
Bit 3: side 4 = open
Bit 4: side 5 = closed

Now we've three further bits to specify by which side we entered the room.
(ie. 0 to 5)


Makes sense.
[color=blue]
> room doesnt need a state
> However, with this aproach one problem remains.
> The walls/doors no longer have a fixes position in the bit field, fx.
> if the direction from witch the room was entered is 5 and therefor
> wall/door no. 6 will be represented by bit no. 8 (as the 6th wall/door
> doesnt need to be represented), if the direction ID is 4, the 5th
> wall/door, will not be represented, it doesnt have to be. If the the
> direction ID is 3 the 5th wall/door will be representet by the 7th bit,
> ect.[/color]

Correct. The order has been disturbed.
[color=blue]
> Maybe that could give some inspiration.[/color]


Here's some code I just wrote. It's just to get you going; it may contain
errors and bugs as I wrote it quickly and sloppily.

class PresenceInRoom
{
private:

char data; //Stores our data

struct SixBools
{
bool side_status[6];
};


bool GetBit(unsigned i)
{
return i && ( 1U << (i - 1) );
}

SixBools GetSixBools()
{
//First we determine which side we came in through

unsigned side_came_in = 0;

if GetBit( 5 ) side_came_in += 4;
if GetBit( 6 ) side_came_in += 2;
if GetBit( 7 ) side_came_in += 1;

//Now we have our side

SixBools six_bools;

six_bools[side_came_in] = false;

{
unsigned bit = 0;

for (unsigned side = 0; side < 6; ++side, ++bit)
{
if (side == side_came_in)
{
--bit;
continue;
}

six_bools[side] = GetBit( bit );
}
}

}
};

-Tomás

[felixnielsen@hotmail.com]

Re: 9 bits crammed in to 8 bits space...


Tomás skrev:
[color=blue]
> posted:
>[color=green]
> > imagine a hollow cube.
> > every wall can have one of two states: open or closed. This would take
> > 6 bits to represent.[/color]
>
> Six sides, each of two possible states, so 6 bits.
>
> I agree.
>[color=green]
> > Now, i allso neew to know whitch way i entered the room, this could be
> > representet with a integer from 0 to 5 = 3 bits.[/color]
>
> There are six possible combinations for which side you used to enter the
> room.
>
> A 3-Bit number has eight possible combinations.
>
> You're wasting the last two of the combinations.
>
>[color=green]
> > As 2^6*6-1 = 383 and an 8 bit integer can hold a max value of 255, we
> > ofcourse have to do some creative thinking, it is however, not as hard
> > as it sounds, because the wall/door/direction in witch i entered the
> > room doesnt need a state, so now we are at 2^5*6-1 = 191 and thats a
> > great deal lower than 255.[/color]
>
>
> Good thinking.
>
> So let's say you entered the room through the side 2:
>
> Bit 0: side 0 = closed
> Bit 1: side 1 = open
> Bit 2: side 3 = closed //We've omitted side 2
> Bit 3: side 4 = open
> Bit 4: side 5 = closed
>
> Now we've three further bits to specify by which side we entered the room.
> (ie. 0 to 5)
>
>
> Makes sense.
>[color=green]
> > room doesnt need a state
> > However, with this aproach one problem remains.
> > The walls/doors no longer have a fixes position in the bit field, fx.
> > if the direction from witch the room was entered is 5 and therefor
> > wall/door no. 6 will be represented by bit no. 8 (as the 6th wall/door
> > doesnt need to be represented), if the direction ID is 4, the 5th
> > wall/door, will not be represented, it doesnt have to be. If the the
> > direction ID is 3 the 5th wall/door will be representet by the 7th bit,
> > ect.[/color]
>
> Correct. The order has been disturbed.
>[color=green]
> > Maybe that could give some inspiration.[/color]
>
>
> Here's some code I just wrote. It's just to get you going; it may contain
> errors and bugs as I wrote it quickly and sloppily.
>
> class PresenceInRoom
> {
> private:
>
> char data; //Stores our data
>
> struct SixBools
> {
> bool side_status[6];
> };
>
>
> bool GetBit(unsigned i)
> {
> return i && ( 1U << (i - 1) );
> }
>
> SixBools GetSixBools()
> {
> //First we determine which side we came in through
>
> unsigned side_came_in = 0;
>
> if GetBit( 5 ) side_came_in += 4;
> if GetBit( 6 ) side_came_in += 2;
> if GetBit( 7 ) side_came_in += 1;
>
> //Now we have our side
>
> SixBools six_bools;
>
> six_bools[side_came_in] = false;
>
> {
> unsigned bit = 0;
>
> for (unsigned side = 0; side < 6; ++side, ++bit)
> {
> if (side == side_came_in)
> {
> --bit;
> continue;
> }
>
> six_bools[side] = GetBit( bit );
> }
> }
>
> }
> };
>
> -Tomás[/color]

looks nice, thank you wery much.
Im sry i havent got time to take a look at it right now,m but im on my
way to a party.
Regard

[felixnielsen@hotmail.com]

Re: 9 bits crammed in to 8 bits space...


Tomás skrev:
[color=blue]
> posted:
>[color=green]
> > imagine a hollow cube.
> > every wall can have one of two states: open or closed. This would take
> > 6 bits to represent.[/color]
>
> Six sides, each of two possible states, so 6 bits.
>
> I agree.
>[color=green]
> > Now, i allso neew to know whitch way i entered the room, this could be
> > representet with a integer from 0 to 5 = 3 bits.[/color]
>
> There are six possible combinations for which side you used to enter the
> room.
>
> A 3-Bit number has eight possible combinations.
>
> You're wasting the last two of the combinations.
>
>[color=green]
> > As 2^6*6-1 = 383 and an 8 bit integer can hold a max value of 255, we
> > ofcourse have to do some creative thinking, it is however, not as hard
> > as it sounds, because the wall/door/direction in witch i entered the
> > room doesnt need a state, so now we are at 2^5*6-1 = 191 and thats a
> > great deal lower than 255.[/color]
>
>
> Good thinking.
>
> So let's say you entered the room through the side 2:
>
> Bit 0: side 0 = closed
> Bit 1: side 1 = open
> Bit 2: side 3 = closed //We've omitted side 2
> Bit 3: side 4 = open
> Bit 4: side 5 = closed
>
> Now we've three further bits to specify by which side we entered the room.
> (ie. 0 to 5)
>
>
> Makes sense.
>[color=green]
> > room doesnt need a state
> > However, with this aproach one problem remains.
> > The walls/doors no longer have a fixes position in the bit field, fx.
> > if the direction from witch the room was entered is 5 and therefor
> > wall/door no. 6 will be represented by bit no. 8 (as the 6th wall/door
> > doesnt need to be represented), if the direction ID is 4, the 5th
> > wall/door, will not be represented, it doesnt have to be. If the the
> > direction ID is 3 the 5th wall/door will be representet by the 7th bit,
> > ect.[/color]
>
> Correct. The order has been disturbed.
>[color=green]
> > Maybe that could give some inspiration.[/color]
>
>
> Here's some code I just wrote. It's just to get you going; it may contain
> errors and bugs as I wrote it quickly and sloppily.
>[/color]
Some bugs indeed needed solving, however, its was nothing seriously.

[color=blue]
> class PresenceInRoom
> {
> private:
>
> char data; //Stores our data
>
> struct SixBools
> {
> bool side_status[6];
> };
>
>
> bool GetBit(unsigned i)
> {
> return i && ( 1U << (i - 1) );
> }
>
> SixBools GetSixBools()
> {
> //First we determine which side we came in through
>
> unsigned side_came_in = 0;
>
> if GetBit( 5 ) side_came_in += 4;
> if GetBit( 6 ) side_came_in += 2;
> if GetBit( 7 ) side_came_in += 1;
>
> //Now we have our side
>
> SixBools six_bools;
>
> six_bools[side_came_in] = false;
>
> {
> unsigned bit = 0;
>
> for (unsigned side = 0; side < 6; ++side, ++bit)
> {
> if (side == side_came_in)
> {
> --bit;
> continue;
> }
>
> six_bools[side] = GetBit( bit );
> }
> }
>
> }
> };[/color]

Still, i dont quite understand how this is suposed to work

Regards
[color=blue]
>
> -Tomás[/color]