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

[paragb]

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.

[Darryl]

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.

[weaknessforcats]

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.

[Darryl]

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.

[JosAH]

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

[weaknessforcats]

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.

[weaknessforcats]

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.