Difference between revisions of "Interview Preparation Bit Fiddling"
Proj user16 (talk | contribs) (→Bit Flip to convert from Integer A to B) |
Proj user16 (talk | contribs) (→Bit Flip to convert from Integer A to B) |
||
| Line 109: | Line 109: | ||
<BR/> | <BR/> | ||
| − | == Bit Flip to convert from | + | == 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. | ||
<br> | <br> | ||
Revision as of 05:25, 11 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;
}
