# Count the number of disjoint 11 blocks

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 /.

• Welcome to Code Golf! Feb 9 at 22:38
• Close voters: Can you explain what's unclear? I don't see anything here that's ambiguous. The instruction set is clearly defined, as well as how it relates to the winning criterion. The task itself is defined clearly and objectively and there are test cases. Feb 9 at 23:09
• The requirement for bitwise operators only seems overly restrictive. Might pay to loosen up the rules, but give bonus credit for solutions that use the strict ruleset. Feb 9 at 23:31
• div and mul are not mentioned. Are they allowed? What about ffs() and friends? Feb 9 at 23:57
• The motivation for this is from memory-efficient data structures, where we want to solve this without data-dependent jumps. The instructions are the ones I thought make sense to keep the scoring simple, but I'll add the suggested ones (with a higher cost for the "slow" div and mul. Feb 10 at 12:50

# 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!

# 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

• ~x appeared twice and only counted once because it looks better
– l4m2
Feb 10 at 6:53
• Why does it look better with ~x twice instead of just creating a variable like _x for it? 🤷 Nice answer btw! EDIT: Ah, you probably meant it looks nicer as cov1 = ~x; // odd ^ even after defining odd and even, instead of putting the cov1 = ~x; as top variable? Feb 10 at 8:10

# 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!