e338: 放暑假了!!!!!...可惜要上暑輔...開學後還要模考...

2019-09-05

內容

段考後的延平:

https://drive.google.com/file/d/1j4qESZGdI0jQW6uuxcSb7tfNsq_SB_vl/view?usp=sharing

輸入

一行一個非負整數 n(n<2^31)

1
2
3
4

輸出

輸出此整數在二進位中 1 的個數

1
1
2
1

解題思路

算出一個整數的二進制中有幾個 1 位元，直覺反應用用右移(">>")和位元 AND ('&') 配合迴圈檢查每個位元，時間複雜度 O(n)

int popCount(int n)
{
    int res = 0;
    while(n)
    {
        res += n & 1;
        n >>= 1;
    }
    return res;
}

但這樣子還不夠快，所以改用建表 + 查表 O(1) 的方法。

作法很簡單，把每兩位元當作一組那每組就有

00, 01, 10, 11

四種狀態，1 出現的次數分別是

0 1 1 2

而當有兩組時變成

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111,
1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

4 * 4 = 16 種狀態，而 1 出現的次數剛好能將他拆成左邊一組右邊一組，然後左右兩組相加，變成

(0 + 0), (0 + 1), (0 + 1), (0 + 2), (1 + 0), (1 + 1), (1 + 1), (1 + 2),
(1 + 0), (1 + 1), (1 + 1), (1 + 2), (2 + 0), (2 + 1), (2 + 1), (2 + 2)

之後 6 位, 8 位 … 32 位皆可用同理求得，而由於過程是簡單遞迴，所以可以用巨集來建表減少程式的運算消耗 (如下方程式碼)，最後查表輸出，但由於 2³² 太大了，所以表只建到 2¹⁶ 然後用右移(">>")和位元 AND ('&') 來拆成前 16 位和後 16 位再相加求得 1 的總數輸出。

輸入輸出量極大，要做 IO 優化。

–

題外話: 本題出題者應該是想要用時間卡開頭 O(n) 的算法，但本來 O(n) 就沒多慢，所以連帶著用 O(1) 算法但 IO 優化不夠好的人一起被卡掉了，結果就產生了討論區精彩的筆戰，然後不知道是不是因為太精采的關係，每次 Loading 進這題都要讀很久…

完整程式碼

AC (0.2s, 2.1MB)

#pragma GCC optimize(3)
#include <stdio.h>
#define MAX 65535
#define BUFSIZ 1048576
#define BUFMAX 1048560
#define  BIT2(n)       n,         n+1,       n+1,        n+2
#define  BIT4(n)  BIT2(n),  BIT2(n+1),  BIT2(n+1),  BIT2(n+2)
#define  BIT6(n)  BIT4(n),  BIT4(n+1),  BIT4(n+1),  BIT4(n+2)
#define  BIT8(n)  BIT6(n),  BIT6(n+1),  BIT6(n+1),  BIT6(n+2)
#define BIT10(n)  BIT8(n),  BIT8(n+1),  BIT8(n+1),  BIT8(n+2)
#define BIT12(n) BIT10(n), BIT10(n+1), BIT10(n+1), BIT10(n+2)
#define BIT14(n) BIT12(n), BIT12(n+1), BIT12(n+1), BIT12(n+2)
#define BIT16(n) BIT14(n), BIT14(n+1), BIT14(n+1), BIT14(n+2)

const unsigned char TABLE[MAX + 1] = { BIT16(0) };
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(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;
}

char* setUInt(char buffer[], register unsigned int src, const char suffix)
{
    register unsigned int div;
    char tmp[11], * st = tmp + 10, *res = buffer - 1;
    *st = 0;
    do
    {
        *(--st) = src - ((div = src / 10) << 3) - (div << 1) + '0';
    } while (src = div);
    while (*++res = *st++)
        ;
    if (suffix)* res++ = suffix;
    return res;
}

int main()
{
    int n;
    char *end = output + BUFMAX;
    register char* oTop = output;
    while (readUInt(&n))
    {
        oTop = setUInt(oTop, TABLE[n & MAX] + TABLE[(n >> 16) & MAX], '\n');
        if (oTop > end)
        {
            *oTop = 0;
            fputs(output, stdout);
            oTop = output;
        }
    }
    *oTop = 0;
    fputs(output, stdout);
    return 0;
}