Bit delivery in Bin City

Question

sandbox

Story

Similar to a newspaper route you have been tasked with delivering bits to the residents of Bin City. Just as certain people like certain newspapers, the citizens of Bin City prefer either \$1\$s or \$0\$s delivered to their doorstep. Unfortunately, your new boss has arranged the deliveries in an awkward manner.

The residential streets of Bin City all have multiples of \$8\$ houses. So naturally, your delivery routes are organised as a series of one or more bytes. Your boss has laid out the deliveries as follows: first off, start at the house at the beginning the street on the left-side, followed by the house opposite on the right-side of the street, then the next house after the first one on the left-side of the street, then the one opposite it on the right-side, etc. The \$1\$s and \$0\$s to be delivered along this route are stored, in order, in the bits of the bytes.

Task

You've quite rightly deduced it would be far easier and more time effective to deliver the bits starting from the first house on the left-side of the street and continue on delivering bits up the left-side to the end. Then cross the street to the house opposite on the right-side and continue on down the right-side back to what would have originally been your second delivery at the end.

Illustration for eight houses (one byte)

The original input route is on the far left next to the byte containing the bits to be delivered along that route. Beside it, to the right, is the output byte with the bits rearranged for the new improved delivery route on the far right.

Input and output

The input will be between \$1\$ and \$8\$ bytes long, organised by your boss in a back-and-forth left-side to right-side manner as above. This can be in any convenient byte-wise way (eg not a list of bits, but a list of bytes, words, or double-words etc is ok). A 64-bit integer along with the bit-length is ok too. A bit-length will be needed for any structure using elements larger than a byte. The order can be in any convenient bit-wise way (i.e. least-significant to most-significant bit or vice versa) and any convenient byte-wise way (eg first element in a byte list to last or vice versa, least--significant to most-significant byte or vice versa in a list or words or double-words etc traversed first to last or vice versa) so long as the output follows the same convention. The output must use the same structure and ordering convention as the input but with the bits rearranged to be up the left-side then back down the right-side in the manner described above.

Please state your bit-wise and byte-wise ordering as well as your i/o structure.

Scoring and winning criterion

Standard code-golf rules apply. Shortest code in bytes wins.

Test cases

As lists of bytes ordered least-significant bit to most-significant bit and first byte to last byte in the list.

[85] -> [15]
[85, 85] -> [255, 0]
[85, 85, 85] -> [255, 15, 0]
[85, 85, 85, 85] -> [255, 255, 0, 0]
[85, 85, 85, 85, 85] -> [255, 255, 15, 0, 0]
[85, 85, 85, 85, 85, 85] -> [255, 255, 255, 0, 0, 0]
[85, 85, 85, 85, 85, 85, 85] -> [255, 255, 255, 15, 0, 0, 0]
[85, 85, 85, 85, 85, 85, 85, 85] -> [255, 255, 255, 255, 0, 0, 0, 0]
[170] -> [240]
[170, 170] -> [0, 255]
[170, 170, 170] -> [0, 240, 255]
[170, 170, 170, 170] -> [0, 0, 255, 255]
[170, 170, 170, 170, 170] -> [0, 0, 240, 255, 255]
[170, 170, 170, 170, 170, 170] -> [0, 0, 0, 255, 255, 255]
[170, 170, 170, 170, 170, 170, 170] -> [0, 0, 0, 240, 255, 255, 255]
[170, 170, 170, 170, 170, 170, 170, 170] -> [0, 0, 0, 0, 255, 255, 255, 255]
[208] -> [28]
[96] -> [40]
[155, 36] -> [37, 210]
[232, 33] -> [24, 114]
[174, 18, 247] -> [66, 191, 248]
[130, 143, 125] -> [48, 111, 157]
[76, 181, 117, 107] -> [122, 159, 46, 67]
[158, 238, 106, 124] -> [166, 232, 230, 223]
[233, 87, 232, 152, 182] -> [249, 72, 182, 117, 120]
[142, 61, 195, 199, 218] -> [114, 185, 220, 153, 214]
[107, 131, 170, 25, 103, 171] -> [25, 80, 27, 175, 244, 233]
[71, 41, 113, 118, 202, 26] -> [27, 237, 72, 220, 42, 134]
[30, 226, 236, 110, 111, 211, 202] -> [134, 170, 219, 216, 233, 126, 203]
[162, 53, 89, 29, 128, 172, 134] -> [112, 125, 32, 146, 23, 68, 178]
[112, 71, 252, 192, 100, 176, 108, 71] -> [188, 142, 74, 186, 104, 35, 113, 40]
[111, 58, 224, 222, 231, 246, 214, 200] -> [75, 232, 235, 142, 149, 187, 61, 238]

Same test cases in hex

These may look odd, but remember they are byte-wise from beginning to end, and bit-wise from least-significant to most-significant bit (i.e. in opposite directions).

55 -> 0F
55 55 -> FF 00
55 55 55 -> FF 0F 00
55 55 55 55 -> FF FF 00 00
55 55 55 55 55 -> FF FF 0F 00 00
55 55 55 55 55 55 -> FF FF FF 00 00 00
55 55 55 55 55 55 55 -> FF FF FF 0F 00 00 00
55 55 55 55 55 55 55 55 -> FF FF FF FF 00 00 00 00
AA -> F0
AA AA -> 00 FF
AA AA AA -> 00 F0 FF
AA AA AA AA -> 00 00 FF FF
AA AA AA AA AA -> 00 00 F0 FF FF
AA AA AA AA AA AA -> 00 00 00 FF FF FF
AA AA AA AA AA AA AA -> 00 00 00 F0 FF FF FF
AA AA AA AA AA AA AA AA -> 00 00 00 00 FF FF FF FF
D0 -> 1C
60 -> 28
9B 24 -> 25 D2
E8 21 -> 18 72
AE 12 F7 -> 42 BF F8
82 8F 7D -> 30 6F 9D
4C B5 75 6B -> 7A 9F 2E 43
9E EE 6A 7C -> A6 E8 E6 DF
E9 57 E8 98 B6 -> F9 48 B6 75 78
8E 3D C3 C7 DA -> 72 B9 DC 99 D6
6B 83 AA 19 67 AB -> 19 50 1B AF F4 E9
47 29 71 76 CA 1A -> 1B ED 48 DC 2A 86
1E E2 EC 6E 6F D3 CA -> 86 AA DB D8 E9 7E CB
A2 35 59 1D 80 AC 86 -> 70 7D 20 92 17 44 B2
70 47 FC C0 64 B0 6C 47 -> BC 8E 4A BA 68 23 71 28
6F 3A E0 DE E7 F6 D6 C8 -> 4B E8 EB 8E 95 BB 3D EE

Reference implementation in Python.

Answer 1

x86-64 machine code function, 22 bytes

Callable with the Windows x64 calling convention: bit length in ECX, bit-pattern in RDX (first = least significant bit aka right-most). Returns in the low ECX bits of RAX.

NASM listing with machine code and the source it was assembled from:

 5                         bit_even_reverseodd:
 6 00000000 D1E9               shr  ecx, 1
 7 00000002 51                 push rcx                    ; save n/2 for later
 8                         .loop:               ; do {
 9 00000003 48D1EA             shr  rdx, 1                 ; shift low bit into CF (carry flag)
10 00000006 49D1D8             rcr  r8, 1          ; rotate even bits into the top of R8
11 00000009 48D1EA             shr  rdx, 1
12 0000000C 11C0               adc  eax, eax       ; odd bits into the bottom of RAX (reversing).  Same as rcl but faster
13 0000000E E2F3               loop .loop       ; }while(--rcx);
14                         
15                             ; return in EDX:EAX?  Nope, that has a gap for bit lengths less than 64, as well as hard to justify
16 00000010 59                 pop  rcx
17 00000011 4C0FA5C0           shld rax, r8, cl    ; shift even bits into the bottom
18 00000015 C3                 ret

Explanation:

Loop N/2 iterations, separating the odd and even bits into different registers, 2 input bits per iteration. (Into the carry flag then rotate-through carry back out).

Shifting into the top and bottom of 64-bit registers sets us up for a shld double precision shift that shifts in bits from another register instead of zeros.

The return value is the low ECX bits of RAX. It gets there by being shifted one bit at a time for the first half, then the 2nd half all at once. Bits above that bit position may be non-zero, depending on the initial value of RAX. These bits are not part of the return value.

If you think this is too much of a stretch of the rules, it costs 2 bytes for an xor eax, eax before the loop. Or a BMI2 bzhi on the return value, using the BIT_LEN in a register. But presumably the caller in this question's example use-case wants to loop over the resulting bits, and they're in the right order for that. Real x86 calling conventions allow high garbage in return-value registers, the only differences here are that the width isn't a power of 2, and is runtime variable.

Try it online! - includes a test _start caller that hexdumps the selected number of bytes before / after calling the function. (Tweaked version of the SSSE3 qword->hex version on https://stackoverflow.com/questions/53823756/how-to-convert-a-binary-integer-number-to-a-hex-string)

The test caller only prints the selected number of bits in the return value. If it wanted to avoid leading zeroes, that would take the same effort as avoiding leading garbage.

Example output with input loaded from db 170, 170, 170, 170, 170, 170, 170, 170, and bit-length = 8 * 5

aaaaaaaaaa
fffff00000

i.e. the 64-bit return value was 0x000000fffff00000, or would be after clearing high bits outside the low 40. Bits in a register have no endianness. The caller can iterate them in low-to-high order by right shifting.

Since x86 is little-endian, if we stored that to memory the significant 00 bytes would be at the low 2 addresses, and the 0xf0 (240) byte would be the 3rd, followed by two 0xff bytes.

The test cases in the question use that little-endian byte-order to dump bytes separately, not printing as a single wide integer with high/late/most-significant bits left-most as per standard arabic-numeral ordering for the whole thing as one number.

It's easy to input that ordering with db 170, 170, ... (even with decimal chunks like the original form of the test cases), if you don't mind loading from memory, but less convenient to output. I didn't want to write a bigger loop, and hex is obviously the more useful way to look at bit-pattern manipulation like this.

---

The TL:DR of the bit manipulation is to pack and concatenate the even bits with the bit-reversed odd bits. For some multiple of 8 number of total bits.

If only AArch64 had x86's BMI2 pext, it could be very compact. If x86 had ARM/AArch64's rbit, that would be fun, but x86 takes a 10-byte mov reg, imm64 to create an 8-byte alternating-bits constant. (Unlike AArch64 which can do it in one 4-byte instruction with its repeating-bit-pattern immediates for logical instructions).

To do this efficiently on x86 you'd use pshufb as a nibble LUT to bit-reverse maybe after packing with BMI2 pext. Or maybe palignr and another pshufb with a shuffle control from a bit-length lookup table. (pext/pdep are very slow on AMD, but single-uop / 3-cycle latency on Intel)

Answer 2

05AB1E, 12 bytes

Port of the Python answers. -1 Thanks to Kevin Cruijssen. -2 Thanks to Grimmy.

₁sm+b¦2ι`R«C

Try it online!

Explanation

₁            Push 256.
 s           Swap to get another input.
  m          Push 256 ** (input).
   +         Add by the other input.
    b        Convert to base 2.
     ¦       Remove the first item of ^
      2ι     Uninterleave.
        `    Dump onto stack.
         R   Reverse second copy.
          «  Merge.
           C Convert from base 2.

Answer 3

APL (Dyalog Unicode), 22 bytes

{83⎕DR⍵[⍒-\⍳≢⍵]}11∘⎕DR

Try it online!

Another case of alternating sequence trick.

I/O format is signed 8-bit integers, and the byte order is reversed from the OP's (bit order within each byte is the same).

How it works

{83⎕DR⍵[⍒-\⍳≢⍵]}11∘⎕DR  ⍝ Input: a vector of signed bytes
                11∘⎕DR  ⍝ Reinterpret as boolean vector (8bit/byte)
{              }        ⍝ Pass into inline function
      ⍵[⍒-\⍳≢⍵]  ⍝ Use alternating sequence trick to rearrange bits
 83⎕DR           ⍝ Convert back to a vector of signed bytes

Answer 4

J, ^{40 34 31} 29 bytes

_8#.\[:(\:[:-/\#\.)@,(8$2)#:]

Try it online!

-3 bytes thanks to Bubbler's suggestion of applying the alternating sequence trick from APL

-2 bytes thanks to FrownyFrog

Takes input in little-endian format.

Answer 5

Python 3.8, 50 bytes

lambda n,x:int((t:=f"{x:0{n*8}b}")[::2]+t[::-2],2)

Try it online!

Format: visit from MSB to LSB. Input is number of bytes n and an integer x representing the boss's order.

Simply converts x to a binary string t of length 8*n, then perform the following string slicing:

t[::2]+t[::-2]

which takes all the even indexed bits, then takes all the odd indexed bits in reverse order.

Answer 6

K (oK), 46 bytes

{|t/'0N 8#{(*x),|x@1}|:+:0N 2#,/(|(t:8#2)\)'x}

Try it online!

A naive solution. I'll try to improve it later.

Answer 7

Motorola M68HC11 machine code function, 96 bytes

Hexdump:

300808E6003A17343436860418306400
18660264001869014A26F3095A270C17
18A800850126E3325D26DC33C5012716
86041866011866024A26F73C543A18A6
02A701383131E60054173A59C4013C18
383A33E701083318E70018094A26F339

Takes input as a length-prefixed byte array on the stack and returns as a length-prefixed byte array on the stack.

If you run this on an emulator, you may get "uninitialized memory" warnings at SUB+0x10 and SUB+0x15; these can be ignored.

ASM source:

SUB
    TSX
    INX
    INX
    LDAB 0,X
    ABX
    TBA

TRANSFORM_LOOP
    DES
    DES

    PSHA
TRANSFORM_BYTE_PAIR_LOOP
    LDAA    #4
    TSY
TRANSFORM_BYTE_LOOP
    LSR 0,X
    ROR 2,Y
    LSR 0,X
    ROL 1,Y
    DECA
    BNE TRANSFORM_BYTE_LOOP

    DEX

    DECB
    BEQ TRANSFORM_DONE
    TBA
    EORA    0,Y
    BITA    #01
    BNE TRANSFORM_BYTE_PAIR_LOOP * ODD
    PULA     * EVEN
    TSTB
    BNE TRANSFORM_LOOP
TRANSFORM_DONE
    * Now, size, array is at 0,X and output(ish) is at 0,Y
    PULB
    BITB    #01
    BEQ BYTES_READY
    LDAA    #4
FIX_MIDDLE_BYTE_LOOP
    ROR 1,Y
    ROR 2,Y
    DECA
    BNE FIX_MIDDLE_BYTE_LOOP

    PSHX
    LSRB * B /= 2
    ABX
    LDAA    2,Y
    STAA    1,X
* Now the middle byte is dealt with for odd-sized arrays
    PULX
    INS
    INS

BYTES_READY
    LDAB 0,X
    LSRB
    TBA
    ABX  * 1.X is after the middle
    PSHX
    PULY * 0,Y is before the middle
    ROLB
    ANDB #01
    ABX
    
MOVE_BYTES_LOOP
    PULB
    STAB 1,X
    INX
    PULB
    STAB 0,Y
    DEY
    DECA
    BNE MOVE_BYTES_LOOP

    RTS

Answer 8

Charcoal, 37 bytes

≔⪪⭆⮌Ａ◧⍘鲦⁸¦²θＩＥ⪪⁺⮌ＥθΣ§ι¹ＥθΣ§ι⁰¦⁸↨²⮌ι

Try it online! Link is to verbose version of code. Explanation:

≔⪪⭆⮌Ａ◧⍘鲦⁸¦²θ

Take the input array, reverse it, convert each byte to binary padded to 8 bytes, concatenate the result, then split the bits into a list of pairs.

ＩＥ⪪⁺⮌ＥθΣ§ι¹ＥθΣ§ι⁰¦⁸↨²⮌ι

Take the second of each pair of bits, reverse the list, append the first of each pair of bits, split back into bytes, reverse each byte, convert each byte back from binary, convert to decimal.