Palindrome is a number or string that reads the same forward and backwards (424, "rotor"). A known way to determine if string is a palindrome is to run two pointers from the ends until the values match:

```
public static bool IsPalindrome(char[] input)
{
var i = 0;
var j = input.Length - 1;
while (i < j)
{
if (input[i++] != input[j--]) return false;
}
return true;
}
```

What if we are given a number and we need to determine if bits of this number form palindrome, for example 7(111), 9(1001), 33(100001) are palindromes while 8(1000) is not.

### Convert number to its binary representation

We can convert an integer number, say 9 to the array of characters ['1', '0', '0', '1'] with a handy dandy `Convert.ToString(int value, int toBase)`

overload and then use string palindrome function (above):

```
public static bool IsPalindrome(int input)
{
var charBinaryArray = Convert.ToString(input, 2).ToCharArray();
return IsPalindrome(charBinaryArray);
}
```

This works but has on overhead and thus the other method is

### Bit reversal

Basically reverse number bits and compare them with the original bits. If they match, then it is palindrome. In what I think was an original code this was labeled as reverse bits the obvious way (and also this StackOverflow question). I don't know about obvious, but comparing to other methods, this is the shortest code:

```
public static bool IsBinaryPalindrom(uint n)
{
uint r = 0;
for (uint v = n; v > 0; v >>= 1)
{
r = (r << 1) | (v & 1);
}
return r == n;
}
```

Here's the execution trace for n = 5 (101):

Iteration | v | r << 1 | v & 1 | r = (r << 1) | (v & 1) | |
---|---|---|---|---|---|

0 | 101 | 000 | 001 | 001 | |

1 | 010 | 010 | 000 | 010 | |

2 | 001 | 100 | 001 | 101 |

So basically shift bits right and left simultaneously, but shifting left grab the lowest bit from the right shift and at the end if we get **r == n** then it is palindrome.