Count the number of disjoint 11 blocks

Question

The task is to count the number of disjoint 11 blocks in a 64-bit word, using the minimum number of straight-line instructions. That is, how many nonoverlapping neighbored pairs of 1-bits can be found.

Examples

(imagine leading zeros to fill up to 64 bits)

      Input Output
     111111      3
    1110111      2
11110010111      3

Here is a possible implementation (that would not be a valid answer since it uses a loop and a condition):

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

Scoring

The goal is to minimize the number of instructions. Instructions allowed are only the basic bitwise and arithmetic operators (|, &, ^, +, -, ~, <<, >> (arithmetic shift)) plus popcount (count the number of bits set in a word), clz (count leading zeroes), and ctz (count trailing zeroes). Also, * and / are allowed with a cost of 5 and 25 instructions, respectively. Using 64-bit constants is free. No loops, conditions, function calls etc. are allowed. Example of a three-instruction function that makes it easy to count the number of instructions:

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

but it's also fine to present it in more readable form.

EDIT: now also allowing clz, ctz, *, and /.

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

Try it online!

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

Try it online!

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)
}

Try it online!

Verify through 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);
}

Try it online!