How to save multiple numbers into one byte
allinsight.de
allinsight.de
But this is just really simple bit packing. Is this something many engineers (maybe frontend/JS) don't know about now?
If he was a front-end engineer I wouldn't be so surprised but he has 3 years experience working in telecoms, CompSci with networking module at UMass. Uses Wireshark on a regular basis.
A very odd knowledge gap in this domain. So yes I think many engineers don't know these things.
Maybe civil engineers.
Definitely not IT engineers because, well, it's in the name
packed = fileobj.read(2)
# (missing: check the read for early EOF)
packed, = struct.unpack('<H', packed)
flags = packed >> 12
value = packed & 0xfff
Python's integer type isn't 64 bits. It's however many bits you need it to be. For example, I can compute 2 raised to the 128th power, without use of floating point math (and thus, get an exact answer):
In [13]: 2**128
Out[13]: 340282366920938463463374607431768211456
In [14]: type(2**128)
Out[14]: int
> which is not very fast.
It's fast enough for most things. :-) There's numpy, and always C/C++/Rust if you need more speed.
Packing may be performed automatically, unfortunately in an implementation specific way.
In C, you can also specify the size of your fields within integer types:
struct{ unsigned char lowByte:3, midByte:3, highByteLowBits:2; };
And unfortunately too, the actual layour depends on the implementation.
So in most cases, you still have to implement bit shuffling yourself to produce the exact layout that is needed for external files.
You can, but probably it's even slower than doing regular bit shifting operations (<<, >>, &, |, ^, ~)
In [11]: %timeit hex(b[0] | (b[1] << 8) | (b[2] << 16) | (b[3] << 24))
The slowest run took 6.89 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 715 ns per loop
In [12]: %timeit hex(struct.unpack('<I', b)[0])
The slowest run took 8.77 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 587 ns per loop
The struct module is, I believe, written in C. (Pedantically, the struct module isn't; the C module _struct is hidden/private, but if you open the source for struct.py, you'll see it referenced.)
For instance, the ones who breathe tends to take it for granted, yet there are more than 350 000 people who just discovered breathing for the first time today.
That said, I agree with the sentiment here. I can understand people brother having seen packing before. There are lots of programmers and engineers out there that simply haven't had a need. Especially ones who haven't dealt with binary formats or tight resource constraints.
Mind you, the reference implementation from the blog is really poor in terms of code quality and performance because I was not allowed to open-source what I actually developed for my client, but the ideas still stand. Delta compression can make a huge difference in some cases; because cpu cycles are cheap and bitwise operations are very fast it has the potential to bring serious benefits in some scenarios, ie. lower latency of transmitting (numeric) data over networks.
The code gets more complex and slow, but not really by much.
The word is "ternary", by the way.
A useful intermediate representation would be "binary coded ternary" (BCT?) whereby 121 gets represented as 011001. The code 11 isn't used, just like 1010 through 1111 are not used in binary-coded decimal (BCD).
The 10 bit BCT representation of a five digit ternary number could index into an array of 1024 entries, each yielding its numeric value, that fits into a byte.
Likewise, a reverse table of 243 values can map to a 10 bit BCT.
Conversions between BCT and textual digits are trivial.
The way I have in mind is the same way you'd separate out the digits in a decimal number, except you'd use 3 instead of 10 in the math.
Writing is the harder part. I suppose you could just make 15 such tables, one for each possible value you could write.
from math import *
def number_to_trits(n):
# little-endian encoding
# (i.e. smallest precision trit first)
trits = []
v = n
for i in range(1,9):
v, d = divmod(v, 3**i)
trits.append(d)
return trits
print(number_to_trits(8))
# [2, 2, 0, 0, 0, 0, 0, 0]
def trits_to_number(trits):
n = 0
for i, trit in enumerate(trits):
n += trit*3**i
return n
print(trits_to_number([2,2]))
# 8http://number-none.com/product/Packing%20Integers/index.html
I recently implemented a bitpacker in a game VM that didn't have bitwise operations, and the math-based version worked perfectly.
As many games of Go as 100000 is, it's not so big you couldn't use a regular, untuned database.
The method that the article describes (storing two-dimensional arrays of "empty", "black", and "white" in 2 bits) is also not the best one to use to store Go games. Chopping up games and creating deltas from them, or storing the moves rather than the sheets themselves and recreating those sheets on the fly, are best for data compression.
Bitfields are great, but not for this.
I wrote some very slow code to set/get the Nth bit in an array of bytes.
I was planning on using it for Chess bitboards - https://en.wikipedia.org/wiki/Bitboard, but it could be used for say 8 booleans to the byte.
unsigned char getbit(unsigned char * bits,unsigned long n){
return (bits[n/8] & (unsigned char)pow(2,n%8)) >> n%8; void setbit(unsigned char * bits,unsigned long n, unsigned char val){
bits[n/8] = (bits[n/8] & ~(unsigned char)pow(2,n%8)) | ((unsigned char)pow(2,n%8) * val);
} return (bits[n/8] & (1 << (n%8))) >> n%8;