I thought I'd share this since it seemed like quite a novel optimization.

Let's say you have a uint32_t bitfield and need to determine whether an arbitrary bit (*not* a constant) in that field is set. The naive way of doing this is just

static uint32_t bitfield = 0xFEDCBA90; uint8_t nthbitset = (uint32_t)(bitfield32 & (1UL << n)) != 0UL;

However, since 8-bit AVRs can only shift one byte by one place at a time, this is quite inefficient. GCC compiles this to a loop of right shifts. Even with -Os, this will take over 200 cycles with n = 31!

So I came up with a solution that operates only on 8-bit integers and requires no loops:

static uint8_t bitfield = { 0x90, 0xBA, 0xDC, 0xFE }; static uint8_t bitmasks[8] = { 1, 2, 4, 8, 16, 32, 64, 128 }; uint8_t nthbitset = bitfield[n >> 3] & bitmasks[n & 0x7];

The bitfield is stored explicitly as 4 bytes. The upper 2 bits of n indicate which byte to test. The "AND with shifted 1" is thus performed on one byte, instead of 4, and the value of (1 << n) is stored in a precomputed table a mere 8 bytes in size.

This runs in constant time and takes only 24 cycles!