Detecting bit patterns with series of zeros followed by ones

Author:Wojciech Muła
Added on:2016-10-16
Keywords: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 applied 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.