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