改善一般迴文判斷，實作高效率演算法
原文題目：
Check whether binary representation of number is palindrome or not
9 = 1001 is palindrome
10 = 1010 not a palindromic
bool isPalindrome(unsigned value)
{
if(!value)
{
return true;
}
unsigned leftBit, rightBit = value & 1;
for (leftBit = 1 << 31; !(leftBit & value); leftBit >>= 1);
while (rightBit < leftBit)
{
if (((leftBit & value) > 0) != ((rightBit & value) > 0))
{
return false;
}
leftBit >>= 1;
rightBit <<= 1;
}
return true;
bool isPalindrome(unsigned value)
{
if (1 & value)
{
unsigned leftBit, rightBit = value & 1;
for (leftBit = 1 << 31; !(leftBit & value); leftBit >>= 1);
while (rightBit < leftBit)
{
if (((leftBit & value) > 0) != ((rightBit & value) > 0))
{
return false;
}
leftBit >>= 1;
rightBit <<= 1;
}
return true;
}
return !value;
}
Internally, integers have a fixed sized binary representation (prefixed with zeros), so simply reversing the bits by a system function won't give you the correct answer. You have to shift out all the low zeros (that used to be high zeros) before you can check for equality.
Another approach to check if a number is a binary palindrome would be to shift-in the least significant bit of the number in question into an auxiliary variable, and then check for equality between that number and the original number. If it fails, shift-out one bit from the original number and check again. repeat the process (shift-in one bit, compare, shift-out one bit, compare), until the auxiliary variable becomes larger than the number. C plus plus:
bool isPalindrome(unsigned value)
{
if(value & 1)
{
for(unsigned lo = 0, hi = value; lo < hi; )
{
if((lo = (lo << 1) + (hi & 1)) == hi || lo == (hi >>= 1))
{
return true;
}
}
return false;
}
return !value;
}
Source Code
#include <iostream>
#include <string>
using namespace std;
#define Bit 32
bool isPalindrome(unsigned value)
{
if(value & 1)
{
for(unsigned lo = 0, hi = value; lo < hi; )
{
if((lo = (lo << 1) + (hi & 1)) == hi || lo == (hi >>= 1))
{
return true;
}
}
return false;
}
return !value;
}
void unsignedToBinaryStr(unsigned value, string &str)
{
str = "";
if(!value)
{
str += '0';
}
else
{
unsigned leftBit;
for(leftBit = 1 << Bit - 1; !(leftBit & value); leftBit >>= 1);
for( ; leftBit; leftBit >>= 1)
{
str += (leftBit & value) ? '1' : '0';
}
}
str += '\0';
}
int main()
{
unsigned i;
string binaryStr;
/**
* this is a easy test (0 ~ 256)
*/
for(i = 0; i <= 256; i++)
{
unsignedToBinaryStr(i, binaryStr);
cout << i << " Binary = " << binaryStr
<< (isPalindrome(i) ?
" is palindrome"
:
" not a palindromic"
) << endl;
}
return 0;
}
0 Binary = 0 is palindrome
1 Binary = 1 is palindrome
2 Binary = 10 not a palindromic
3 Binary = 11 is palindrome
4 Binary = 100 not a palindromic
5 Binary = 101 is palindrome
6 Binary = 110 not a palindromic
7 Binary = 111 is palindrome
8 Binary = 1000 not a palindromic
9 Binary = 1001 is palindrome
10 Binary = 1010 not a palindromic
11 Binary = 1011 not a palindromic
12 Binary = 1100 not a palindromic
13 Binary = 1101 not a palindromic
14 Binary = 1110 not a palindromic
15 Binary = 1111 is palindrome
16 Binary = 10000 not a palindromic
17 Binary = 10001 is palindrome
18 Binary = 10010 not a palindromic
19 Binary = 10011 not a palindromic
20 Binary = 10100 not a palindromic
21 Binary = 10101 is palindrome
22 Binary = 10110 not a palindromic
23 Binary = 10111 not a palindromic
24 Binary = 11000 not a palindromic
25 Binary = 11001 not a palindromic
26 Binary = 11010 not a palindromic
27 Binary = 11011 is palindrome
28 Binary = 11100 not a palindromic
29 Binary = 11101 not a palindromic
30 Binary = 11110 not a palindromic
31 Binary = 11111 is palindrome
32 Binary = 100000 not a palindromic
33 Binary = 100001 is palindrome
34 Binary = 100010 not a palindromic
35 Binary = 100011 not a palindromic
36 Binary = 100100 not a palindromic
37 Binary = 100101 not a palindromic
38 Binary = 100110 not a palindromic
39 Binary = 100111 not a palindromic
40 Binary = 101000 not a palindromic
41 Binary = 101001 not a palindromic
42 Binary = 101010 not a palindromic
43 Binary = 101011 not a palindromic
44 Binary = 101100 not a palindromic
45 Binary = 101101 is palindrome
46 Binary = 101110 not a palindromic
47 Binary = 101111 not a palindromic
48 Binary = 110000 not a palindromic
49 Binary = 110001 not a palindromic
50 Binary = 110010 not a palindromic
51 Binary = 110011 is palindrome
52 Binary = 110100 not a palindromic
53 Binary = 110101 not a palindromic
54 Binary = 110110 not a palindromic
55 Binary = 110111 not a palindromic
56 Binary = 111000 not a palindromic
57 Binary = 111001 not a palindromic
58 Binary = 111010 not a palindromic
59 Binary = 111011 not a palindromic
60 Binary = 111100 not a palindromic
61 Binary = 111101 not a palindromic
62 Binary = 111110 not a palindromic
63 Binary = 111111 is palindrome
64 Binary = 1000000 not a palindromic
65 Binary = 1000001 is palindrome
66 Binary = 1000010 not a palindromic
67 Binary = 1000011 not a palindromic
68 Binary = 1000100 not a palindromic
69 Binary = 1000101 not a palindromic
70 Binary = 1000110 not a palindromic
71 Binary = 1000111 not a palindromic
72 Binary = 1001000 not a palindromic
73 Binary = 1001001 is palindrome
74 Binary = 1001010 not a palindromic
75 Binary = 1001011 not a palindromic
76 Binary = 1001100 not a palindromic
77 Binary = 1001101 not a palindromic
78 Binary = 1001110 not a palindromic
79 Binary = 1001111 not a palindromic
80 Binary = 1010000 not a palindromic
81 Binary = 1010001 not a palindromic
82 Binary = 1010010 not a palindromic
83 Binary = 1010011 not a palindromic
84 Binary = 1010100 not a palindromic
85 Binary = 1010101 is palindrome
86 Binary = 1010110 not a palindromic
87 Binary = 1010111 not a palindromic
88 Binary = 1011000 not a palindromic
89 Binary = 1011001 not a palindromic
90 Binary = 1011010 not a palindromic
91 Binary = 1011011 not a palindromic
92 Binary = 1011100 not a palindromic
93 Binary = 1011101 is palindrome
94 Binary = 1011110 not a palindromic
95 Binary = 1011111 not a palindromic
96 Binary = 1100000 not a palindromic
97 Binary = 1100001 not a palindromic
98 Binary = 1100010 not a palindromic
99 Binary = 1100011 is palindrome
100 Binary = 1100100 not a palindromic
101 Binary = 1100101 not a palindromic
102 Binary = 1100110 not a palindromic
103 Binary = 1100111 not a palindromic
104 Binary = 1101000 not a palindromic
105 Binary = 1101001 not a palindromic
106 Binary = 1101010 not a palindromic
107 Binary = 1101011 is palindrome
108 Binary = 1101100 not a palindromic
109 Binary = 1101101 not a palindromic
110 Binary = 1101110 not a palindromic
111 Binary = 1101111 not a palindromic
112 Binary = 1110000 not a palindromic
113 Binary = 1110001 not a palindromic
114 Binary = 1110010 not a palindromic
115 Binary = 1110011 not a palindromic
116 Binary = 1110100 not a palindromic
117 Binary = 1110101 not a palindromic
118 Binary = 1110110 not a palindromic
119 Binary = 1110111 is palindrome
120 Binary = 1111000 not a palindromic
121 Binary = 1111001 not a palindromic
122 Binary = 1111010 not a palindromic
123 Binary = 1111011 not a palindromic
124 Binary = 1111100 not a palindromic
125 Binary = 1111101 not a palindromic
126 Binary = 1111110 not a palindromic
127 Binary = 1111111 is palindrome
128 Binary = 10000000 not a palindromic
129 Binary = 10000001 is palindrome
130 Binary = 10000010 not a palindromic
131 Binary = 10000011 not a palindromic
132 Binary = 10000100 not a palindromic
133 Binary = 10000101 not a palindromic
134 Binary = 10000110 not a palindromic
135 Binary = 10000111 not a palindromic
136 Binary = 10001000 not a palindromic
137 Binary = 10001001 not a palindromic
138 Binary = 10001010 not a palindromic
139 Binary = 10001011 not a palindromic
140 Binary = 10001100 not a palindromic
141 Binary = 10001101 not a palindromic
142 Binary = 10001110 not a palindromic
143 Binary = 10001111 not a palindromic
144 Binary = 10010000 not a palindromic
145 Binary = 10010001 not a palindromic
146 Binary = 10010010 not a palindromic
147 Binary = 10010011 not a palindromic
148 Binary = 10010100 not a palindromic
149 Binary = 10010101 not a palindromic
150 Binary = 10010110 not a palindromic
151 Binary = 10010111 not a palindromic
152 Binary = 10011000 not a palindromic
153 Binary = 10011001 is palindrome
154 Binary = 10011010 not a palindromic
155 Binary = 10011011 not a palindromic
156 Binary = 10011100 not a palindromic
157 Binary = 10011101 not a palindromic
158 Binary = 10011110 not a palindromic
159 Binary = 10011111 not a palindromic
160 Binary = 10100000 not a palindromic
161 Binary = 10100001 not a palindromic
162 Binary = 10100010 not a palindromic
163 Binary = 10100011 not a palindromic
164 Binary = 10100100 not a palindromic
165 Binary = 10100101 is palindrome
166 Binary = 10100110 not a palindromic
167 Binary = 10100111 not a palindromic
168 Binary = 10101000 not a palindromic
169 Binary = 10101001 not a palindromic
170 Binary = 10101010 not a palindromic
171 Binary = 10101011 not a palindromic
172 Binary = 10101100 not a palindromic
173 Binary = 10101101 not a palindromic
174 Binary = 10101110 not a palindromic
175 Binary = 10101111 not a palindromic
176 Binary = 10110000 not a palindromic
177 Binary = 10110001 not a palindromic
178 Binary = 10110010 not a palindromic
179 Binary = 10110011 not a palindromic
180 Binary = 10110100 not a palindromic
181 Binary = 10110101 not a palindromic
182 Binary = 10110110 not a palindromic
183 Binary = 10110111 not a palindromic
184 Binary = 10111000 not a palindromic
185 Binary = 10111001 not a palindromic
186 Binary = 10111010 not a palindromic
187 Binary = 10111011 not a palindromic
188 Binary = 10111100 not a palindromic
189 Binary = 10111101 is palindrome
190 Binary = 10111110 not a palindromic
191 Binary = 10111111 not a palindromic
192 Binary = 11000000 not a palindromic
193 Binary = 11000001 not a palindromic
194 Binary = 11000010 not a palindromic
195 Binary = 11000011 is palindrome
196 Binary = 11000100 not a palindromic
197 Binary = 11000101 not a palindromic
198 Binary = 11000110 not a palindromic
199 Binary = 11000111 not a palindromic
200 Binary = 11001000 not a palindromic
201 Binary = 11001001 not a palindromic
202 Binary = 11001010 not a palindromic
203 Binary = 11001011 not a palindromic
204 Binary = 11001100 not a palindromic
205 Binary = 11001101 not a palindromic
206 Binary = 11001110 not a palindromic
207 Binary = 11001111 not a palindromic
208 Binary = 11010000 not a palindromic
209 Binary = 11010001 not a palindromic
210 Binary = 11010010 not a palindromic
211 Binary = 11010011 not a palindromic
212 Binary = 11010100 not a palindromic
213 Binary = 11010101 not a palindromic
214 Binary = 11010110 not a palindromic
215 Binary = 11010111 not a palindromic
216 Binary = 11011000 not a palindromic
217 Binary = 11011001 not a palindromic
218 Binary = 11011010 not a palindromic
219 Binary = 11011011 is palindrome
220 Binary = 11011100 not a palindromic
221 Binary = 11011101 not a palindromic
222 Binary = 11011110 not a palindromic
223 Binary = 11011111 not a palindromic
224 Binary = 11100000 not a palindromic
225 Binary = 11100001 not a palindromic
226 Binary = 11100010 not a palindromic
227 Binary = 11100011 not a palindromic
228 Binary = 11100100 not a palindromic
229 Binary = 11100101 not a palindromic
230 Binary = 11100110 not a palindromic
231 Binary = 11100111 is palindrome
232 Binary = 11101000 not a palindromic
233 Binary = 11101001 not a palindromic
234 Binary = 11101010 not a palindromic
235 Binary = 11101011 not a palindromic
236 Binary = 11101100 not a palindromic
237 Binary = 11101101 not a palindromic
238 Binary = 11101110 not a palindromic
239 Binary = 11101111 not a palindromic
240 Binary = 11110000 not a palindromic
241 Binary = 11110001 not a palindromic
242 Binary = 11110010 not a palindromic
243 Binary = 11110011 not a palindromic
244 Binary = 11110100 not a palindromic
245 Binary = 11110101 not a palindromic
246 Binary = 11110110 not a palindromic
247 Binary = 11110111 not a palindromic
248 Binary = 11111000 not a palindromic
249 Binary = 11111001 not a palindromic
250 Binary = 11111010 not a palindromic
251 Binary = 11111011 not a palindromic
252 Binary = 11111100 not a palindromic
253 Binary = 11111101 not a palindromic
254 Binary = 11111110 not a palindromic
255 Binary = 11111111 is palindrome
256 Binary = 100000000 not a palindromic
iThome鐵人賽
看影片追技術