Expert: Zlatko - 11/28/2011

Question
Hi,
How can i do the following in C:
in order to store the string "abcd", i may need 5 bytes( 40 bits). What i want to do is store each element 'a' or 'b' or ... in its minimal strorage form. eg. if character 'a' is represented as 97 it may take roughly( i didn't do the math) 7 bits. And considering it takes 7 bits for the other chars i need 35 bits to store the string. How can i do this? Any creativity is acceptable. THANK YOU VERY MUCH!

Answer
Hi Heni

It's an interesting question. I may be off by 1 here and there in my analysis below, but I hope you get the basic idea. Basically, you need to be able to get and set the N'th bit of a chunk of memory. That is your basic tool. To build the tool, you will need to understand bit shifting and bitwise logical operators like bitwise AND, which is the single ampersand &.

You decide that your symbol takes B bits. In your case you decided on B = 7. Let's say you want to store S symbols. So you need B*S bits, or B*S/8 + 1 bytes. OK, if B*S is exactly a multiple of 8, then you don't need the extra +1 byte, but lets not worry about that for now.

So the first thing you need to do is get a chunk of memory which is B*S/8+1 bytes long.

Next you need a function, which can return the N'th bit from your chunk of memory.
First you need to determine in which byte of the memory the N'th bit is.
It is in byte N/8
Does that work?
If N is 0 through 7, then we want byte 0 and N/8 is 0.
If N is 8 through 15, then we want byte 1 and N/8 is 1.
BYTE = N/8 seems to work.

Next you need to determine which bit in that byte is the N'th bit of the entire chunk.
That happens to be the remainder of N/8, and in C, the remainder is given with the modulo operator %
BIT = N % 8
Does that work?
If N is 5, then we want bit 5 of byte 0 and 5%8 is 5.
If N is 15, then we want bit 7 of byte 1 and 15%8 is 7.
BIT = N % 8 seems to work.

So now we know the BYTE number and the BIT number within the byte. We can get the byte value with
byteValue = chunk[BYTE];
and we can get the bit value by shifting 1000000 over to the right by the BIT count, ANDing it with the byteVvalue and then shifting the result over to the right (7-BIT) times more.

Are you getting tired? I am.

bitValue = ( (10000000 >> BIT) & byteValue ) >> (7-BIT)

I think that will work, but you would need pencil and paper to prove it to yourself.

Ok, now we have a way of getting the N'th bit from your chunk of memory. The same idea can be used to set the N'th bit, except to set the N'th bit you must do
byteValue = chunk[BYTE]
byteValue = byteValue | (10000000 >> BIT)
chunk[BYTE] = byteValue

Now that you have your function to get and set the N'th bit, you reason as follows.

Your first symbol is at bits 0, 1, 2, ... B-1
Your second symbol is at bits B, B+1, B+2 ... B+B-1
Your third symbol is at bits 2*B, 2*B+1, 2*B+2 ... 2*B+B-1
Your (K)'th symbol is at bits (K-1)*B, (K-1)*B+1, (K-1)*B+2 ... (K-1)*B+B-1

You call your getBit function repeatedly to get all the bits of the symbol you are decoding. Once you have all the bits. You can decode the symbol. Of course you will need more shifting and bitwise operations to build up the symbol from the individual bits you get back from your getBit function.

Do you think you can implement that? Show me your attempt and I'll help you more.

Best regards
Zlatko