Show HN: How to store a set of four 5-bit values in one 16-bit value
1–10 of 149 posts
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#2Ah, without preserving order. That's a set of four 5-bit values, not a sequence of four 5-bit values.
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#3This is quite related to the problem of sorting a million 32 bit integers using only 2M of RAM (and no disk). It can be done.
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#4Ah, without preserving order. That's a set of four 5-bit values, not a sequence of four 5-bit values.
[deleted]
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#5That is one big-ass makefile though. I realize it has some extra niceties but I have to ask, did you ever try
make main
If you haven't done so, delete the makefile now (you have it in version control anyway) and give it a try.
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#6Ah, without preserving order. That's a set of four 5-bit values, not a sequence of four 5-bit values.
To answer the obvious next question:
Four 5-bit values in order have 20 bits of entropy, so cannot be stored in 16 bits.
Four 5-bit values without order have 20 - log2(4!) =~ 20 - 4.59 = 15.41 bits of entropy (corresponding to log(2^20/4!) possible configurations), and thus can fit in 16 bits of data if you're clever about it.
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#7Ah, without preserving order. That's a set of four 5-bit values, not a sequence of four 5-bit values.
Hmm, it's interesting to me that order would be expected. I nearly always think of storage and ordering as entirely separate problems.
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#8This is quite related to the problem of sorting a million 32 bit integers using only 2M of RAM (and no disk). It can be done.
Only if all your ints are unique I guess?
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#9That is one big-ass makefile though. I realize it has some extra niceties but I have to ask, did you ever try make main without any makefile at all? If you haven't done so, delete the makefile now (you have it in version control anyway) and give it a try.
GNU Make has a number of implicit rules. A blank target rule (or no target rule) in the Makefile (or no Makefile at all!) will cause `make` to try to create the specified target `foo` from `foo.c` or `foo.cpp` (or others) if they exist. More complete explanation here:
https://www.gnu.org/software/make/manual/html_node/Catalogue...
Note: I was initially annoyed with parent's "do this and see what happens" post and its lack of substantive communication, and responded poorly. This comment is substantially edited.
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#10The fact that it's using lookup tables to store the mapping between the set of numbers and the encoded 16-bit number makes it less interesting; it basically just enumerates the set of all possible combinations of numbers, and uses the ordinal as the encoding. A directly calculated scheme without a lookup would be niftier, though I suspect in practice the way it steals bits from redundancy of duplicates it wouldn't be pretty.