Microsoft Interview Question
Country: -
Very good solution, though it very clear that how it works, but just for sake of clarification and verification, following is my understanding:
- 1. Bitwise AND operation of a 32 bit number with a number having only last 16 bits (16 - 31) as 1, now if the result is anything > 0, then add 16 to the counter to find the greatest index.
- 2. Reduce the 32 bit number to 16 bit by 16 times right shift, so even if the 31st index was 1, then that becomes 15th index for a 16 bit number
- 3. Bitwise AND operation with 16 bit number with only last 8 bits as 1 (8-15) and repeat the above mentioned process in same proportion i.e for a value > 0 add 8 to the counter and right shift by 8 times, leading to a 8 bit number
- 4. Final value is determined by the value of the counter, that is the value of highest index for 1 in a 32 bit number
int top_bit(unsigned int bits)
{
int i;
if (bits == 0)
return -1;
i = 0;
if (bits & 0xFFFF0000) {
bits &= 0xFFFF0000;
i += 16;
}
if (bits & 0xFF00FF00) {
bits &= 0xFF00FF00;
i += 8;
}
if (bits & 0xF0F0F0F0) {
bits &= 0xF0F0F0F0;
i += 4;
}
if (bits & 0xCCCCCCCC) {
bits &= 0xCCCCCCCC;
i += 2;
}
if (bits & 0xAAAAAAAA) {
bits &= 0xAAAAAAAA;
i += 1;
}
return i;
}
Take a checker variable and set it to 10000...0 (only the last bit set).
On each recursive call, keep ANDing it with our number and if it's a 0 we recursive call the function with the number shifted right once (x<<1).
The static count will keep counting.
Finally subtract the count from 32 and display the number.
Guess it should work. Comments and criticism welcome.
void FindHighestBitSet(int x)
{
static int count = 0, checker = 0x80000000;
if(x==0){ cout<<"0"; }
if(!(x&checker))
{
count ++;
FindHighestBitSet(x<<1);
}
else { cout<<32-count; }
}
int main()
{
FindHighestBitSet(685);
return 1;
}
1 #include<stdio.h>
2
3 int find_1st_set_Bit_from_msb(int x,int mask,int count)
4
5 {
6
7
8 if( x & mask)
9
10 return count;
11
12 mask = mask >> 1;
13
14 find_1st_set_Bit_from_msb(x,mask,--count);
15
16
17 }
18
19 int main()
20
21 {
22
23 int count = sizeof(int)*8;
24
25 unsigned int size = sizeof(int)*8;
26
27 unsigned int mask = 1<<(size-1);
28
29
30
31 int x;
32
33 printf("Enter the Number :");
34
35 scanf("%d",&x);
36
37 int y=find_1st_set_Bit_from_msb(x,mask,count);
38
39 printf("1st msb position set 1 =%d",y);
40
41
42
43 }
Just traverse from the left hand side of the number and searching for the first element other than zero. This would fetch the result I suppose . Correct me if I am wrong
{int in =8;
int t=0;
while(in>=1){
in =in>>1;
t++;
}
t gives value. even this looping is not allowed?
use lookup table. it solves the problem in O(1)
now dont ask me to give detail just google it.
x & 0xFFFF0000 && (i += 16, x >>= 16),
- kakawka October 19, 2011x & 0xFF00 && (i += 8, x >>= 8),
x & 0xF0 && (i += 4, x >>= 4),
x & 0x0C && (i += 2, x>>= 2),
x & 2 && (i += 1);
?