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:
Here is the implementation of the pseudocode :
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.
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