代码

#include <vector>
const int W = 64;
const int cbincnt = 8;
using vbool = std::vector<bool>;
void add_single(vbool& x, size_t w) {
    for (size_t i=x.size(); i-->w; ) {
        x[i] = x[i] | x[i-w];
    }
}
void slice(vbool& dst, vbool& src, size_t offset) {
    for (size_t i=0; i<dst.size(); ++i) {
        size_t k = i+offset;
        dst[i] = k<src.size()?src[k]:0;
    }
}
template<int mode>
void symlogic(vbool& dst, vbool& s0, vbool& s1, vbool& s2) {
    for (size_t i=0; i<dst.size(); ++i) {
        dst[i] = 1 & (mode >> s0[i]+s1[i]+s2[i]);
    }
}
void add(vbool& x, size_t w, size_t n) {
    if (!w || !n) return;
    if (w<W) {
        add_single(x, w);
        --n;
        if (n&1) {
            add_single(x, w);
            --n;
        }
        add(x, w*2, n/2);
        return;
    }
    vbool bincnt[cbincnt];
    for (int i=0; i<cbincnt; ++i) bincnt[i] = vbool(w);
    vbool incr(w), decr(w), b0(w), b1(w), cy(w), cy2(w), ov(w), nzx(w), nz(w);
    std::vector<size_t> extra;
    for (size_t i=0; i<x.size(); i+=w) {
        slice(incr, x, i);
        if (i>=n*w) slice(decr, x, i-n*w);
        symlogic<6> (b0, incr, decr, decr); // xor
        symlogic<1> (b1, incr, incr, decr); // dec 1
        cy.clear();
        nz = nzx;
        for (int j=0; j<cbincnt; ++i) {
            symlogic<12>(cy2, b0, cy, bincnt[j]); // maj
            symlogic<10>(bincnt[j], b0, cy, bincnt[j]); // xor
            symlogic<14>(nz, nz, nz, bincnt[j]); // or
            if (j==0) std::swap(b0, b1);
            std::swap(cy, cy2);
        }
        symlogic<6> (ov, b0, cy, cy); // xor
        for (size_t j=0; j<b1.size(); ++j) {
            if (!ov[j]) continue;
            if (decr[j]) { // dec overflow
                --extra[j];
                bincnt[cbincnt-1][j] = 0;
            } else { // inc overflow
                ++extra[j];
                bincnt[cbincnt-1][j] = 1;
            }
            nzx[j] = extra[j];
        }
        for (size_t j=i; j<i+w && j<x.size(); ++j) {
            x[j] = nzx[j-i];
        }
    }
}

评测结果