The interstice of two binary numbers

Question

Given two integers, compute the two numbers that come from the blending the bits of the binary numbers of equal length(same number of digits, a number with less digits has zeros added), one after the other, like such:

2 1   
10 01    
1 0     
1001    
0 1    
0110  

some examples:

Input	Binary	Conversion	Output
1,0	1,0	10,01	2,1
1,2	01,10	0110,1001	6,9
2,3	10,11	1101,1110	13,14
4,9	0100,1001	01100001,10010010	97,146
12,12	1100,1100	11110000,11110000	240,240
1,3	01,11	0111,1011	7,11
7,11	0111,1011	01101111,10011111	111,159
7,3	111,011	101111,011111	47,31

The program must take integers as inputs and give integers as outputs

Answer 1

Jelly,  8  6 bytes

-2 Thanks to Unrelated String!

Bḅ4S+$

A monadic Link that accepts a pair of non-negative integers and yields a pair of non-negative integers.

Try it online! Or see the test-suite.

How?

Bḅ4S+$ - Link: integers A           e.g. [4, 9]
B      - convert A to binary             [[1,0,0],[1,0,0,1]]
 ḅ4    - convert from base 4             [16,65]
                                 ...i.e. insert zeros between the binary digits
                                         [16,65] = [[1,0,0,0,0],[1,0,0,0,0,0,1]]
     $ - last 2 links as a monad - f(x):
   S   -   sum x                         81
    +  -   add x (vectorises)            [97,146]
                                 ...i.e. the above S+$ is a rearrangement of
                                         [(16+16)+65,(65+65)+16]
                                         where 16+16 is the zero spaced bits of 4
                                         shifted one place to the left & similarly
                                         for (65+65) with respect to 9.

Answer 2

APL (Dyalog Extended), 9 bytes

,⍥⊥⍥,∘⌽⍨⊤

Try it online!

⊤ Create a matrix where each column holds a binary representation of one of the integers.
f∘⌽⍨ Apply the function f with that matrix on the left and the reverse of the matrix on the right.
,⍥⊥⍥, Flatten both matrices, convert both resulting vectors from binary and pair them up to return a length-2 vector of integers.

Alternatively, for a bit more symmetry: ⊤,⍥⊥⍥,⌽⍤⊤

Answer 3

3 versions, all work in 32 or 64-bit mode:
x86 machine code (clmul + AVX-512), 17 bytes. (Or 16B with AMD XOP instead of AVX-512)
x86 machine code (clmul + AVX1 32->64-bit, output pair in same order as input pair), 18 bytes
x86 scalar machine code (with BMI2 pdep), 22 bytes

x86 machine code (clmul + AVX-512), 17 bytes

Takes 2 integers in the low two 16-bit elements of XMM0, returns 2 integers in 32-bit elements #1 and #0 of XMM0 (in that order, opposite of the input order). Swapping them would take another 4-byte instruction, shufps xmm0, 0b00_01 (or a left shift of the original and a different rotate count), but if we're willing to stretch the bounds of calling-convention plausibility, this is fine. If not, use the 18 byte version below.

NASM listing: address, hexdump of machine code, source

;;; 16-bit inputs packed in XMM0,  32-bit outputs packed in XMM0 (opposite order)
                        bit_interleave_bothways_avx512:
00 C4E37944C000     vpclmulqdq  xmm0, xmm0, 0      ; space out each bit
                      ;    movq       rax, xmm0
                      ;    rol        rax, 33      ; non-AVX512 emulation for the low qword
                      ;    movq       xmm1, rax
06 62F1F50872C821   vprolq     xmm1, xmm0, 33      ; <<=1 and swap 32-bit halves
0D 0F56C1           orps       xmm0, xmm1          ; combine
10 C3               ret

Key building block: Carryless multiply of a number by itself spaces out the bits, interleaving with zeros. x86 has that as pclmulqdq, single-uop on modern Intel, e.g. Skylake (and 4 uops on AMD Zen1/2/3). Same size for VEX or legacy-SSE encoding, 6 bytes. With an immediate 0, reads the low qword of each input, writes a 128-bit output to the full dqword XMM register.

AVX-512 has SIMD rotates, but unfortunately earlier Intel doesn't. (TODO: AMD's XOP instruction set has vprotq with a 6-byte encoding according to NASM, 1 shorter than AVX-512 EVEX. AFAIK equivalent behaviour with an immediate count of 33. Would only run on AMD Bulldozer-family, which I don't have, so would be inconvenient to test but would still satisfy the rules of working on at least one implementation of a language.)

Combining the swap to line up outputs with each other along with a shift by 1 bit can be done with one rotate, but only with an EVEX encoding (4-byte prefix + opcode + modRM + imm8 = 7-byte encoding.) And only within a 64-bit qword, which means limiting the output size to two 32-bit integers, which means limiting the input to 16-bit integers.

Legacy SSE1 encodings are the smallest, only the escape byte no mandatory prefixes. We didn't dirty any YMM upper halves, so there's no SSE/AVX transition penalty here from mixing VEX/EVEX with legacy SSE. vorps xmm0, xmm0, xmm1 or por xmm0, xmm1 would each be 4 bytes.

x86 machine code (clmul 32->64-bit), 18 bytes

Requires only AVX1 + CLMUL CPU features, e.g. Sandybridge.

As above with clmul, but using separate left-shift and swapping halves of the output to line them up for OR. This way we can handle 32-bit inputs (and the corresponding 64-bit outputs), and output in the same order as inputs.

Includes comments that trace the 4,9 test-case through it, confirmed from actual single-stepping in GDB. Would have output in hex, but the test cases strangely use decimal despite this being about bit-manipulation.

                        bit_interleave_bothways_avx512_32it:
                                                 ; xmm0.v4_int32 = { 4, 9, 0, 0}
30 C4E37944C000    vpclmulqdq  xmm0, xmm0, 0     ; xmm0.v2_int64 = { 16, 65 }  value after clmul, from GDB
36 C5F9D4C8        vpaddq      xmm1, xmm0, xmm0           ; xmm1 = { 32, 130 }  ; VEX allows copy + left-shift with same size as paddw
3A 0FC6C04E        shufps      xmm0, xmm0, 0b01_00_11_10  ; xmm0 = { 65, 16 }
3E 0F56C1          orps        xmm0, xmm1                 ; xmm0 = { 97, 146 }  ; in-place swap saves a byte vs. pshufd
41 C3              ret

Two 4-byte instructions (vpaddq and shufps) are only 1 byte larger than a single 7-byte EVEX vprolq.

---

x86 scalar machine code (with BMI2), 22 bytes

                bit_interleave_bothways:
00 BA55555555     mov   edx, 0x55555555
05 C4E243F5FA     pdep  edi, edi, edx
0A C4E24BF5F2     pdep  esi, esi, edx
0F 8D047E         lea   eax, [rsi + rdi*2]  ; low bit = low b of arg1 = first out
12 8D1477         lea   edx, [rdi + rsi*2]  ; low bit = low b of arg2 = second out
15 C3             ret

Callable with the x86-64 System V calling convention (args in EDI, ESI),
return values in EAX (first), EDX (second).

The output is only 32 bits wide. This limit is more justifiable in 32-bit mode, where the same machine code does the same thing, disassembling as lea eax, [esi + edi*2] and so on. (Using 64-bit operand-size would cost an extra REX.W byte on each PDEP and LEA, and need a 10-byte mov rdx, 0x5555555555555555 instead of 5-byte mov reg, imm32, so an extra 9 bytes total). The same machine code would not work in 16-bit mode; scaled index addressing modes would need an address-size prefix. VEX prefixes (for pdep) only decode in 16-bit protected mode, not real.

The key building block is pdep, parallel bit-deposit, which takes low source bits and puts them at places where the control mask was non-zero. With 0b...010101, this unpacks each input by interleaving it with zeros.

Doing (x << 1) + y and vice versa with LEA merges the unpacked bits into a single interleaved integer. + instead of the more idiomatic | allows using the shift-and-add LEA instruction.

Try it online! with a brief test harness. (Only uses the first return value as exit status; I tested by single-stepping in a debugger. Not updated for the later CLMUL versions.)

Answer 4

Vyxal, 7 bytes

b4vβ:∑+

Try it Online!

Port of (my suggested golf to) Jonathan Allan's Jelly solution. Input as a list of the two numbers.

b          Convert each to binary,
 4vβ       then convert each from base 4.
b4vβ       This has the effect of interleaving with a bit pattern of all zeroes.
      +    Add each to
    :∑     their sum.

Answer 5

C (clang), ⁹¹ 86 bytes

i;t;f(*a,*b){for(i=1<<17;i/=2;*b=*b&~i|(*b&i)*i)t=*a=*a&~i|(*a&i)*i;*a+=*b*2;*b+=2*t;}

Try it online!

Saved 5 bytes thanks to Olivier Grégoire!

Inputs pointers to two integers.
Returns the Interleaved Values™ (Neil) through the input pointers.

Answer 6

Python, 54 bytes (@UnrelatedString)

lambda*I:map(sum,2*[J:=[int(f"{x:b}",4)for x in I]],J)

Attempt This Online!

Old Python, 57 bytes

lambda*I:[*map(sum,2*[J:=[int(f"{x:b}",4)for x in I]],J)]

Attempt This Online!

Answer 7

Wolfram Language (Mathematica), 41 bytes

If[#1,0,Tr[a=#~Mod~2]+a+4#0[(#-a)/2]]&

Try it online!

Answer 8

x64 machine code (requires VPCLMULQDQ, supported by Intel Ice Lake and later), 22 21 bytes

Totally different approach than the BMI2 solution, but by some cosmic coincidence it's exactly the same size, well it was until I saved a byte.

0:  c4 e3 7d 44 c0 00       vpclmullqlqdq ymm0,ymm0,ymm0
6:  c4 e3 fd 00 c8 4e       vpermq ymm1,ymm0,0x4e
c:  c5 f5 d4 c9             vpaddq ymm1,ymm1,ymm1
10: c5 f5 eb c0             vpor   ymm0,ymm1,ymm0
14: c3                      ret 

Takes the input in a slightly odd way: a 256-bit vector with a 64bit number at index 0 and at index 2, the rest just padding. Maybe cheating?

Output is in a 256-bit vector again, but since it's two 128-bit numbers, that doesn't feel like cheating to me.

The idea here is that a carryless square is equivalent to spacing the bits out just like we need here, so the first step is to carrylessly-multiply the input with itself. Then vpermq is used to get a copy of the squares but with the low and high halves switched around, vpaddq shifts that all left by 1, and vpor merges the even and odd bits together.

If you want to try this code, beware: there's a high chance your processor doesn't support this vpclmulqdq instruction. It was introduced with Intel's Ice Lake microarchitecture and is also supported by Tiger Lake and Rocket Lake. It is not officially supported on Alder Lake, but can be enabled on certain systems. Since this instruction is not officially part of AVX-512, it may not be present in future implementations.

Answer 9

JavaScript, 55 bytes

q=v=>v&&q(v>>1)*4+v%2,a=>a.map((x,i)=>q(x)*2+q(a[i^1]))

Try it online!

Answer 10

Java (JDK), 89 bytes

(l,r)->{for(int i=1<<16;i>0;r=r&~i|(r&i)*i,i/=2)l=l&~i|(l&i)*i;return r+l*2+","+(l+r*2);}

Try it online!

This first interweaves 0 between each bit of each number, then weaves the two numbers together in both directions.

Answer 11

Pip, 22 bytes

L2PFB R J:R*TB(R:g)ZD0

Takes the two numbers as command-line arguments. Attempt This Online!

Explanation

L2PFB R J:R*TB(R:g)ZD0
L2                      Loop twice:
               R:         Reverse in-place
                 g        The list of command-line args
            TB(   )       Convert each to binary
          R*              Reverse each binary representation
                   ZD0    Zip, filling in missing values with 0
        J:                Join into a single string of 1s and 0s
      R                   Reverse
   FB                     Convert from binary back to decimal
  P                       Print

Answer 12

Charcoal, 16 14 bytes

Ｆ²⊞υ↨⁴↨Ｎ²Ｉ⁺Συυ

Try it online! Link is to verbose version of code. Edit: Saved 2 bytes thanks to @UnrelatedString. Explanation:

Ｆ²⊞υ↨⁴↨Ｎ²

Input the two integers, convert them to base 2, and then convert them from base 4. This spaces the bits in the integers out.

Ｉ⁺Συυ

Vectorised add the list to its doubled sum. This interleaves the bits in both ways.

Example: With inputs of 4 and 9, these are 0100 and 1001 in binary, and spaced out these are 00010000 and 01000001. Adding the sum of these to each results in 00010000+00010000+01000001 and 00010000+01000001+01000001, which is equivalent to 00100000+01000001 and 00010000+10000010, resulting in 01100001 and 10010010, which are the desired interleaved values.

Answer 13

PARI/GP, 35 bytes

f(a)=if(a,4*f(a\2)+a%2*[2,1;1,2],a)

Takes input as a vector of two integers.

Attempt This Online!

Answer 14

05AB1E, 6 bytes

b4öDO+

I/O as a pair of integers.

Port of @JonathanAllan's Jelly answer, so make sure to upvote him as well!

Try it online or verify all test cases.

Explanation:

b       # Convert both integer in the (implicit) input-pair to binary strings
 4ö     # Convert them from base-4 strings back to integers
   D    # Duplicate this pair of integers
    O   # Sum them together
     +  # Add this sum to both values
        # (after which the resulting pair is output implicitly)

Answer 15

Desmos, 94 87 bytes

f(a,b)=[g(a),g(b)]+g(a)+g(b)
g(A)=total(mod(floor(A/2^k),2)4^k)
k=[0...log_2(A+0^A)+.5]

Uses the base-4 interleaving trick that some of the other answers are using. Not sure if this is the optimal strategy for Desmos though, I will definitely look at alternate strategies.

The +.5 trick works on the last line because if the end of an arithmetic range is not an integer, it will round it instead. For example, [1...3.5] is the same as [1...4], while [1...3.4] is the same as [1...3]. We take advantage of the implicit rounding by noting that round(x-.5) is equal to floor(x), so we can convert [0...floor(log_2(A+0^A))+1] to [0...log_2(A+0^A)+.5].

Try It On Desmos!

Try It On Desmos! - Prettified

Answer 16

Factor, 59 bytes

[ [ 64 <bits> ] bi@ 2dup swap [ vmerge bits>number ] 2bi@ ]

Try it online!

• [ ... ] bi@ Call a quotation on two objects.
• 64 <bits> Convert an integer to a virtual sequence of sixty-four booleans.
• 2dup swap Set up the data stack for both interleavings. a b -> a b b a
• [ ... ] 2bi@ Call a quotation on two pairs of objects.
• vmerge Interleave two sequences.
• bits>number Convert a boolean sequence to an integer.

Answer 17

ARMv8.2 A64 machine code (requires FEAT_SHA3), 16 bytes

0e20e000 6e004001 ce608c20 d65f03c0

Following the AAPCS64, this takes a uint32x2_t in the low half of v0 and returns a uint64x2_t in v0.

Disassembled:

0e20e000    pmull   v0.8h, v0.8b, v0.8b
    // Self-multiply as polynomials over GF(2);
    // because this is a ring of characteristic 2, (a+b)^2 = a^2 + b^2 holds,
    // thus squaring doubles each exponent in the polynomial, spreading out the bits.
6e004001    ext v1.16b, v0.16b, v0.16b, #8
    // Extract bytes 8–23 from the concatenation of v0 and v0, and put them into v1.
    // This swaps the positions of the two 64-bit numbers.
ce608c20    rax1    v0.2d, v1.2d, v0.2d
    // Rotate each 64-bit element of v0 left by 1
    // and then take the exclusive-or with v1, and put the result in v0.
d65f03c0    ret
    // Return.