x86 32-bit machine code, 13 bytes
Input: uint32_t *esi, size_t ecx
returns: EDX = len - 2*even
= 0 for balanced, non-zero for unbalanced.
This conveniently works even for len=0 = balanced. As part of this asm custom calling convention / ABI, my boolean data type is 0 / non-zero, rather than the 0 / 1 that C ABIs use.
This avoids needing to actually compare, just decrement twice inside the loop, starting with the list length.
1 boe:
2 00000000 89CA mov edx, ecx ; balance = len
3 00000002 E309 jecxz .end
4 .loop: ; do {
5 00000004 AD lodsd ; eax = *p++
6 00000005 A801 test al, 1
7 00000007 7502 jnz .odd
8 00000009 4A dec edx
9 0000000A 4A dec edx ; more compact than sub edx,2 in 32-bit code
10 .odd:
11 0000000B E2F7 loop .loop ; }while(--ecx);
12 .end:
13 ; xchg eax, edx ; custom calling convention: return in EDX instead of spending a byte on xchg
14 0000000D C3 ret
Try it online! (with a _start
test case that exits with the return value as exit status)
An alternate version that calculates in EAX to return in the standard calling convention's register is 14 bytes. It uses test byte [edi], 1
(1 byte longer than test al,1
) and increments the pointer with scasd
(without caring about the FLAGS result of the eax - [edi]
it also does). See the TIO link.
Uncommenting the xchg eax, edx
at the bottom of the 13-byte version would do the same thing, and that version's loop is more efficient.
For 8-bit integer input, use lodsb
instead. Unfortunately, we can't use and al, 1
/ add dl, al
or similar (without branching). That would only work for array sizes up to 255. and eax,1
is 3 bytes.
Also, masking and adding only does one increment. lea edx, [edx + eax*2]
could work but that's also 3 bytes. Branching on the low bit with test/jnz seems to be best for size, although it sucks for performance with branch mispredicts.
Of course if we wanted to go fast, we'd load 16 bytes at once with movdqa
, isolate the low bits with pand
, and sum with paddd
. Then hsum at the end. Or hsum with psadbw
against a zeroed register, then paddq
. SIMD is of course especially good for 8-bit elements, 16 per vector instead of 4, with an outer loop to avoid overflowing 8-bit counters. e.g. this AVX2 SO answer.
Something like this could maybe be smallish code-size if we limited it to a fixed-size 16-byte input array, or maybe 8-byte in MMX registers. Unfortunately we rarely get to play with SIMD in code golf because the instructions are larger and inputs can be odd lengths requiring cleanup loops.