 |
lua-l archive |
|
|
||
|
On Mar 26, 2014 2:15 PM, "Doug Currie" <doug.currie@gmail.com> wrote:
> On Wed, Mar 26, 2014 at 12:41 PM, Roberto Ierusalimschy <roberto@inf.puc-rio.br> wrote:
>>
>> Just for curiosity, do you remember those techniques?
>
> One application that comes to my mind is extracting a signed M bit field from bit position P in a word of length N:
>
> (x << (N - (P + M))) >> (N - M)
>
> where >> is signed (otherwise the field won't be sign extended), and bit positions are little endian, M <= N, P <= N.
If you want bit-twiddling fun, you want
http://graphics.stanford.edu/~seander/bithacks.html#VariableSignExtend which through the power of xkcd386 has been scrubbed of arithmetic shifts.
Here's the variable sign extension entry:
====
unsigned b; // number of bits representing the number in x
int x; // sign extend this b-bit number to r
int r; // resulting sign-extended number
int const m = 1U << (b - 1); // mask can be pre-computed if b is fixed
x = x & ((1U << b) - 1); // (Skip this if bits in x above position b are already zero.)
r = (x ^ m) - m;
The code above requires four operations, but when the bitwidth is a constant rather than variable, it requires only two fast operations, assuming the upper bits are already zeroes.
A slightly faster but less portable method that doesn't depend on the bits in x above position b being zero is:
int const m = CHAR_BIT * sizeof(x) - b;
r = (x << m) >> m;
====
> This sort of thing comes up in embedded applications, e.g., pulling a ADC value out of a SPI packet, or parsing a binary comm buffer.
All of this starts to look suspiciously like scanf/printf at the bit level.
> This is a case where // 2^(N - M) would be fine... assuming the // and ^ operators are performant enough, which I am skeptical about in embedded processors where integer mode would be used.
I'll take that bet. All the SoCs with 32k of RAM seem to be Cortex M3s and up. 12-cycle 32-bit divider.
Jay