Difference between revisions of "Interview Preparation Bit Fiddling"
Proj user16 (talk | contribs) |
Proj user16 (talk | contribs) (→Swap all odd and even bits) |
||
Line 109: | Line 109: | ||
<BR/> | <BR/> | ||
+ | |||
== Bit Flip to convert from integer A to B == | == 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. | This function determines the number of bits you would need to flip to convert from integer A to integer B. |
Revision as of 04:14, 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 :(
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, 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;
}