9 bits crammed in to 8 bits space...

Discussion in 'C++' started by felixnielsen, Feb 24, 2006.

  1. felixnielsen

    felixnielsen Guest

    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<unsigned 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_back(T_Stack);
    T_Stack = 0;
    }
    void Pop() { // should work
    P_Stack.pop_back();
    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
     
    felixnielsen, Feb 24, 2006
    #1
    1. Advertisements

  2. felixnielsen

    fandoras Guest


    the "<<" ignores the 3 bits used for the "comming from direction"
     
    fandoras, Feb 24, 2006
    #2
    1. Advertisements

  3. felixnielsen

    Tomás Guest

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

    I agree.
    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.


    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.
    Correct. The order has been disturbed.

    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
     
    Tomás, Feb 24, 2006
    #3
  4. felixnielsen

    felixnielsen Guest

    Tomás skrev:
    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, Feb 24, 2006
    #4
  5. felixnielsen

    felixnielsen Guest

    Tomás skrev:
    Some bugs indeed needed solving, however, its was nothing seriously.

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

    Regards
     
    felixnielsen, Feb 26, 2006
    #5
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.