13
\$\begingroup\$

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

\$\endgroup\$
11
  • \$\begingroup\$ What output formats are allowed? \$\endgroup\$ Mar 24 at 16:20
  • 2
    \$\begingroup\$ Does the output order matter? \$\endgroup\$
    – pajonk
    Mar 24 at 17:03
  • 1
    \$\begingroup\$ If the order matters, the third test-case should be 13,14, I think. \$\endgroup\$
    – pajonk
    Mar 24 at 19:28
  • 6
    \$\begingroup\$ So this is about interleaving bits both ways? Took a lot of looking at the examples to figure that out because the text didn't use clear terminology or walk through any of the examples to describe where each bit came from, and the first few also work with concatenation. "Blend" in bit-manipulation and SIMD is normally a select operation, e.g. blend two integers according to a mask would give you a same-length integer with some bits from each input (unless the mask was all-zero or all-one). \$\endgroup\$ Mar 25 at 3:44
  • 2
    \$\begingroup\$ To me it'd be much easier to understand that we should take the two numbers as piles of bits, and provide the two results are out- and in-shuffles respectively. \$\endgroup\$ Mar 25 at 16:36

17 Answers 17

7
\$\begingroup\$

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.
\$\endgroup\$
5
  • \$\begingroup\$ You've shown us how, but why does this work? \$\endgroup\$
    – emanresu A
    Mar 24 at 18:35
  • 2
    \$\begingroup\$ @emanresuA Think of the conversion from base 4 as a conversion from base 2 with zeroes interleaved, and the twos as ones shifted once to the left. \$\endgroup\$ Mar 24 at 22:34
  • \$\begingroup\$ ...-2? \$\endgroup\$ Mar 24 at 23:14
  • 1
    \$\begingroup\$ @UnrelatedString very nice golf, thanks! \$\endgroup\$ Mar 25 at 0:16
  • \$\begingroup\$ Came up with it after ten minutes of trying to think of how I could golf æ×[1,2],[2,1] down :P \$\endgroup\$ Mar 25 at 0:19
6
\$\begingroup\$

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: ⊤,⍥⊥⍥,⌽⍤⊤

\$\endgroup\$
6
\$\begingroup\$

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

\$\endgroup\$
7
  • \$\begingroup\$ related \$\endgroup\$
    – loopy walt
    Mar 25 at 11:26
  • \$\begingroup\$ Also, may I ask the same question as at the linked answer (with the same apology for my ignorance) how clmul would fare in comparison? \$\endgroup\$
    – loopy walt
    Mar 25 at 11:54
  • \$\begingroup\$ @loopywalt: Not an instruction I've played with much; it can unpack bits like pdep? PCLMULQDQ is a 6-byte instruction with the VEX or legacy-SSE encoding. Nor sure how that would help, although possibly we could justify taking both inputs in the low 2 elements of XMM0 or something, so we only need it once? Would still need a constant somehow, I assume, and that takes a lot of bytes (either in memory plus a RIP-relative addressing mode, or mov-immediate + movd). Also, SSE/AVX doesn't have a 3-byte LEA to shift/add all in one. \$\endgroup\$ Mar 25 at 15:04
  • \$\begingroup\$ Not as general as pdep but it can do this particular special case. As I indicated I'm not an assembly buff, but the underlying maths is that if you do the carryless multiplication (aka polynomial multiplication over the field with two elements) Q = P x P mod 2 with two times the same argument P = p0 + p1 X + p2 X^2 ... then the result will have coefficients q2n=pn with all odd coefficients vanishing. Essentially because all mixed terms in the product expansion vanish mod 2 because they come in pairs. So I was wondering whether not having to set up the mask could help in any way. \$\endgroup\$
    – loopy walt
    Mar 25 at 15:53
  • \$\begingroup\$ ... though from what you write I suspect clmul family has other overheads. \$\endgroup\$
    – loopy walt
    Mar 25 at 15:53
5
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

C (clang), 91 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.

\$\endgroup\$
1
  • \$\begingroup\$ Based on my Java answer: 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;} (86 bytes). Can very likely be further shortened. \$\endgroup\$ Mar 25 at 17:36
4
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I think returning a map object instead of a list is permitted per meta consensus (though it's more about a Prolog style of "generator", the comments about Python haven't been disputed). \$\endgroup\$ Mar 25 at 0:02
4
\$\begingroup\$

Wolfram Language (Mathematica), 41 bytes

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 16 14 bytes

F²⊞υ↨⁴↨N²I⁺Συυ

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

F²⊞υ↨⁴↨N²

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

I⁺Συυ

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.

\$\endgroup\$
2
  • \$\begingroup\$ ...-2? \$\endgroup\$ Mar 25 at 0:12
  • 1
    \$\begingroup\$ @UnrelatedString Gosh I was overthinking this wasn't I... \$\endgroup\$
    – Neil
    Mar 25 at 0:22
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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