Author: | Wojciech Muła |
---|---|

Added on: | 2016-10-16 |

Keywords: | bit twiddling |

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 |

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.