## Microsoft Interview Question

Country: -

Comment hidden because of low score. Click to expand.
8
of 10 vote

x & 0xFFFF0000 && (i += 16, x >>= 16),
x & 0xFF00 && (i += 8, x >>= 8),
x & 0xF0 && (i += 4, x >>= 4),
x & 0x0C && (i += 2, x>>= 2),
x & 2 && (i += 1);
?

Comment hidden because of low score. Click to expand.
0

that's good one))

Comment hidden because of low score. Click to expand.
0

Not able to understand the solution. :(

Comment hidden because of low score. Click to expand.
0

Nice one, just one more questn , doesnt the right shift uses a loop internally ?

Comment hidden because of low score. Click to expand.
0

Nice one.. More like binary search...

Comment hidden because of low score. Click to expand.
0

Ingenious :)

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Actually this is a kind of 'manual' loop, but just optimized. Almost the same if you write:

``````x&0x8000000 && (i = 31, x <<= 1),
x&0x8000000 && (i = 30, x <<= 1),
x&0x8000000 && (i = 29, x <<= 1),
...``````

Comment hidden because of low score. Click to expand.
5
of 5 vote

floor(LOGbase2(n))

Comment hidden because of low score. Click to expand.
0

So beautiful solution

Comment hidden because of low score. Click to expand.
-1
of 1 vote

cool! floor(log2(n)) +1

Comment hidden because of low score. Click to expand.
0

LOGbase2() might use loops internally.

Comment hidden because of low score. Click to expand.
0

+1 eugene :D

Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int find_highbit(int number, int k){
int m = 1<<k;
if (k<0){
}
if ((number & m)>0)
return k; //if kth bit is 1
else
return find_highbit(number, k-1); //check next highest bit
}

find_highbit(number, 32);

Comment hidden because of low score. Click to expand.
0
of 0 vote

int find_highbit(int number){
static int k=32;
k--;
if (k<0){
}
cout<<k<<endl;
int check=(number & 1<<k);
int check1=1<<k;
if ((number & 1<<k))
return k; //if kth bit is 1
else
return find_highbit(number); //check next highest bit
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int find_highbit(int number){
static int k=32;
k--;
if (k<0){
}
if ((number & 1<<k))
return k; //if kth bit is 1
else
return find_highbit(number); //check next highest bit
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int k = 3456;
String s = Integer.toBinaryString(k);
System.out.println(k+" : "+s);
int x = k;
x = x >> 1;
int j = 1;
int count = 1;
while(x > 0){
j = j << 1;
x = x >> 1;
count ++;
}
s = Integer.toBinaryString(j);
System.out.println(j+" : "+s+" "+count);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

cout<<((log(x&(x-1)))/log(2))+1;

Comment hidden because of low score. Click to expand.
0
of 0 vote

int FindIndex(unsigned int val)
{
static int count = 0, loop = 0;
if(loop != 32)
{
if((val & 1) == 1)
{
count = (loop + 1);
}
loop++;
FindIndex(val >> 1);
}
else
{
return count;
}
}

int main()
{
unsigned int x = 0x81111111;
printf("%d\n", FindIndex(x));
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

32-clz(x)
Clz is an intrinsic function.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int main()
{
int n=7;
std::cout<<"\n Highest bit set position:"<<floor(log(n)/log(2));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int findMSB(int a){
return (a & 0x80000000) ? 31 : (findMSB((a << 1) | 1) - 1);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````1 #include<stdio.h>
2
3 int find_1st_set_Bit_from_msb(int x,int mask,int count)
4
5 {
6
7
9
10         return count;
11
13
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
38
39     printf("1st msb position set 1 =%d",y);
40
41
42
43 }``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

we are not supposed to use loop. read the questions carefully before giving the approach.
for ex 00000000000001 o(n) n is the number of bits.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

{int in =8;
int t=0;
while(in>=1){
in =in>>1;
t++;
}
t gives value. even this looping is not allowed?

Comment hidden because of low score. Click to expand.
0

Instead of lopp can we use recurcive function?
I guess this will be alternate solution for the same.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

use lookup table. it solves the problem in O(1)

Comment hidden because of low score. Click to expand.
0

Lookup table only needs recording single Byte - 256 cases. For a 4 Byte int, we can get highest bit by just checking each Byte by lookup table.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

int find_set_bits(int n)
{
if(n&1)
return(count+1);
count++;
find_set_bits(n>>1);
}

Comment hidden because of low score. Click to expand.
0

I don't think this will work. Assume that the input is 7 (0111) . During the 1st call to this function the condition in the if statement will turn out to be true -
(0111 & 0001) = 0001 = true
so count will be returned as 1, but it is actually 3.
Let me know in case i am wrong.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.