2016-09-28 @sunderls

https://leetcode.com/problems/reverse-integer/

Reverse digits of an integer.

Example1: x = 123, return 321

Example2: x = -123, return -321

for 123, we can get the least significant digit every time, and accumulate the result, by following

- 123 -> 12, result -> 3
- 12 -> 1, result-> 3 * 10 + 2
- 1 -> 0, result -> 32 * 10 + 1 = 321

about the sign, we keep a flag at first.

```
var reverse = function(x) {
var result = 0;
var rest = x;
var flag = 1;
if (x < 0){
flag = -1;
x = -1 * x;
}
while(x > 0){
rest = x % 10;
result = result * 10 + rest;
x = Math.floor(x / 10);
}
return flag * result;
};
```

While this is almost right, but it turned out that if we reverse an integer it may overflow. we have to add some boundary check.

```
var reverse = function(x) {
var result = 0;
var rest = x;
var flag = 1;
var MAX_INT = Math.pow(2,32 - 1) - 1;
var MIN_INT = - Math.pow(2,32 - 1);
if (x < 0){
flag = -1;
x = -1 * x;
}
while(x > 0){
rest = x % 10;
result = result * 10 + rest;
x = Math.floor(x / 10);
}
result = flag * result;
if (result > MAX_INT || result < MIN_INT){
return 0;
} else {
return result;
}
};
```

This passed, but too slow, ranking at the last 12%, 179ms.

There is no editorial solution on leetcode, but I found an article here: http://www.programcreek.com/2012/12/leetcode-reverse-integer/. Which told me that I didn't need to handle the sign problem, since `-11 % 10 === -1`

, thus came the following improvements:

firstly, we change the last if conditions to ternary operator: 122ms, 86% then, we remove the sign handling, which has much cleaner code.

```
var reverse = function(x) {
var result = 0;
var MAX_INT = Math.pow(2,32 - 1) - 1;
var MIN_INT = -Math.pow(2,32 - 1);
while(x !== 0){
result = result * 10 + x % 10;
x = (x / 10) | 0;
}
return (result > MAX_INT || result < MIN_INT) ? 0 : result;
};
```

There is no integer in javascript, so to truncate the decimal part, we can use bitwise or `| 0`

. how does this work? sorry to forgot almost all of college study.

According online(http://stackoverflow.com/questions/7487977/using-bitwise-or-0-to-floor-a-number), all bitwise operators work on 32-bit integers, and ecma spec says that binary operators will call ToInt32 to convert values to signed 32-bit integers http://ecma262-5.com/ELS5_HTML.htm#Section_11.10. So it works.

Besides `| 0`

, we can also use `Math.trunc()`

what is the largest and smallest 32-bit integer? I didn't get right answer until searching for the detail explanation, here I'll leave some of my understandings.

- as we know, computers store data in bits, take a 3-bit as an example:
`000`

must be 0, no doubt,`001`

=> 1,`011`

=> 3, this have no problem. what about a negative number? a positive number, if added to its negative counterpart, will result in 0, so for 3 (`011`

), -3 should be (`101`

), in fact the result is`1000`

, overflowed. So the negative number is got by reversing the bits & plus 1- for a negative number, the highest bit must be 1, because it have to give a carry to
`1000`

when added to positive counterpart, respectively, positive numbers start with 0 - so the max positive number is
`011`

=> 3, -3 is`101`

, -2 is`110`

, -1 is`111`

. here is natural thought`100`

is -4. - so the range should be [-2^(n-1), 2^(n-1) -1], since 0 has no sign, signed numbers & unsigned numbers have the same account.

如果觉得有帮助到你的话，

欢迎支付宝donate