CareerCup

can anyone please explain the question.

what does the question mean? thanks

i think the question is about finding the first 2 bits of an integer which are set.

i think the question is about masking ..
i.e. function that hides first 2 bits of given integer

sol : & with "00111111" i.e. 63
which lets pass other bits of given values except first 2.

I guess the question says to give a number for a supplied number such that it masks the first 2 set bits of the supplied number.

Solution:
Make a copy of the supplied number. Look for the first two set bits in the number and reset them to 0. Now "AND" both numbers.

Note: Both numbers should be unsigned.
Complexity: (complexity of AND operation=O(1)) + (complexity in searching first two set bits which in worst case = O(sizeof(unsigned))).

int a;
for(;!(a&0x0003);a>>=1);
print out a&0x0003;

I understood this question this way:

code a function which returns the mask to the first two non-zero bits

e.g.
function(1110) => 0011
function(111110101011000000000) => 000000000001100000000
function(0001) => 0011

The code I wrote is this:

#include <iostream>
using namespace std;


unsigned int getFirstTwoBitSetMask(unsigned int value)
{
	unsigned int ret = ((value - 1) ^ value) ^ (((value - 1) ^ value) >> 2);
	if(ret == 1)
		return 0x3;
	else
		return ret;
}


int main()
{
	int value = 0x1F5600;

	unsigned int mask = getFirstTwoBitSetMask(value);

	return 0;
}

Explanation:

Let's suppose I have the following number: 10101011000000000000 (0xAB000).
If I subtract 1 from this unsigned number I have all 1s on the first right digits that I don't need in the mask except for the last one on the left

10101011000000000000 - 1
10101010111111111111

Now to eliminate all the part on the left which I honestly don't need in my mask let's make a xor between this value and the original one

10101011000000000000 xor
10101010111111111111
------------------------------------
00000001111111111111 let's call this variable MASK_TEMP

the last two 1 values on the left are my mask, I need to cut all the others away so I shift this number by two

MASK_TEMP >> 2
00000001111111111111 >> 2 = 00000000011111111111 let's call this MASK_TEMP_SHIFTED

and now I can xor MASK_TEMP xor MASK_TEMP_SHIFTED to cut away all the 1s I don't need in my mask

00000001111111111111 xor
00000000011111111111
------------------------------------
00000001100000000000 MASK

The result is exactly the mask I was looking for.

There's a problem when the number inserted has a 1 as its least significant bit, that's why the code checks if the returning value is == 1 and, in that case, returns 0x3 which is 0011 and uses a digit on the left to form the mask.

An O(1) solution if the two set bits are from LHS.

given number n:
int n1 = n&(n-1);
Answer = n1&(n1-1);

I think all have got it wrong. The question is asking for first two non zero digits of an integer not the first two bits. So first divide the number by 100 to get remainder. Get the last two digits and figure out the bits for them and figure out the mask from it and mask the integer with that.