Bit delivery in Bin City

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.

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.

Scoring and winning criterion

Standard 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

• So the TL:DR here is to pack and concatenate the even bits, with bit-reversed odd bits. For some multiple of 8 number of total bits. If only AArch64 had x86's pext, or x86 had ARM's rbit, a machine-language answer could be very compact (and efficient without a SIMD lookup table for nibbles). – Peter Cordes Apr 16 '20 at 20:46
• @PeterCordes Yes indeed. :-) – Noodle9 Apr 16 '20 at 22:13

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)

• Great answer +1, and the unused bits can have anything in them since they're, er, not used! :-) And I'll post the test-cases in hex. – Noodle9 Apr 16 '20 at 22:55
• @Noodle9: Fun question, nice to have one that CPUs were made for, but which high-level languages often don't expose easily. (At least ISAs with a carry flag and rotate-through-carry or double-shift instructions, e.g. not MIPS.) – Peter Cordes Apr 16 '20 at 23:03
• Posted test cases in hex, probably not the exact format you'd like. Note that the structure is still as a list of bytes from beginning to end of list, lsb to msb within the bytes. – Noodle9 Apr 17 '20 at 15:01
• @Noodle9: Thanks. Yeah, sorting out the test-case byte-order vs. bit-order to make sure I didn't have a bug in combining the halves the wrong way took almost as long as writing the function. (Longer if you count writing the test harness, too). Eventually grokked that your test cases are N-bit integers in little-endian byte order, which is something totally familiar x86 asm hackers. (And that my hex print function was working the way I thought it did, after double-checking register values with GDB. Had to add code to discard the high garbage to stop confusing myself!) – Peter Cordes Apr 17 '20 at 15:51
• But when I can do so for no byte cost, I write a C prototype like int foo(int dummy, int dummy, unsigned long bit_pattern, unsigned bit_length); for x86-64 System V or whatever. – Peter Cordes Apr 18 '20 at 17:51

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.

• @KevinCruijssen Is there a shorthand for 2ι here? I feel like it's definitely golfable.. – user92069 Apr 16 '20 at 6:35
• Not that I'm aware of. I was actually about to post that exact same answer when you beat me to it. – Kevin Cruijssen Apr 16 '20 at 6:38
• I don't think this one works. Both python answers do multiple-of-8 padding (which requires the second input: the number of bytes) to the binary digits before rearranging the bits; this answer doesn't. – Bubbler Apr 16 '20 at 7:49
• @Bubbler Mine was a port of dingledooper's answer, forgive me as I also checked with the wrong test cases. – user92069 Apr 16 '20 at 9:00
• Your current approach with the absolute different of 8 only works for inputs of 1 byte.. Why not just take the length as additional input like the Python answer does. Then you can do bs8*jð0:2ιR«C for 14 bytes: try it online or verify all test cases. – Kevin Cruijssen Apr 16 '20 at 9:02

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


J, 403431 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. • _8(#.$$(\:-/$$#\.))&,(8$2)#:]. Which is really _8#.\[:(\:[:-/\#\.)@,(8\$2)#:] but obfuscated. – FrownyFrog Apr 22 '20 at 16:31
• Very nice, thank you! – Jonah Apr 23 '20 at 2:32

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.

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.

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

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


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.