## 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
of 0 votes

that's good one))

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

Not able to understand the solution. :(

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

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

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

Nice one.. More like binary search...

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

Ingenious :)

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

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
of 0 votes

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
of 0 votes

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
of 0 votes

LOGbase2() might use loops internally.

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

+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){
return 33; //not found
}
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){
return 33; //not found
}
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){
return 33; //not found
}
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
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 }``````

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
of 0 votes

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
of 0 votes

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)
now dont ask me to give detail just google it.

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

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
of 0 votes

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.

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More