lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On Mar 26, 2014 2:15 PM, "Doug Currie" <> wrote:

> On Wed, Mar 26, 2014 at 12:41 PM, Roberto Ierusalimschy <> 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 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.