Check if two blocks of bits dovetail perfectly.


  • A block of bits is a fixed sequence of 8 bits just like this for example : 11110101.

  • For simplicity we refer to truthy/falsey values as 1/0 bits but they can be everything capable of representing those two states in a clear, well defined and consistent way, for example :0/1 x/y False/True "false"/"true" 'a'/'b' []/[...] odd/even >0 / <0 0 / !0

What does it mean dovetail perfectly?

  • 1's bits of one block can fit only into 0's of the other block or outside it.

  • You can shift an entire block left or right but you cannot modify a block nor reverse it.

  • The resulting block must contain all 1's of both inputted blocks and only those.

  • There must not be any 0's between 1's while there can be any trailing and leading 0's.

  • The resulting block can be more than 8 bits long.

  • Example

 Input : [ 10010111, 01011010 ]
             ↓  ↓ ↓↓↓
           01011010   <- shif by 2
  result   0111111111  => dovetails perfectly 

Input: two blocks of bits.

  • You don't need to handle empty blocks (all 0's).

Output: your solution have to clearly state if input blocks can dovetail perfectly as described above or not.

  • the resulting block won't be a valid answer.

Test cases.

00000000, 00000000 | you don't  
00000000, ...      | need to
...     , 00000000 | handle these

11111111, 11111111 -> True
11111111, 10000000 -> True
11110000, 00101000 -> False 
00101000, 10100000 -> True
10000000, 00111000 -> True
00110011, 11001100 -> True
00010000, 11101010 -> False
10000100, 10111101 -> True 
01111010, 01011111 -> True 
10010101, 00001101 -> False 
01010011, 10110000 -> True
00000111, 00010011 -> False
00000011, 00000101 -> False


  • Input/output can be given by any convenient method.
  • You can print it to STDOUT, return it as a function result or error message/s.
  • Either a full program or a function are acceptable.
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.


  • 4
    \$\begingroup\$ Can we take the inputs as 8-bit numbers from 0 to 255? \$\endgroup\$
    – xnor
    Sep 16, 2020 at 9:48
  • 1
    \$\begingroup\$ @Arnauld The test cases seem to say we don't have to handle any all-zero inputs. \$\endgroup\$
    – xnor
    Sep 16, 2020 at 11:00
  • 2
    \$\begingroup\$ @xnor Ah ... the famous 'put some part of the spec in the test cases' joke. :-) Thank you, I totally missed that. \$\endgroup\$
    – Arnauld
    Sep 16, 2020 at 11:03
  • 1
    \$\begingroup\$ @Arnauld true ahahah! Actually it was specified initially, but I missed it during the many reviews on sandbox \$\endgroup\$
    Sep 16, 2020 at 11:59
  • 2
    \$\begingroup\$ That's what I thought, and agreed it's reasonable, but I wondered if you might have just switched conventions because everything else was listed with that order, too, like "false"/"true" which would be surprising because it's strings as well as inverted from our normal conventions of what those words mean. \$\endgroup\$ Sep 16, 2020 at 21:06

15 Answers 15


JavaScript (ES6),  63 54 52  50 bytes

Saved 2 bytes by applying an optimization similar to the one suggested by @AZTECCO on my C answer

Expects (a)(b), where a and b are bytes. Returns 0 if the blocks can dovetail perfectly or 1 otherwise.


Try it online!


The recursive function g attempts to shift b to the left, 1 position at a time, until the following conditions are both met:

  • (a << 8) & b is equal to 0, i.e. a << 8 and b have no set bits in common
  • c = (a << 8) | b is a sequence of consecutive 1's, possibly followed by trailing 0's

For the second test, we add to c the rightmost set bit in c and see if this results in a single 1, by carry propagation along the sequence of consecutive 1's.

We use the following bitwise tricks:

c & -c      // returns the rightmost set bit in c

c & (c - 1) // returns c without the rightmost set bit in c
            // (0 if c is an exact power of 2)


0111111000 + (0111111000 & -0111111000) = 0111111000 + 0000001000 = 1000000000
1000000000 & (1000000000 - 1) = 1000000000 & 0111111111 = 0

We stop the recursion when b = 0, which means that all bits have been thrown away. (This is why we do b << 1 instead of b * 2, so that b is forced to a 32-bit integer rather than an IEEE 754 floating-point number.)


Python 3, 68 bytes

lambda a,b:any(a<<8&b<<x==('01'in bin(a<<8^b<<x))for x in range(17))

Try it online!

The function tries all overlap configurations of the two binary sequences. It performs a bitwise xor for each configuration and checks if all the resulting 1s are consecutive. This gives a false positive for some cases where the xor operation results in a leading 0, so additionally it checks if the bitwise and operation yields 0.

-4 bytes thanks to xnor

  • \$\begingroup\$ Did you mean ...<1>...? \$\endgroup\$
    – xnor
    Sep 17, 2020 at 0:47
  • \$\begingroup\$ @xnor I did not. In many cases, there are trailing zeroes in the binary representation. The 2>... part captures both with and without trailing zeroes. For the ...<2 part, it does not matter. Any overlapping bits happen at the 8th bit or further left. \$\endgroup\$
    – Jitse
    Sep 17, 2020 at 6:58
  • \$\begingroup\$ Oh, I see, that's neat. Would it also work to count '01' and check that this is 0 using 1>, for the same byte count? If so, there's probably something shorter with '01'in. \$\endgroup\$
    – xnor
    Sep 17, 2020 at 7:27
  • \$\begingroup\$ @xnor Good point! That saves some bytes right away. \$\endgroup\$
    – Jitse
    Sep 17, 2020 at 8:46

Python 2, 78 59 57 bytes

Output is via exit code. The program fails (1) for truthy inputs and completes (0) for falsely ones. Input are two non-negative integers.

This is now quite similar to Arnauld's answers, but I found the d&-d trick on this website.


Try it online!

  • \$\begingroup\$ Out of curiosity: where does the q come from in your code? \$\endgroup\$ Sep 17, 2020 at 9:33
  • 2
    \$\begingroup\$ @KevinCruijssen Because chained comparisons are lazily evaluated, q throws a NameError if all comparisons before are True. \$\endgroup\$
    – ovs
    Sep 17, 2020 at 9:37
  • \$\begingroup\$ Ah, I hadn't noticed you throw an error as truthy inputs and not as falsey. That makes sense. And I didn't knew Python comparisons are lazy evaluated like that. If I'd try to use a non-existing variable in Java I would already get an error during compilation way before the program is actually executed. TIL. :) Oh, and nice approach! \$\endgroup\$ Sep 17, 2020 at 9:41
  • 1
    \$\begingroup\$ catonmat.net/low-level-bit-hacks is a nice explanation of multiple bithacks like d & -d to isolate the lowest set bit, with 8-bit examples. (Like the x86 BMI2 instruction blsi.) \$\endgroup\$ Sep 18, 2020 at 19:07

C (gcc),  61 58 57  53 bytes

Saved 4 bytes thanks to @AZTECCO

A port of my JS answer.

Returns 0 if the blocks can dovetail perfectly or a non-zero integer otherwise.


Try it online!

  • \$\begingroup\$ Bah! I don't believe it! After all your help, you had this up your sleeve all along...! \$\endgroup\$ Sep 16, 2020 at 15:03
  • \$\begingroup\$ @Dominic Best man wins - and he always has a whopper up his sleeve! :D \$\endgroup\$
    – Noodle9
    Sep 16, 2020 at 15:11
  • \$\begingroup\$ I'll do. Btw glad to see a C answer of you Sir! \$\endgroup\$
    Sep 16, 2020 at 21:24

Jelly,  18  17 bytes


A dyadic Link accepting two lists of eight ones/zeros which yields 1 if they may dovetail, or 0 if not.

Try it online! Or see the test-suite (I reordered them to have the eight truthy cases followed by the five falsey cases).

There is probably a terser way...


T_8+Ɱ17;ṢIPʋ€T}1e - Link: block A; block B
T                 - truthy indices of A
 _8               - subtract eight from each
     17           - seventeen
   +Ɱ             - map with addition -> a list of the 17 shifted versions of T
            €     - for each:
             T}   -   using the truthy indices of B as the right argument
           ʋ      -   last four links as a dyad:
       ;          -     concatenate
        Ṣ         -     sort
         I        -     incremental differences
          P       -     product (0 if two 1-bits collide; >1 if zero-gaps would result)
               1e - does 1 exist in that result?

05AB1E, 18 bytes


Input as a pair of lists of bit-integers, outputs 1/0 for truthy/falsey respectively.

Try it online or verify all test cases. (The test suite contains an additional Ù after the æ, otherwise it'll time out. The single TIO takes roughly 35-40 seconds without this uniquify.)


¬                # Push the first list of the (implicit) input-pair (without popping)
 0*              # Multiply each value by 0 to create a list of 0s of that same length
   æ             # Get the powerset of this list of 0s (including empty list)
                 # (prefixes builtin would be preferably here, but unfortunately it lacks
                 #  an empty list; obviously this powerset contains a lot of duplicated
                 #  lists, which is why the uniquify `Ù` in the test suite is used to
                 #  make the program faster)
    δ            # Apply double-vectorized (using the powerset of 0s and implicit input)
     ì           #  Prepend the list of 0s to the inner input-list
      `          # Pop and push both list of lists separated to the stack
       â         # Use the cartesian product to get every possible pair of inner lists
        ε        # Map each pair of lists to:
          ζ      #  Zip/transpose; swapping rows/columns,
         0       #  using a 0 as trailing filler-item if the lists are unequal in length
           O     #  Sum each inner pair
            0Ú   #  Remove all leading and trailing 0s from this list
              P  #  Take the product of the remaining values
               Θ #  And check that this is equal to 1
        }à       # After the map: check if any are truthy by taking the maximum
                 # (after which this is output implicitly as result)

Try it online for a step-by-step from input to output (with the uniquify to speed it up).


Husk, 15 bytes


Try it online! or verify test cases. Output is a positive integer for truthy cases and 0 for falsy.


Parentheses added for clarity.

VΠ¤(׿≠)(→kΣQ(Ṡ+mṗ))   Implicit inputs: two lists of integers.
  ¤( A )(     B    )   Apply B to both and combine with A.
         →kΣQ(Ṡ+mṗ)    Argument is a list x.
                m      Map
                 ṗ     primality test
              Ṡ+       and concatenate before x.
                       Since 0 and 1 aren't primes, this effectively prepends 8 zeros.
            Q          All contiguous slices.
          k            Classify (into separate lists)
           Σ           by sum.
         →             Get the last class, i.e. the slices with maximal sum.
                       They are those that contain all the 1s of x.
    ׿≠                Combining function:
    ×                  Cartesian product by
     ż                 zip (preserving overflowing elements) by
      ≠                absolute difference.
                       Now we have a list of all combinations of slices from both extended lists,
                       with 1 and 1 producing 0.
V                      Does any of them have
 Π                     nonzero product (all 1s)?
  • \$\begingroup\$ Nice! I think C answers and some others can benefit how you used output rules \$\endgroup\$
    Sep 16, 2020 at 21:01

x86 32-bit machine code, 27 bytes

An x86-64 version would be callable from C as int dovetail(dummy, unsigned x, unsigned y); Returns EAX=0 for dovetail, non-zero for not; all paths of execution for non-zero inputs that don't dovetail lead to EAX=(x<<n)|y as the last thing calculated in EAX before returning. Also more simply and obviously, returns ZF=1 for dovetail, ZF=0 for not.

Try it online!. NASM listing: offset, machine code, source

 1                         dovetail:                   ; bool dovetail (ESI, EDX)
 2 00000000 86F2               xchg  dh, dl             ; shl edx,8 ; upper bytes are zero
 3                         .loop:
 4 00000002 85F2               test  edx, esi
 5 00000004 7510               jnz   .overlap           ; skip any bit conflicts
 7 00000006 8D0432             lea   eax, [edx+esi]     ; equivalent to | or ^ for non-overlapping bits
 8 00000009 0FBCC8             bsf   ecx, eax           ; count trailing zeros
 9 0000000C D3E8               shr   eax, cl            ; shift out low zeros
10 0000000E 40                 inc   eax                ; turn contiguous low bits into 1 set bit
12 0000000F 8D48FF             lea  ecx, [eax-1]        ; clear lowest set bit
13 00000012 21C8               and  eax, ecx            ; like blsr  eax, eax
14 00000014 7404               jz   .dovetail_found     ; there was only 1 set bit, now 0
15                         .overlap:
16 00000016 01F6               add  esi, esi
17 00000018 79E8               jns  .loop             ; keep looping until ESI hits the top
19                         .dovetail_found:
20                             ;; return value in ZF:
21                                   ; 1 for dovetail detection by BLSR
22                                   ; 0 for exiting loop via ESI setting SF: implies non-zero
23 0000001A C3                 ret

See https://catonmat.net/low-level-bit-hacks for an overview of bithack tricks including isolating or clearing the lowest set bit.

Alternate versions:

BMI1 blsr eax, eax is 5 bytes, same as lea edx, [rax-1] / and eax, edx. That would require BMI1 (Haswell+, Piledriver+). I used and instead of test so an integer result in EAX would be available.

BMI1 blsi ecx, eax (5B) / add eax, ecx (2B) (eax += lowest_set_bit(eax)) turned out not to be the shortest way to turn a contiguous bit-range into a single set bit. Instead, shifting to the bottom with bsf / shr / inc saved 1 byte in 32-bit code, for a total of 6 bytes to turn a contiguous bit-range into a single set bit. An x86-64 version (no single-byte inc encoding) could save instructions at equal code-size by doing that, though, if BMI1 was available.

I was hoping to avoid doing the x & y == 0 test separately from combining the bits. e.g. by XORing them together and checking that a contiguous bit-range started at the bottom of one of the inputs:

    mov  eax, edx
    xor  eax, esi
    jz  .all_cancelled      ; exclude all-zeros from the 1-set-bit test

    blsi  ecx, esi          ; isolate lowest set of the shifting input
    add   eax, ecx          ; carry turns contiguous set bits into 1
                    ; BROKEN, need blsi(esi|edx)

But we can't just use the lowest set bit of the XOR result; some conflicting bits might have cancelled each other. e.g. x=0b110010 y=1 would give a false-positive when with x ^ (y<<1) = 0b110000 having all its set bits contiguous.

And it doesn't work to isolate the lowest set bit of the input you're shifting; once you shift it left past the lowest set bit of the other input, you need to be adding that isolated bit instead. e.g. the following input was mis-handled by my first version using xor and blsi ecx, esi, because it only dovetails with ESI's lowest bit shifted left past EDX's lowest set bit.

mov edx, 0b0110010
mov esi, 0b1001100

This way could still work with some kind of min(blsi(x), blsi(y)), or blsi(x|y), but doing that separately is not a win.


C (gcc), 105 \$\cdots\$ 63 62 bytes

Saved a whopping 13 bytes thanks to the man himself Arnauld!!!
Saved a byte thanks to AZTECCO!!!


Try it online!

Returns \$!0\$ for true and \$0\$ otherwise.


Shifts the first parameter, \$a\$, over \$8\$-bits so we can try all different shift positions by just shifting the second parameter, \$b\$. Loops over all shifts of \$b\$ checking to see if all bits are ever different from \$a\$ and \$b\$ forms one continuous block of \$1\$s when combined with \$a\$.

  • \$\begingroup\$ ...I've been frantically fixing my buggy first 'C' attempt, and when I finally post the fix, I see that you've got almost exactly the same strategy... Now I need to learn how you saved those 3 bytes... \$\endgroup\$ Sep 16, 2020 at 14:14
  • \$\begingroup\$ @DominicvanEssen Yeah, basically shifting and making sure the bits are all different but form a block of 1s when combined. Started dead simple to make sure it worked and then started doing tricks - best way with C. One nice trick is n & (n - 1) is zero iff \$n\$ is a power of \$2\$. \$\endgroup\$
    – Noodle9
    Sep 16, 2020 at 14:19
  • 5
    \$\begingroup\$ t/=t&-t can be used instead of t>>=__builtin_ctz(t) \$\endgroup\$
    – Arnauld
    Sep 16, 2020 at 14:32
  • \$\begingroup\$ @Arnauld Now that's a nice trick - thanks! :D \$\endgroup\$
    – Noodle9
    Sep 16, 2020 at 14:36
  • 1
    \$\begingroup\$ @AZTECCO Thanks for reminding me, noticed that but go so into into it forgot. Great challenge - thanks muchly! :D \$\endgroup\$
    – Noodle9
    Sep 16, 2020 at 21:13

Retina 0.8.2, 82 81 bytes



Try it online! Link includes test cases. Explanation:


Create duplicates of the input with ;s inserted at every position.


Swap the two inputs if the ; lies within the second.


Try to dovetail the part between the ; and the , with the other input.


Count the number of bits in each overlap.


Delete the separators.


Check whether a dovetail produced a valid result. Edit: Saved 1 byte by returning any non-zero value for a valid result (value is number of possible dovetailings plus one if concatenating the inputs is a valid dovetailing).

  • \$\begingroup\$ Yes you can drop it! \$\endgroup\$
    Sep 16, 2020 at 21:10

Perl 5 -p, 68 bytes

s/\b0+|0+\b//g;s/(1*)(.*?)(1*) //;y/01/10/;$_=/^(0*$1)?$2(${3}0*)?$/

Try it online!

  • s/\b0+|0+\b//g trims 0 from two blocks

  • s/(1*)(.*?)(1*) // substitution to remove the first argument, and capture 3 groups :

    • $1: the left ones
    • $2: shortest sequence between
    • $3: the right ones (eventually)
  • y/01/10/ transliteration of second argument remaining (bitwise not)

  • /^(0*$1)?$2(${3}0*)?$/ the pattern second argument (inverted) must match


Factor, 149 139 bytes

: d ( a b -- ? ) [ 8 [ 0 suffix ] times 15 rotate ] bi@
all-rotations [ dupd [ + ] 2map [ 0 = ] trim all-equal? ] map
f [ or ] reduce nip ;

Try it online!

Gets the input as arrays of integers.

A naive solution - pads both arrays with 8 additional 0s, then adds each of the rotations of the second array to the first one, trims the leading/trailing zeros and check if the resulting arrays consist only of one number (1).


C (gcc), 94 82 71 70 bytes

Edit: -12 bytes by poring over Noodle9's similar C answer and rather shamelessly stealing all of the golfing tricks that I could use here... so please upvote that one, too!

More edits: ...thanks to various stolen tips & tricks from Arnauld, also -12 more bytes...


Try it online!

My first ever answer in 'C' (which embarassingly didn't work the first time: thanks to Arnauld for spotting the bug...).

Input is two 8-bit integers, outputs '-1' (truthy) if bits of input dovetail together perfectly, '0' (falsy) otherwise.

Works by first bit-shifting b by 9 bits, and then testing for successful dovetailing with a shifted by 1..18 bits (so, all-the-way to the right up to all-the-way to the left).
Tests dovetailing at each position by checking that a AND b is zero (so there are no 'clashing' bits), then taking A XOR B, chopping-off any trailing zeros, and testing whether x AND (x+1) is equal to zero (which is only true for 2^n-1 = strings of 1-bits).

  • \$\begingroup\$ I also have an 81 byte answer, but it leaves-behind disrupted global variables & so cannot be run multiple times sequentially. I assume that this is frowned-upon (or outright banned): perhaps someone can confirm/refute this...? \$\endgroup\$ Sep 16, 2020 at 12:16
  • \$\begingroup\$ Regarding your question: this is indeed banned \$\endgroup\$
    – Arnauld
    Sep 16, 2020 at 12:37
  • \$\begingroup\$ Rats! How did I miss that... \$\endgroup\$ Sep 16, 2020 at 13:13
  • 1
    \$\begingroup\$ ...fixed at last \$\endgroup\$ Sep 16, 2020 at 14:53
  • \$\begingroup\$ The c/=c&-c trick works fine with Noodle9's answer, but in your case it may result in a division by zero and a floating point exception. (Example: a=9 / b=9.) \$\endgroup\$
    – Arnauld
    Sep 16, 2020 at 15:10

Charcoal, 29 bytes


Try it online! Works by dovetailing in base 3, which avoids issues other answers have when trying to XOR or add the values together. Explanation:

  α                             (Uppercase alphabet)
¬⬤                              No indices match
   №                            (Non-zero) Count of
                           01   Literal string `01` in
                   θ            First input
                  ⍘ ³           Converted as if base 3
              ×                 Multiplied by
                ³               Literal 3
               X                Raised to power
                 κ              Current index
      ⁺                         Plus
            η                   Second input
           ⍘ ³                  Converted as if base 3
       ×                        Multiplied by
         ³                      Literal `3`
        X                       Raised to power
          χ                     Predefined constant 10
     ↨                ³         Converted to base 3 as a list
    ⭆                           Map over digits
                         λ      Current digit
                        ⍘ ²     Converted to base 2 as a string
                       ⮌        Reversed
                                Implicitly print
  • \$\begingroup\$ What's the difference between true and false outputs? They both appear to be - when I run the linked program \$\endgroup\$
    – Jo King
    Sep 16, 2020 at 12:44
  • \$\begingroup\$ @JoKing There's a byte missing. I'll add it shortly. \$\endgroup\$
    – Neil
    Sep 16, 2020 at 15:28
  • \$\begingroup\$ @JoKing Or better still, I can golf it away again... \$\endgroup\$
    – Neil
    Sep 16, 2020 at 15:29

Java 8, 86 83 82 bytes

(a,b)->{int i=18,t;for(a<<=8;--i>0;i=(a&b)>-(t&(t&-t)+t)?i:0,b*=2)t=a|b;return i;}

Inspired by halve the other answers. -3 bytes thanks to @AZTECCO.
-1 byte thanks to @ceilingcat.

Inputs as (32-bit) integers. Output as -1 for truthy and 0 for falsey.

Try it online.


(a,b)->{               // Method with two integer parameters and boolean return-type
  int i=18,            //  Index-integer, starting at 18
      t;               //  Temp-integer, uninitialized
  for(a<<=8;           //  Bit-shift the first input-integer `a` 8 bits to the left
      --i>0            //  Loop `i` in the range (18, 0):
      ;                //    After every iteration:
       i=(a&b)         //     Get `a` bitwise-AND `b`
         <             //     And check that it's smaller than:
          -(           //      The negative of:
            t          //      `t`
             &         //      Bitwise-AND with:
              (t&-t)   //       `t` bitwise-AND `-t`
                    +t)//       and add `t`
         ?             //     If this is truthy:
          0            //      Change `i` to 0 (which will also stop the loop)
         :             //     Else:
          i,           //      Keep `i` the same
       b*=2)           //     And multiply `b` by 2
    t=a|b;             //   Set `t` to `a` bitwise-OR `b`
  return i;}           //  Return `i` as result (where -1 means we've changed `i` to 0
                       //  manually as truthy output and 0 means the loop has fully
                       //  looped as falsey output)
  • \$\begingroup\$ Why don't you use --i>0; and return i? \$\endgroup\$
    Sep 17, 2020 at 15:18
  • \$\begingroup\$ @AZTECCO The TIO you've linked all returned 0, but you're indeed correct I can save 3 bytes with -->0. Thanks! \$\endgroup\$ Sep 17, 2020 at 16:44
  • \$\begingroup\$ Previous link was wrong sorry, this may work.. Not sure though. \$\endgroup\$
    Sep 17, 2020 at 16:57

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.