4 ms·

I guess we never do bit shifting in higher level languages at all. E.g. in Python, there is no point to do this, there is only one type of int (64 bit) and it s

by Walkman 10y ago

I guess we never do bit shifting in higher level languages at all. E.g. in Python, there is no point to do this, there is only one type of int (64 bit) and it still creates a new int object, which is not very fast.

seiferteric 10y ago
You certainly can do this in python and often will need to when dealing with binary formats. The struct library is a great help for this. (https://docs.python.org/2/library/struct.html https://docs.python.org/2/library/struct.html)
- Walkman 10y ago
  > This module performs conversions between Python values and C structs represented as Python strings. You can, but probably it's even slower than doing regular bit shifting operations (<<, >>, &, |, ^, ~)
  - deathanatos 10y ago
    Where you can, you should use struct. For example, decoding a 32-bit integer in struct is faster than doing it manually: 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 resulting code is also going to be cleaner, especially if you end up needing to unpack multiple members at once, which is common when parsing a binary file. 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.)
- deathanatos 10y ago
  The struct library is great for decoding binary file formats, but it has no facilities for sub-byte packing such as what the article talks about. But if you have a structure composed of little or big-ending encoded 8-/16-/32-/64-bit signed/unsigned integers in a file (quite common) … struct is amazing.
deathanatos 10y ago
If you're reading a file format that does bit packing, such as what the article is talking about, then as you read over the bytes / members of that file, you're probably going to need to get those out of the resulting bytes/decoded integers with Python's bit-shifting instructions. For example, if I have an unsigned 16-bit LE in a file, where the high four bits are flags, and the low 12 bits a value of some ilk, I can parse that with something like, packed = fileobj.read(2) # (missing: check the read for early EOF) packed, = struct.unpack('<H', packed) flags = packed >> 12 value = packed & 0xfff > there is only one type of int (64 bit) 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 This computation would not fit in a 64 bit integer. (For the non-Python programmers, there is a floating-point type, "float", which in CPython corresponds to an IEEE double.) > 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.
informatimago 10y ago
In Common Lisp, you can directly specify the size of your bytes, using types such as (unsigned-byte 3). 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.

by Walkman 10y ago

seiferteric 10y ago

You certainly can do this in python and often will need to when dealing with binary formats. The struct library is a great help for this. (https://docs.python.org/2/library/struct.html https://docs.python.org/2/library/struct.html)

Walkman 10y ago
> This module performs conversions between Python values and C structs represented as Python strings. You can, but probably it's even slower than doing regular bit shifting operations (<<, >>, &, |, ^, ~)
- deathanatos 10y ago
  Where you can, you should use struct. For example, decoding a 32-bit integer in struct is faster than doing it manually: 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 resulting code is also going to be cleaner, especially if you end up needing to unpack multiple members at once, which is common when parsing a binary file. 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.)
deathanatos 10y ago
The struct library is great for decoding binary file formats, but it has no facilities for sub-byte packing such as what the article talks about. But if you have a structure composed of little or big-ending encoded 8-/16-/32-/64-bit signed/unsigned integers in a file (quite common) … struct is amazing.

deathanatos 10y ago

If you're reading a file format that does bit packing, such as what the article is talking about, then as you read over the bytes / members of that file, you're probably going to need to get those out of the resulting bytes/decoded integers with Python's bit-shifting instructions. For example, if I have an unsigned 16-bit LE in a file, where the high four bits are flags, and the low 12 bits a value of some ilk, I can parse that with something like, packed = fileobj.read(2) # (missing: check the read for early EOF) packed, = struct.unpack('<H', packed) flags = packed >> 12 value = packed & 0xfff > there is only one type of int (64 bit) 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 This computation would not fit in a 64 bit integer. (For the non-Python programmers, there is a floating-point type, "float", which in CPython corresponds to an IEEE double.) > 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.

informatimago 10y ago

In Common Lisp, you can directly specify the size of your bytes, using types such as (unsigned-byte 3). 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.