How SWAR Finds Zero Bytes in an Integer

SWAR (SIMD Within A Register) is a technique that processes multiple data lanes in parallel using standard general-purpose registers and integer operations. One of the most famous SWAR algorithms detects whether any byte in a 32-bit (or 64-bit) integer contains a zero byte (0x00) using the expression ((v - 0x01010101) & ~v & 0x80808080). This article explains the underlying binary mechanics of how subtraction underflow and bitwise logic isolate null bytes without branching or loops.

The Objective

A 32-bit unsigned integer \(v\) consists of four 8-bit bytes:

\[v = [B_3, B_2, B_1, B_0]\]

The goal is to determine if any \(B_i == 0x00\) in parallel. If any byte is zero, the algorithm sets the most significant bit (MSB / bit 7) of that byte to 1, leaving all other bits 0.

Step 1: Subtraction (v - 0x01010101)

Subtracting 0x01 from every byte triggers an underflow/borrow mechanism across each byte lane:

1. If a byte is 0x00: Subtracting 1 results in 0xFF (11111111 in binary). The high bit (bit 7) becomes 1 due to underflow.
2. If a byte is in the range 0x01 to 0x80: Subtracting 1 results in 0x00 to 0x7F. The high bit (bit 7) is 0.
3. If a byte is in the range 0x81 to 0xFF: Subtracting 1 results in 0x80 to 0xFE. The high bit (bit 7) remains 1.

At this stage, the MSB is 1 for zero bytes, but it is also 1 for bytes originally greater than or equal to 0x81.

Step 2: Inversion and Intersection & ~v

To eliminate the false positives from bytes in the 0x81..0xFF range, the algorithm uses the bitwise complement ~v:

• Bytes originally in the range 0x81..0xFF have their MSB set to 1. Therefore, ~v has an MSB of 0 for these bytes.
• A byte originally equal to 0x00 has an MSB of 0. Therefore, ~v has an MSB of 1.

When the two terms are combined via bitwise AND (v - 0x01010101) & ~v:

Only bytes that originally were 0x00 satisfy both conditions: 1. Underflowed upon subtracting 1 (producing a 1 at the MSB). 2. Originally had a 0 at the MSB (producing a 1 after ~v).

Step 3: Masking with & 0x80808080

The intermediate operations may leave lower bits (bits 0 through 6) set to arbitrary values. Applying & 0x80808080 clears all bits except the MSB of each byte lane:

• If the original integer \(v\) contains at least one zero byte, the resulting value will be non-zero (specifically, having 0x80 in the corresponding byte lane).
• If the original integer contains no zero bytes, the entire expression evaluates to 0x00000000.

Summary

The expression functions through three logical stages: 1. (v - 0x01010101): Forces zero bytes to borrow and set their MSB to 1. 2. & ~v: Masks out bytes that already had their MSB set to 1 prior to subtraction. 3. & 0x80808080: Isolates the MSBs, producing a deterministic non-zero indicator if and only if a null byte was present.