Difference between revisions of "Interview Preparation Bit Fiddling"
From Embedded Systems Learning Academy
(Created page with "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 y...") |
|||
| Line 6: | Line 6: | ||
uint32_t find_highest_bit_num(uint32_t num) | 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 big 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]; | ||
} | } | ||
| + | </syntaxhighlight> | ||
| − | /* | + | <BR/> |
| − | uint32_t | + | == Invert bit at bit position N == |
| + | <syntaxhighlight lang="C"> | ||
| + | /* Invert a number's bit at a particular bit position */ | ||
| + | uint32_t invert_bit(uint32_t num, uint32_t bit_pos) | ||
{ | { | ||
| + | /* TODO */ | ||
| + | } | ||
| + | </syntaxhighlight> | ||
| + | <BR/> | ||
| + | == Swap Nibbles == | ||
| + | A "nibble" is a 4-bit value | ||
| + | <syntaxhighlight lang="C"> | ||
| + | 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); | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
Revision as of 22:32, 7 July 2013
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 big 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)
{
/* TODO */
}
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);
}
