Difference between revisions of "Interview Preparation Bit Fiddling"

/* 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 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
}

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);
}

unsigned int Bits_swap(unsigned int z)
{
    // Get all even bits of z.
    // The number 0xAAAAAAAA is a 32 bit number with all even bits set as 1 and all odd bits as 0.
    unsigned int even_bits = z & 0xAAAAAAAA;

    // Get all odd bits of z
    // The number 0x55555555 is a 32 bit number with all odd bits set as 1 and all even bits as 0.
    unsigned int odd_bits  = z & 0x55555555;

    even_bits >>= 1;  // Right shift even bits
    odd_bits <<= 1;   // Left shift odd bits

    return (even_bits | odd_bits); // Combine even and odd bits
}

// Driver program to test above function
int main()
{
    unsigned int x = 56; // 00111000

    // Output is 52 (00110100)
    printf("%u ", Bits_swap(x));

    return 0;
}