內容
給你兩個整數 a,b
求 a 到 b 之間所有整數(含)進行 and 運算的結果
輸入
每一行兩個非負整數 a,b(a,b<2^64)
12 15
2 3
8 13
17 23
11 15
輸出
答案
12
2
8
16
8
解題思路
很困難也很簡單的一題，重點在「進位」，二進制在進位之後原本的 1 都會變成 0，像是
0111(2) 進位後就會變成 1000(2)，而題目是使用 AND 運算，當某位元出現過 0 之後不管之後出現幾次 1 都不會變回 1，因此當範圍內有任一 8 或其倍數(?????000(2)) 時代表答案的最後 3 位必為 0 ，同理能套用在所有 2 的乘冪或其倍數。(如下表)
| 數 |
二進制 |
| 2 |
??????0 |
| 4 |
?????00 |
| 8 |
????000 |
| 16 |
???0000 |
| 32 |
??00000 |
| 64 |
?000000 |
而既然二的冪次或其倍數一定是最多 0 的，那在 a ~ b 中最大的二的冪次或其倍數就會是答案了，所以接下來的目標就是求出範圍內最大的二的冪次或其倍數，這時候就要用到下式
n = n & (n - 1);
這個式子可以把任一數的最後一位 1 變成 0 ，像是
11000(2) & 10111(2) = 10000(2)
11100(2) & 11011(2) = 11000(2)
11010(2) & 11001(2) = 11000(2)
11001(2) & 11000(2) = 11000(2)
具體原理是因為借位會讓最小位的 1 變成 0，讓比最小位 1 還小的 0 變成 1 ，但 0 和 1 經過 位元 AND 運算後又都會變回 0 ，所以就能達成將最小位的 1 改為 0 的效果。
用這個式子不斷的移除 b 的最小位 1 ，直到 b <= a ，這時候的 b 就會是範圍內最大 2 的冪次的倍數，也就是答案了。
注意本題中輸入的 a 有可能比 b 還大，所以要先判斷兩數大小。
完整程式碼
AC (14ms, 1.1MB)
#include <stdio.h>
#define BUFSIZ 1048576
#define SWAP(x, y) (x)^=((y)^=((x)^=(y)))
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 readULongLong(unsigned long long* 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;
}
inline void putULongLong(register unsigned long long src, const char suffix)
{
register unsigned long long div;
char tmp[22], * st = tmp + 20;
*st = suffix, * (st + 1) = 0;
do
{
*(--st) = src - ((div = src / 10) << 3) - (div << 1) + '0';
} while (src = div);
fputs(st , stdout);
}
int main()
{
unsigned long long f, t;
while (readULongLong(&f), readULongLong(&t))
{
if (t < f) SWAP(t, f);
while (f < t)
t &= (t - 1);
putULongLong(t, '\n');
}
return 0;
}
|
