Ah, 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.
[deleted]
Show HN: How to store a set of four 5-bit values in one 16-bit value
51–60 of 149 posts
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#52Earlier quoted context omitted.
Usually, when you store a value, you want to be able to get exactly that value back. If you store multiple values without keeping the ordering, you lose that capability. I.e. you can't replace all possible uses of four 5-bit variables with one 16-bit variable, only those where the variables are interchangeable.
Many common data structures fail to preserve order. Maps (aka dictionaries) based on hash tables come to mind. Slightly adrift of the topic... I have a HAMT (hash array map trie) implementation that uses a 32-bit unsigned int as a bitfield to indicate which of the 32 possible children nodes are populated. With this trick I could encode any node with 5 or fewer bits flagged with a 16-bit unsigned int instead. I just c…
I believe, based on the math, that 6 6-bit values barely don't fit in 32 bits. :(
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#53That 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.
Is there a way to make it work with just make? I'm way too used to just typing make at this point and it's not too much work to just copy the same makefile everywhere.
[deleted]
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#54It's pretty cool and all but what are the uses for this? What set of 4 un ordered 5-bit numbers would i need to store that I couldn't just store as 3 bytes? I waste only 4 bits while preserving the order if need be of the values I'm storing. I can think of a very very small few occasions 4 bits would matter over order but nothing realistic. Again It's a cool trick and I'm not trying to be a dick about it. I like cool little tricks like this even if there's no purpose. I'm honestly curious about some realistic use cases for this or some variation of this with larger numbers.
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#55What's the practical use for this?
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#56how are you getting 3876 unique values for a set of 4 4 bit values (16, 16, 16, 16) ?
I don't understand as well...
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#57That 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.
Is there a way to make it work with just make? I'm way too used to just typing make at this point and it's not too much work to just copy the same makefile everywhere.
Use a phony target that does whatever you want. Mine typically invoke cc to build the program ("cc -O3 -Wall -o main main.c", something like that?), then run the program ("./main"), which prints its stuff to stdout and stderr. Makes it very easy to build+run from within Emacs, where the default compile command is "make".
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#58Taking this to the extreme, you could "store" 65535 1-bit values in one 16-bit value. You just have to keep track of how many of them are equal to 1.
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#59Could one practical use of the general case be to store factorial based numbers efficiently ? https://en.wikipedia.org/wiki/Factorial_number_system
Re: Show HN: How to store a set of four 5-bit values in one 16-bit value
#60Earlier quoted context omitted.
Your math is wrong. If two of the numbers happen to be the same, order no longer matters for those numbers, so your log2(4!) needs to be larger...
Right. So the true answer is log2((32*31*30*29)/(4*3*2) + (32*31*30)/2 + (32*31) + (32*31)/2) = 15.675 which is still smaller than 16.
Are you sure you don't mean
log2((32*31*30*29)/(4*3*2*1) + (32*31*30)/(3*2*1) + (32*31)/(2*1) + 32/1) = 15.34
If on the other hand you want to store exactly 4 values, possibly with duplicates (while still ignoring order), you need to count multisets ( https://en.wikipedia.org/wiki/Bag_(mathematics)#Counting_mul... )
log2( (35*34*33*32)/(4*3*2*1) ) = 15.676