Topics / Bit Manipulation / Q22
How do you detect if a value has a zero byte?
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
v - 0x01010101subtracts 1 from every byte. A byte that was0x00becomes0xFF(and borrows from the next byte up), so its high bit becomes 1.- Bytes that were
0x81–0xFFalso have the high bit set after subtracting.& ~vremoves those, because their original high bit was already 1. & 0x80808080keeps 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/memchruse this idea; Arm's optimized routines use NEON orUADD8/SELinstead.