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

Swap all odd and even bits

Given an unsigned integer, swap all odd bits with even bits. For example, if the given number is 56 (‭00111000‬), it should be converted to 52 (00110100‬).

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

Bit Flip to convert from integer A to B

This function determines the number of bits you would need to flip to convert from integer A to integer B.
Approach: How to figure out which bits are different in the two given numbers? Simple - XOR!!
Each 1 in XOR represents a bit that is different between A and B. So we simply need to count the number of bits in A^B that are 1.

int bitSwapConversion (int x, int y)
{
	int count = 0;
	for(int z = x^y; z != 0; z = z >> 1)
	{
		count += z & 1;
	}
	return count;
}

To improve upon the code, instead of shifting z repeatedly while checking, we can continuously flip the least significant bit and count how long it takes z to reach 0.

int bitSwapConversion(int x, int y)
{
	int count = 0;
	for (int z = x^y; z != 0; z = z & (z-1))
	{
		count++;
	}
	return count;
}

Interview Question : Bit Insertion between specified positions

Given two 32-bit Numbers, X and Y, and two bit positions a and b, write a function to insert Y into X such that Y starts at bit b and ends at bit a.
For Example,
Input: X = 00100000 (32), Y = 1100 (12), a = 0, b = 4
Output: X = 00101100 (44)
Approach: First, we need to clear the bits from a to b. Then, we can shift Y so that it lines up with bits a through b. Finally, we merge Y and X.

int bitsInsert(int x, int y, int a, int b)
{
	/* Create a mask value to clear bit a through b in x.
	 * Example: a = 0, b = 4. Result should be 11100000.
	 * For simplicity, use just 8 bits for example.
	 */
	int allOnes = ~0;

	//Insert 1s before position b, then all 0s.
	int left = allOnes << (b+1); // left = 11100000

	// Insert 1s after bit position a.
	int right = ((1 << a) - 1); // right =  00000000

	int mask_num = left | right; // mask = 11100000

	int clear_X = x & mask_num; // clear bits a through b
	int shift_Y = y << a; // Move Y into correct position

	return clear_X | shift_Y;
}