內容
暑假水題大放送!!!來解個水題消暑吧!!!
請判斷一個數是否為 2 的乘冪!
輸入
一個整數(int 可以存的下)
1
2
3
4
輸出
如果是,輸出”Yes”,如果不是,輸出”No”
Yes
Yes
No
Yes
解題思路
由於二進制進位的關係， 2n-1 的數 (如下)
20 - 1 = 0 = 0000
21 - 1 = 1 = 0001
22 - 1 = 3 = 0011
23 - 1 = 7 = 0111
因為 2n-1 中 1 的位元必會從最小位元連續出現，所以加上 1 進位後，原本的 1 都會因為進位變成 0 (如下)
20 = 1 = 0001
21 = 2 = 0010
22 = 4 = 0100
23 = 8 = 1000
這時候發現 2n 和 2n-1 中位元 1 必定不會重疊，所以當輸入為 2n和 2n-1 利用位元 AND ('&')做運算時得到的結果必為 0。
而由於不是 2n-1 的數中位元 1 不可能同時滿足從最小位元開始連續出現且完全沒有斷開兩個條件，所以上面的特殊情況只會出現在 2n 和 2n-1 做位元 AND 時。
已經能確定是 2n 專有的情況了，就能用 n & (n - 1) 來判斷，如果為 0 輸出 "YES"，反之輸出 "NO"。
本題輸入輸出量極大，一定要做 IO 優化，輸入中包含特例 0，這時候應該輸出 "YES"。
完整程式碼
AC (73ms, 2.1MB)
#include <stdio.h>
#define BUFSIZ 1048576
#define BUFMAX 1048570
char output[BUFSIZ];
inline char readChar()
{
static char buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;
if (now == end)
{
if (end < buffer + BUFSIZ)
return EOF;
end = (buffer + fread(buffer, 1, BUFSIZ, stdin));
now = buffer;
}
return *now++;
}
inline char readUInt(register unsigned int* dst)
{
register char ch;
while ((ch = readChar()) < '0')
if (ch == EOF) return 0;
*dst = ch ^ '0';
while ((ch = readChar()) >= '0')
* dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
return 1;
}
int main()
{
unsigned int n;
register char* oTop = output;
char* end = output + BUFMAX;
while (readUInt(&n))
{
if (n & (n - 1) | !n)
* oTop++ = 'N', * oTop++ = 'o', * oTop++ = '\n';
else
*oTop++ = 'Y', * oTop++ = 'e', * oTop++ = 's', * oTop++ = '\n';
if (oTop > end)
{
*oTop = '\0';
puts(output);
oTop = output;
}
}
*oTop = '\0';
puts(output);
return 0;
}
|
在開頭再加上命令編譯時對程式進行優化的指令
AC (69ms, 2.1MB)
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
|
