|
Gven an integer n, write code to calculate n+1
Microsoft Interview Questions and Answers
(Continued from previous question...)
70. Gven an integer n, write code to calculate n+1
Question:
Given an integer n, write code to calculate n+1, without using +,-,++,--,*,/
maybe an answer:
int inc(int n)
{
int i=1;
while(n&&i)
{
n &= ~i;
i <<= 1;
}
return (n|i);
}
maybe an answer2:
The main thing to look out for is when you have a number such as 0x0011 where adding one will carry to the next bit.
MaskA does addition using & for each bit position. For each operation if there is a carry, the result will be greater than one.
Example:
0x0011 & 0x0001 = 0x0001
0x0011 & 0x0010 = 0x0010
(and so on). As long as the result is not zero then we will have a carry bit.
MaskB is used to keep track of these carry bits, every time the result of the above operation is greater than one, we shift as follows.
0x0001->0x0011->0x0111 etc.
Once we break out of the loop we xor the original value with MaskB to get the final result. Example, 0x0011 ^ 0x0111 = 0x0100, which is what we want.
The code works for negatives!! woot!
public void bitAdd(int val){
int maskB = 0xFFFFFFFF - 1;
int maskA = 0x0001;
while(maskA>=1){
if((maskA & val) == 0){
break;
} else {
maskA = maskA << 1;
maskB = maskB << 1;
}
}
System.out.println("Adding one:" + (val ^ ~(maskB)));
(Continued on next question...)
Other Interview Questions
| 