By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
429,067 Members | 1,818 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 429,067 IT Pros & Developers. It's quick & easy.

Memory Optimization: Need to store two 4-bit no. in 6 bits

P: 1
Hi,

In a certain system we are left with only 6 bits, which can store a no. of range 0 to 63.

We want to store two numbers each ranging from 0 to 12, which will take 4 bits each.

Does anyone know of any algorithm that can store these two 4 bit number in optimized way together into 6 bits.

I initially thought of old Birth date trick:
1.Ask your friend to multiply the number of his month of birth by 5.
2.To this add 6.
3.Now,multiply by 4.
4.Add 9.
5.Multiply again by 5 and add to it his date of birth.
6.Ask him/her to subtract 165 from this and tell the answer.

The last two digits of this number will give you the date and the first 1 or 2 digit/s give the month.
May be some combination of XOR/AND/OR operation can compress it into 6 bit.

Any weird working idea is welcome.

Thanks in advance.
Aug 7 '07 #1
Share this Question
Share on Google+
6 Replies


P: 86
It can't be done....see Pidgeon Hole Principle

0-12 yield 13 possible values
and you need to store 2 which gives you 13*13 combinations or 169 unique combination which would need 7 bits.

Compression won't help, because some combinations are not compressible.
Aug 7 '07 #2

weaknessforcats
Expert Mod 5K+
P: 9,197
Use a map:

000000 == 0
000001 == 1
000010 == 2
000011 == 3
000100 == 4
001100 == 12
etc...
010000 == 0 //the other number
010001 == 1
etc...
011100 == 12

It looks like you can map 4 numbers between 0 and 12 into the 6 bits.
Aug 8 '07 #3

P: 86
Use a map:

000000 == 0
000001 == 1
000010 == 2
000011 == 3
000100 == 4
001100 == 12
etc...
010000 == 0 //the other number
010001 == 1
etc...
011100 == 12

It looks like you can map 4 numbers between 0 and 12 into the 6 bits.
Nice try, but uh...No

He needs to store BOTH numbers not one or the other, for instance he might need to store the numbers 11 AND 12.
11 = 001011 and 12 = 001100, so how do i combine them unambiguously, so that when I am ready to extract I get 11 and 12 back?

As I've stated already, you can't.
Aug 10 '07 #4

Expert 10K+
P: 11,448
Nice try, but uh...No

He needs to store BOTH numbers not one or the other, for instance he might need to store the numbers 11 AND 12.
11 = 001011 and 12 = 001100, so how do i combine them unambiguously, so that when I am ready to extract I get 11 and 12 back?

As I've stated already, you can't.
13*13 possibile pigeons in 6 bits == 64 pigeon holes; not much privacy for some
of them according to the Pigeon Hole Principle.

kind regards,

Jos
Aug 10 '07 #5

weaknessforcats
Expert Mod 5K+
P: 9,197
Nice try, but uh...No

He needs to store BOTH numbers not one or the other, for instance he might need to store the numbers 11 AND 12.
11 = 001011 and 12 = 001100, so how do i combine them unambiguously, so that when I am ready to extract I get 11 and 12 back?
Numbers in the range 0-12 need 4 bits. You use the the reamnining 2 bits as map keys:

001100 --> a 12
011100 --> another 12
111100 ---> yet another 12
101100 -- > even one more 12

Just write code that works with these 6 bits. What you really have here is a resgister of 4 numbers.
Aug 10 '07 #6

weaknessforcats
Expert Mod 5K+
P: 9,197
Nice try, but uh...No

He needs to store BOTH numbers not one or the other, for instance he might need to store the numbers 11 AND 12.
11 = 001011 and 12 = 001100, so how do i combine them unambiguously, so that when I am ready to extract I get 11 and 12 back?
My apologies to Darryl. The light just went on. Boy, do I feel sheepish.
Aug 10 '07 #7

Post your reply

Sign in to post your reply or Sign up for a free account.