429,067 Members | 1,818 Online
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
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

 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

 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

 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