Interview Preparation Bit Fiddling

This article prepares you for the bit-fiddling questions. The source code should guide you through by example. If you get confused at any step, you can try the source code yourself using a debugger. Note that none of the code has been tested to compile :(

Find Highest Bit Set

/* Find the highest bit that has been set in a uint32 variable */
uint32_t find_highest_bit_num(uint32_t num)
{
    for(int i = 31; i >= 0; i--) {
        if (num & (1 << i)) {
            return i;
        }
    }
    return 0;
}

/* Well, that is too slow, so find the highest bit faster */
int find_highest_bit_num(uint32_t num)
{
    uint16_t high = (num >> 16);
    uint16_t low  = (num >> 0 );
    if (high) {
        return find_highest_bit_num_16(high);
    } else {
        return find_highest_bit_num_16(low);
    }
}
/* Same idea, except this function finds highest in 16-bit number */
int find_highest_bit_num_16(uint16_t num)
{
    uint8_t high = (num >> 8);
    uint8_t low  = (num >> 0);
    if (high) {
        return find_highest_bit_num_8(high);
    } else {
        return find_highest_bit_num_8(low);
    }
}
/* This is the final step, which ends up in a lookup table.
 * Your interviewer will be looking for "lookup table" answer.
 */
int find_highest_bit_num_8(uint8_t num)
{
    /* Create a lookup table of a number and its highest bit set */
    const int8_t table[256] = { -1, /* No bit set */
                                 0, /* 1 */
                                 1, /* 2 */
                                 1, /* 3 */
                                 2  /* 4 */
                               }
    return table[num];
}

Invert bit at bit position N

/* Invert a number's bit at a particular bit position */
uint32_t invert_bit(uint32_t num, uint32_t bit_pos)
{
    return num xor (1 << bit_pos); // xor is a valid operator
    return (num ^ (1 << bit_pos)); // Same result, ^ is same as XOR
}

Swap Nibbles

A "nibble" is a 4-bit value

uint8_t swap_nibble(uint8_t num)
{
    uint8_t high_nibble = (num >> 4);
    uint8_t low_nibble  = (num & 0x0F);
    return (low_nibble << 4) | (high_nibble);
}