## 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);

?