# Detecting bit patterns with series of zeros followed by ones

Author: Wojciech Muła 2016-10-16 bit twiddling

# Problem

We want to detect if a pattern is a sequence of zeros followed by ones. Table below lists all 8-bit patterns having this form.

bin hex
1000_0000 80
1100_0000 c0
1110_0000 e0
1111_0000 f0
1111_1000 f8
1111_1100 fc
1111_1110 fe
1111_1111 ff

# Solution

Negative number, i.e. -x = ~x + 1, from the searched pattern forms a bit pattern having just a bit set on position of the first one in string. The negation of any other pattern has got more ones.

Lets look at the following example:

```-x = -(1111_1100)
= ~(1111_1100) + 1
=   0000_0011  + 1
=   0000_0100
```

For all searched patterns bit-and of a pattern with its negation is equal to the negation. Unfortunately this rule applies also to 0, thus an additional test is required.

Here is a sample implementation for 16-bit numbers.

```int is_pattern(uint16_t x) {

const uint16_t n = -x;

return (x > 0) && n == (n & x);
}
```

All source codes are available at github.