Difference between revisions of "Interview Preparation Bit Fiddling"

From Embedded Systems Learning Academy
Jump to: navigation, search
(Find Highest Bit Set)
(Interview Question : Bit Insertion between specified positions)
 
(9 intermediate revisions by 2 users not shown)
Line 59: Line 59:
 
uint32_t invert_bit(uint32_t num, uint32_t bit_pos)
 
uint32_t invert_bit(uint32_t num, uint32_t bit_pos)
 
{
 
{
     /* TODO */
+
     return num xor (1 << bit_pos); // xor is a valid operator
 +
    return (num ^ (1 << bit_pos)); // Same result, ^ is same as XOR
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
Line 74: Line 75:
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
 +
<BR/>
 +
== 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‬).
 +
<syntaxhighlight lang="C">
 +
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;
 +
}
 +
</syntaxhighlight>
 +
 +
<BR/>
 +
 +
== 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.
 +
<br>
 +
'''''Approach:''''' How to figure out which bits are different in the two given numbers? Simple - XOR!!
 +
<br>
 +
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. 
 +
<syntaxhighlight lang="C">
 +
int bitSwapConversion (int x, int y)
 +
{
 +
int count = 0;
 +
for(int z = x^y; z != 0; z = z >> 1)
 +
{
 +
count += z & 1;
 +
}
 +
return count;
 +
}
 +
</syntaxhighlight>
 +
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.
 +
<syntaxhighlight lang="C">
 +
int bitSwapConversion(int x, int y)
 +
{
 +
int count = 0;
 +
for (int z = x^y; z != 0; z = z & (z-1))
 +
{
 +
count++;
 +
}
 +
return count;
 +
}
 +
</syntaxhighlight>
 +
 +
<BR/>
 +
== 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'''''.
 +
<br>
 +
For Example,
 +
<br>
 +
Input:  X = 00100000 (32), Y = 1100 (12), a = 0, b = 4
 +
<br>
 +
Output:  X = 00101100 (44)
 +
<br>
 +
'''''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'''''.
 +
<syntaxhighlight lang="C">
 +
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, I 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;
 +
}
 +
</syntaxhighlight>
 +
<BR/>
 +
 +
== Interview Question : Next largest integer ==
 +
'''''Task:''''' Given a positive integer, we have to print the next largest integer with the same number of 1 bits in their binary representation.
 +
<br>
 +
'''''Approach:'''''
 +
<br>
 +
Example : Let the input number be 13948 with binary representation 11011001111100
 +
<br>
 +
Step 1: Flip rightmost non trailing zero. Call this position '''''p'''''. This would increase the size of integer '''''x''''' but we have one too many one and ones too few zeros. Binary representation now becomes 11011011111100
 +
<br>
 +
Step 2: Let '''''c1''''' be the number of ones to the right of '''''p''''' and '''''c0''''' be the number of zeroes to the right of '''''p'''''. For this example, '''''c0 = 2''''' and '''''c1 = 5'''''. Clear bits to the right of '''''p'''''. Binary representation now becomes 11011010000000.
 +
<br>
 +
Step 3: Add in '''''c1-1''''' ones to the right. Binary representation now - 11011010001111. This is our required number - 13967
 +
<br>
 +
<syntaxhighlight lang="c">
 +
int nextGreater(int x)
 +
{
 +
// Compute c0 and c1
 +
int c = x;
 +
int c0 = 0;
 +
int c1 = 0;
 +
 +
while (((c & 1) == 0) && (c != 0))
 +
{
 +
c0++;
 +
c >>= 1;
 +
}
 +
 +
while (((c  & 1) == 1))
 +
{
 +
c1++;
 +
c >>= 1;
 +
}
 +
 +
//Error if x = 11..1100...00, because there is no bigger number with
 +
//same number of 1s.
 +
if (c0 + c1 == 31 || c0 + c1 == 0)
 +
{
 +
return -1;
 +
}
 +
 +
int p = c0 + c1; // Rightmost non trailing 0.
 +
 +
x |= (1 << p); // Flip rightmost non trailing 0.
 +
x &= ~((1 << p) - 1); // Clear all bits to the right of p
 +
x |= (1 << (c1 - 1)) -1; // Insert c1-1 ones on the right and we are done
 +
return x;
 +
}
 +
</syntaxhighlight>
 +
 +
<BR/>

Latest revision as of 07:38, 13 December 2016

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


Interview Question : Next largest integer

Task: Given a positive integer, we have to print the next largest integer with the same number of 1 bits in their binary representation.
Approach:
Example : Let the input number be 13948 with binary representation 11011001111100
Step 1: Flip rightmost non trailing zero. Call this position p. This would increase the size of integer x but we have one too many one and ones too few zeros. Binary representation now becomes 11011011111100
Step 2: Let c1 be the number of ones to the right of p and c0 be the number of zeroes to the right of p. For this example, c0 = 2 and c1 = 5. Clear bits to the right of p. Binary representation now becomes 11011010000000.
Step 3: Add in c1-1 ones to the right. Binary representation now - 11011010001111. This is our required number - 13967

int nextGreater(int x)
{
	// Compute c0 and c1
	int c = x;
	int c0 = 0;
	int c1 = 0;
	
	while (((c & 1) == 0) && (c != 0))
	{
		c0++;
		c >>= 1;
	}
	
	while (((c  & 1) == 1))
	{
		c1++;
		c >>= 1;
	}
	
	//Error if x = 11..1100...00, because there is no bigger number with 
	//same number of 1s.
	if (c0 + c1 == 31 || c0 + c1 == 0)
	{
		return -1;
	}
	
	int p = c0 + c1; // Rightmost non trailing 0.

	x |= (1 << p); // Flip rightmost non trailing 0.
	x &= ~((1 << p) - 1); // Clear all bits to the right of p
	x |= (1 << (c1 - 1)) -1; // Insert c1-1 ones on the right and we are done
	return x;
}