## Microsoft Interview Question

Software Engineer / Developers**Country:**-

finally some good solution ))

I think you can do this even simpler:

```
given a number x = 1000111100
lo = x & -x; // locate the lowest set bit: lo = 100
lz = (x + lo) & ~x; // locate the lowest zero above lo: lz = 1000000
x += lo; // flip the 'lz' bit: x = 1001000000
x |= (lz / lo / 2); // add the rest number of ones: x = 1001000111
```

I didn't think about -x trick. That's a good one and make it much more simpler :)

However, last line should be "x |= (lz / lo / 2) - 1" instead. You forgot -1 at the end and it would result in "1001001000" instead of "1001000111"

Then it should be a perfect solution :)

Here's a 7 operations solution:

```
int x = Integer.parseInt("1000111100", 2);
int a = x & -x;
int b = x + a;
int c = b ^ x;
int d = c / (a << 2);
int y = d + b;
System.out.println(Integer.toString(y, 2));
```

Idea is to swap the least significant '1' with the adjust spot if its '0' (from LSB to MSB)

Why:

You are only adding "the least amount" to make the number larger than it is.

Example:

(for 8 bit numbers)

1) 1

0000 0001

swapping 1 with next 0(again, going LSB to MSB), we get

0000 0010 - 2 (answer)

2) 19

0000 1011

--

swap second LSB with third LSB making it

0000 1101 - 21 (answer)

```
int NextLargetsIntWithSameBits(int num)
{
bitset<sizeof(int)*8> bits(num);
bool prev = bits.at(0);
bool cur = true;
for(int i=1; i<bits.size(); i++)
{
cur = bits.at(i);
if(cur==false && prev==true)
{
bits.set(i);
bits.reset(i-1);
break;
}
}
cout<<bits.to_string()<<endl;
return bits.to_ulong();
}
```

What we need actually is the next permutation of the bits.

This should do it:

```
int main () {
int n = 76;
string s = bitset<32>(n).to_string();
next_permutation(s.begin(), s.end());
cout<<bitset<32>(s).to_ulong()<<endl; // prints 81
}
```

<pre lang="" line="1" title="CodeMonkey6775" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));

String s;

while (!(s=r.readLine()).startsWith("42")) System.out.println(s);

}

}

</pre><pre title="CodeMonkey6775" input="yes">

sdf</pre>

// the mission is to find the first lsb set, clear it, and find the second lsb that is 0 and turn it to 1

main()

{

int a = 816;

int p = 0;

int flsb = 0; //first least significant bit set

int slsb = 0; //second least significant bit set

flsb = ((a & (a - 1))^a);

slsb = ~(a | (a - 1));

slsb = ((slsb & (slsb - 1)) ^ slsb);

a &= ~flsb;

a |= slsb;

printf("next int is %i \n",a);

}

Assuming A is input: 1000111100

- Anonymous October 03, 20111000111100: A

1000111011: A-1

1000111111: A|(A-1)

1001000000: (A|A-1))+1 = B (Now we get the first part of our answer by shifting "least significant" '1' bit

0001111100: A^B = C

1110000011: ~C

0001111011: C-1

0000000011: ~C&(C-1)

0000000100: (~C&(C-1))+1 = D

0000000111: (C/D)>>2 = E (This is the second part of our answer)

1001000111: B|E *Answer here