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

- kakawka October 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

that's good one))

- pavel.em October 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not able to understand the solution. :(

- Srikant Aggarwal December 03, 2011 | Flag
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 ?

- anuja January 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice one.. More like binary search...

- saga February 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ingenious :)

- Anonymous July 25, 2012 | Flag
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

- Mrinal December 18, 2012 | Flag
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),
...

- Aleksey.M May 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
5
of 5 vote

floor(LOGbase2(n))

- Sunny October 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

So beautiful solution

- wave October 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

cool! floor(log2(n)) +1

- DJ October 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

LOGbase2() might use loops internally.

- eugene.yarovoi October 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1 eugene :D

- codez July 04, 2012 | Flag
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;
}

- vathsala September 13, 2014 | Flag Reply
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);

- xbai@smu.edu October 26, 2011 | Flag Reply
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
}

- mayank December 01, 2011 | Flag Reply
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
}

- mayank December 01, 2011 | Flag Reply
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;
}

- code_monkey December 22, 2011 | Flag Reply
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);

- Anonymous December 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Kshitij January 28, 2012 | Flag Reply
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));
}

- Nivas September 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Guest October 03, 2012 | Flag Reply
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));
}

- pras July 22, 2013 | Flag Reply
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);
}

- swapnilsj August 06, 2016 | Flag Reply
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 }

- sandeepkumar211221 August 17, 2017 | Flag Reply
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

- Sri October 18, 2011 | Flag Reply
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.

- kamal October 19, 2011 | Flag
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?

- Anonymous October 18, 2011 | Flag Reply
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.

- Nikhil November 14, 2011 | Flag
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.

- kamal October 19, 2011 | Flag Reply
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.

- Anonymous November 15, 2011 | Flag
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);
}

- cool dude November 02, 2011 | Flag Reply
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.

- codemaniac November 04, 2011 | Flag


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