计算不相交的11个区块的数目。

Question

任务是使用最小的直线指令来计数64位字中不相交的11块的数量。也就是说，可以找到多少个不重叠的1位相邻对。

示例

(想象一下引导零最多填充64位)

      Input Output
     111111      3
    1110111      2
11110010111      3

下面是一个可能的实现(这不是一个有效的答案，因为它使用一个循环和一个条件)：

uint64_t f(uint64_t x) {
    uint64_t n = 0;
    while (x)
        if ((x & 3) == 3)
            ++n, x >>= 2;
        else
            x >>= 1;
    return n;
}

评分

目标是尽量减少指令的数量。允许的指令仅为基本的按位运算符和算术运算符(|、&、^、+、-、~、<<、>> (算术移位))加上popcount (计算一个字中设置的位数)、clz (计数前导零)和d17(计数尾随零)。此外，允许*和/的成本分别为5和25指令。使用64位常量是免费的。不允许循环、条件、函数调用等。一个三指令函数的例子，它使计算指令的数量变得很容易：

uint64_t f(uint64_t x) {
    uint64_t t0 = x ^ 0xff00ff00ff00ff00;
    uint64_t t1 = t0 - 1;
    uint64_t t2 = popcount(t1);
    return t2;
}

但也可以用更易读的形式呈现出来。

编辑：现在还允许clz、ctz、*和/。

Answer 1

5 ops

E = int('01'*32, 2)  # ...01010101

def f(n):
 r = (n ^ E) + E    # 2 ops
 t = n & (E ^ r)    # 2 ops
 return popcount(t) # 1 op

在网上试试！

6 ops

E = int('01'*32, 2)  # ...01010101
O = int('10'*32, 2)  # ...10101010

def f(n):
 r = (n << 1) | E       # 2 ops
 t = n & (O ^ (r - n))  # 3 ops
 return popcount(t)     # 1 op

在网上试试！

Answer 2

11 ops

uint64_t f(uint64_t x) {                      // 11111011110
    uint64_t notx = ~x; // odd ^ even         // 00000100001
    uint64_t bit = notx & (x>>1);             // 00000100001
    uint64_t odd = bit & 0x5555555555555555;  // 00000000001
    uint64_t even = ~bit | 0x5555555555555555;// 11111011111
    uint64_t cov1 = notx; // odd ^ even       // 00000100001
    uint64_t cov2 = odd + even;               // 11111100000
    uint64_t cov = cov1 ^ cov2;               // 11111000001
    uint64_t mask = cov ^ 0x5555555555555555; // 01010010100
    uint64_t res = mask & x;                  // 01010010100
    return __builtin_popcountll(res);         // (4)
}

在网上试试！

通过0.65535进行验证

Answer 3

28 ops

uint64_t f(uint64_t x) {
    uint64_t a = x & (x >> 1);
    uint64_t b = a & (~a >> 1 | a >> 2);
    uint64_t c = b & (~b >> 1 | b >> 4);
    uint64_t d = c & (~c >> 1 | c >> 8);
    uint64_t e = d & (~d >> 1 | d >> 16);
    uint64_t f = e & (~e >> 1 | e >> 32);
    return popcount(f);
}

在网上试试！