Thursday, January 5, 2012

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 :
public static boolean isPalindrome(int input){


  if ( input < 0)
   return false;

  int inputCopy = input;
  int resultantNumber = 0;
//reverse the bits in the number
  while (inputCopy > 0)
  {
   resultantNumber <<= 1;

   if ((inputCopy & 1)!=0)
   {
    resultantNumber |=1;
   }

   inputCopy >>= 1;
  }

  if (input == resultantNumber)
   return true;

  return false;

}

In the program, we first check for invalid inputs.
resultantNumber  is the number whose bit representation is the reverse of the input number. inputCopy  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. We first reverse the number and then compare them to be equal.

0 comments:

Post a Comment