Check If an Integer's Bit Representation Is a Palindrome

Question: how can you determine if a positive integer is a palindrome. For example, 5 is a palindrome because 5 = 101. Also, 9 is a palindrome because 9 = 1001.

Solution: an integer is palindrome when its bit representation is the same reading from left to right or from right to left. Thus, in order to know if it is a palindrome or not, we just have to check if the number's value is still the same when we read the number's bits backward (right to left). For example, 5 is 101 and when we read its bits from right to left, which is 101, the result is still 5. However, 4 is 100 and when read backward it becomes 001 which is 1, so 4 is not a palindrome.

Pseudocode: here is the pseudocode for the algorithm:

integer nResultNum = 0
integer nInputNumCopy = nInputNum

while nInputNumCopy > 0
  nResultNum = nResult << 1;
  if nInputNumCopy & 1 == 1
    nResultNum = nResultNum | 1;
  nResultNumCopy = nResultNumCopy >> 1;
end while

if nResultNumCopy == nInputNum 
  return true

return false

Here is the implementation of the pseudocode using JavaScript:

function bIsIntPalindrome(nInputNum)
{
   if (nInputNum === 'undefined' || nInputNum === null || nInputNum < 0)
      return false;

   var nInputNumCopy = nInputNum;
   var nResultNum = 0;

   while (nInputNumCopy > 0)
   {
      nResultNum <<= 1;

      if (nInputNumCopy & 1)
      {
         nResultNum |=1;
      }

      nInputNumCopy >>= 1;
   }

   if (nInputNum == nResultNum)
      return true;

   return false;
}

Explanation: the general plan is to generate a number whose bit representation is the reverse of that of the input number. After that, we check to see if the two numbers equal. If they do, the input number is palindrome as explained above:

1. Check for invalid inputs.
2. nResultNum is the number whose bit representation is the reverse of the input number. nInputNumCopy is the copy of the input number. Since we'll destroy the value in the process, we must make copy of it so that we can compare the result to the original input later on.
3. The while loop runs until nInputNumCopy is 0, meaning that we have copied all of its bits. In other words, this loop copies the bits from nInputNumCopy to nResultNum from right to left. At each iteration:
   • First, shift nResultNum's bits to the left by 1
   • Second, check if the current right most bit in nInputNumCopy is 1 by using & operator. If the right most bit is 1, turn the right most bit of nResultNum to 1 using | operator.
   • Third, shift all bits of nInputNumCopy to the right by 1.
4. When finishing copying the bits from right to left, we check for equality between nInputNum (the original input value) and nResultNum (containing the same number of bits but in reverse order). If the two equal, then input number is palindrome, otherwise not.

Example: let's check to see if 5 is a palindrome. At the start of while loop, variables' values are nResultNum = 0 and nInputNumCopy = 5 (101). Entering the while loop:

1. First iteration, nResultNum <<= 1 still equals 0 because 000 << 1 = 0. nInputNumCopy & 1 = 1 because 101 & 001 = 001, so nResultNum |= 1 = 000 | 1 = 001. Then, nInputNumCopy >>= 1 = 2 because 101 >> 1 = 010 which is 2. Because nInputNumCopy > 0, loop continues.
2. Second iteration, nResultNum <<= 1 makes nResultNum = 010 because 001 << 1 = 010. Since nInputNumCopy & 1 = 0 (010 & 001 = 000), nothing added to nResultNum in this iteration. nInputNumCopy >>= 1 = 001 = 1. Since nInputNumCopy is still greater than 0, the loop continues.
3. Third iteration, (nResultNum <<= 1) = (010 << 1) = 100. (nInputNumCopy & 1) = 001 & 001 = 001, so a 1 bit is added to nResultNum such that (nResultNum |= 1) = (100 | 1) = 101. Shift nInputNumCopy to right by 1, making nInputNumCopy = 000. Since nInputNumCopy is now 0, the loop ends.

After the while loop, nResultNum = 101 which is 5. Thus, nResultNum equals nInputNum. The method returns true. 5 is a palindrome. We're done.

I hope the explanation was clear. If you have any question, please feel free to ask by emailing or posting in the comment section. Until next time!