Need help with Bit manipulation programming

This is a discussion on Need help with Bit manipulation programming within the C Programming forums, part of the General Programming Boards category; I hope someone can give me some clues or tips to get started in solving the following problem. I have ...

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    2

    Need help with Bit manipulation programming

    I hope someone can give me some clues or tips to get started in solving the following problem.

    I have an Integer array of size 5. Now I need to copy only the first 20 bits of each integer into a Character array. So finally, the character array has first 20 bits from first integer and immediately followed by first 20 bits from second integer and so on..

    I know this can be done using bit manipulation but I am not getting the right idea. I would really appreciate if someone can give me some clues.

    Thanks.

  2. #2
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    This sounds rather ankward to do. When you say you want to store it in a char array, i guess you mean that you want to store it "somewhere" in memory. Also, i'm curious why you need to do this ?

    If you have 5x20 bits to store, that mean you need 100 bits. 100 / 8 = 12.5, so it means you'll need, in fact, 13 bytes of memory, where the last 4 bits will contain some random stuff. Note that each operation has to move k*8 bits at the same time, where k is an integer > 0, because that's how much of the computer works....

    So... well... i don't have much time left... but from what i see, it's going to be easier to write a purely sequential program for treating 5 integer instead of using some kind of more elaborate structure (like a loop).

  3. #3
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,768
    Indeed. Unfortunately, the instructions can only work with data sizes 1, 2, 4 or 8 bytes. Processor instructions cannot work with other sizes, so what you propose will be cumbersome.
    One thing that "might" work is that you treat one byte as one bit. That way you can allocate as many bytes of memory as you need for the number of bits and set them accordingly.
    But then using that array will be cumbersome.
    Perhaps you should explain a little more on what you're trying to do.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    You put bits into an int in multiples of 20, and take them out in multiples of 8.
    If any bits are left afterwards, you flush out the remainder.
    Like this:
    Code:
    unsigned int bitsHeld=0, bits=0;
    
    pack20BitsOf(int val)
    {
        bitsHeld += 20;
        bits = (bits << 20) | val;
        while (bitsHeld >= 8)
        {
            bitsHeld -= 8;
            writeoutByte(bits >> bitsHeld);
            bits ^= (bits >> bitsHeld) << bitsHeld;
        }
    }
    
    flushBits()
    {
        if (bitsHeld > 0)
        {
            writeoutByte(bits << (8-bitsHeld));
            bits = 0;
            bitsHeld = 0;
        }
    }
    or if you want to pack the bits in the other order (which may be a little bit simpler), then like this:
    Code:
    unsigned int bitsHeld=0, bits=0;
    
    pack20BitsOf(int val)
    {
        bitsHeld += 20;
        bits |= val << bitsHeld;
        while (bitsHeld >= 8)
        {
            bitsHeld -= 8;
            writeoutByte(bits & 0xFF);
            bits >>= 8;
        }
    }
    
    flushBits()
    {
        if (bitsHeld > 0)
        {
            writeoutByte(bits & 0xFF);
            bits = 0;
            bitsHeld = 0;
        }
    }
    Last edited by iMalc; 01-25-2008 at 01:13 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,768
    Why do I see missing return type?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Rats! - Guess whether I tried compiling it or not.
    void should do for the return type. However if writeoutByte were writing to disk and itself could return failure codes, then I'd make the return type mirror that of writeoutByte, with the failure codes being passed back in the same manner.
    It's the algorithm that I was more worried about. Make sure you take the time to understand how it works, as you'll have a better idea how to do such things in future.

    If you would like the corresponding "unpacker" and have trouble implementing this yourself, then let me know. Or if you have trouble using the code I've posted, just ask.
    flushBits is to only be called once, at the end, after all numbers have been processed.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,248
    What are the "first bits?" The lowest 20 bits, or the highest 20 bits?

  8. #8
    Registered User
    Join Date
    Dec 2007
    Posts
    2
    its the lowest 20 bits

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 32 bit to 64 bit Ubuntu
    By Akkernight in forum Tech Board
    Replies: 15
    Last Post: 11-17-2008, 02:14 AM
  2. bit value check efficiency
    By George2 in forum C Programming
    Replies: 5
    Last Post: 11-05-2007, 06:59 AM
  3. Bit processing in C
    By eliomancini in forum C Programming
    Replies: 8
    Last Post: 06-07-2005, 10:54 AM
  4. Porting from 32 bit machine to 64 bit machine!
    By anoopks in forum C Programming
    Replies: 10
    Last Post: 02-25-2005, 07:02 PM
  5. Copy bit to bit
    By Coder2Die4 in forum C Programming
    Replies: 15
    Last Post: 06-26-2003, 09:58 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21