</>EmbeddedInterview

How do you detect if a value has a zero byte?

HardBit Manipulation

Short answer: ((v - 0x01010101) & ~v & 0x80808080) != 0 tests all four bytes of a 32-bit word at once. It is the trick behind fast word-at-a-time strlen and memchr.

#include <stdint.h>
#define HAS_ZERO(v)  (((v) - 0x01010101u) & ~(v) & 0x80808080u)

How it works, byte by byte

  1. v - 0x01010101 subtracts 1 from every byte. A byte that was 0x00 becomes 0xFF (and borrows from the next byte up), so its high bit becomes 1.
  2. Bytes that were 0x81–0xFF also have the high bit set after subtracting. & ~v removes those, because their original high bit was already 1.
  3. & 0x80808080 keeps only the high bit of each byte.

If anything is left, at least one byte was zero.

Example

v               = 0x61 62 00 63
v - 0x01010101  = 0x60 60 FF 62   (the 00 byte became FF and borrowed from 0x62)
~v              = 0x9E 9D FF 9C
(v-..) & ~v     = 0x00 00 FF 00
& 0x80808080    = 0x00 00 80 00   -> non-zero, a zero byte exists

The borrow can corrupt bytes above the zero byte, which may produce a false high bit there. That is fine for "is there a zero?" but you must find the exact byte with a byte-by-byte check, or by using __builtin_ctz on a little-endian machine (lowest set marker = first zero byte in memory order).

Find a specific byte value c: XOR with a repeated pattern first: HAS_ZERO(v ^ (0x01010101u * c)).

Practical notes

  • Word-at-a-time reads must be aligned, or you can read past the end of a buffer into an unmapped page. Library implementations align the pointer first.
  • glibc and newlib strlen/memchr use this idea; Arm's optimized routines use NEON or UADD8/SEL instead.