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 :(
Contents
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;
}
