Algorithm
take two varible i -0 & j=N (number)
keep storing bits of number from lsb in reverse order (e.g. shift i left & do or operation with j&1 (mind shud click this the way to extract right most set bit from number :)
keep shifting j right while j is not equals to 0
Explaintion
The first while loop reverses the rightmost bits of the number, stopping after the leftmost 1-bit. It does this by anding out the low-order bit of the number j and oring it into a new number, i. Then j is shifted right. E.g., the number j = 01101 becomes 01011. If the number j matches the input number, then the input number is a palindrome, and the procedure returns TRUE. If the reversed number is less than the input number, it may be that the input number has trailing zeros. E.g., 0110 has reversal 0011. Since this is less than the input number, we shift it left until it is no longer less, giving 0110. Since this equals the input number, we call the number a palindrome. If you don't want to consider the leading zeros, then you leave out the second while loop and say that the number 0110 is not a palindrome.
#include
bool isPalindrome(int N)
{
int i = 0, j = N;
while(j)
{
i = (i << 1) | (j & 1); j >>= 1;
}
return(i == N);
}
int main()
{
printf( " %d ", isPalindrome(9));
}
TC O(logn) as You Know that n=logk(base 2)
Sc O(1)
Run Here http://ideone.com/ddovS
Most Optimized Way can Be Find Here http://www-graphics.stanford.edu/~seander/bithacks.html#BitReverseTable in O(1) :)
6 comments :
If the original bit string = reverse of bit string it will be a plaindrome.
For reverse
start with 2 bit streams
Assuming 1 byte string
we start with a = 0x8; //1000 0000
and b = 1; // 0000 0001
each time we go in a loop
right shift a and left shift b
a: 1000 0000
0100 0000
0010 0000
.... ...
b: 0000 0001
0000 0010
0000 0100
(note b is really power of 2 and is reverse of a in each iteration)
Here is how we reverse the byte string:
If we OR the input byte string with a and we get 1, then we use b to AND.
byte reverse( byte input) {
byte a 0x8;
byte b 1;
byte output 0;
for (int i =0; i<; i++){
a>>=1;
b<<=1;
output += ( input&a > 0: b : 0;
}
return output;
}
if input == output its a palindrome.
Approach seems to be fine & naive but i think something is wrong in line output += input&a > 0: b : 0;
lest say say we have to check 9=1001
is palindrome of not
son lets say input=00001001 when a came to 5th position from right b goes to , b goes to 4th position as well from left & you are adding output to b (which will become 16=2^4) again u repeat the same & we are ahead of answer .
also we are not getting any benefit in terms of complexity ??
let me know if i missed something ?
while(j)
{
i = (i << 1) | (j & 1); j >>= 1;
}
return(i == N);
}
if (i!=N){
logic to shift "i" left until it is no longer less
}
NOTE: the above logic will fail. Try with isPalindrome(5)
@mytwocentsads hey why it won't work just FYI its working http://ideone.com/DvrzB , still any confusion let us know ?
Will it work for number 6??
@ansul , did u tried it ? bdw its working check it http://ideone.com/PzSCzr
Thanks
Shashank
Post a Comment