15
\$\begingroup\$

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

\$\endgroup\$
8
  • 3
    \$\begingroup\$ Welcome to Code Golf! \$\endgroup\$ Commented Feb 9, 2023 at 22:38
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Commented Feb 9, 2023 at 23:09
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – roblogic
    Commented Feb 9, 2023 at 23:31
  • \$\begingroup\$ div and mul are not mentioned. Are they allowed? What about ffs() and friends? \$\endgroup\$ Commented Feb 9, 2023 at 23:57
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Feb 10, 2023 at 12:50

3 Answers 3

11
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ ~x appeared twice and only counted once because it looks better \$\endgroup\$
    – l4m2
    Commented Feb 10, 2023 at 6:53
  • \$\begingroup\$ 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? \$\endgroup\$ Commented Feb 10, 2023 at 8:10
4
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.