Finding consecutive bit string of 1 or 0

by

The following is based on the concept that if you AND a bit sequence with a shifted version of itself, you’re effectively removing the trailing 1 from a row of consecutive 1’s. 

      11101111   (x)
    & 11011110   (x << 1)
    ----------
      11001110   (x & (x << 1)) 
        ^    ^
        |    |
   trailing 1 removed

Repeating this N times will reduce any sequence with N consecutive 1’s to 0x00.

So, to count the number of consecutive 1’s:

int count_consecutive_ones(int in) {
  int count = 0;
  while (in) {
    in = (in & (in << 1));
    count++;
  }
  return count;
}

To count the number of consecutive 0’s, simply invert and the same routine.

int count_consecutive_zeros(int in) {
  return count_consecutive_ones(~in);
}

Proof of concept: http://ideone.com/Z1l0D

int main(void) {
  printf("%d has %d consecutive 1's\n", 0, count_consecutive_ones(0));
  printf("%d has %d consecutive 0's\n", 0, count_consecutive_zeros(0));

  /* 00000000 11110000 00000000 00000000 -> If it is 0 then length will be 20 */
  printf("%x has %d consecutive 0's\n", 0x00F00000, count_consecutive_zeros(0x00F00000));

  /* 11111111 11110000 11110111 11111111 -> If it is 1 then length will be 12 */
  printf("%x has %d consecutive 1's\n", 0xFFF0F7FF, count_consecutive_ones(0xFFF0F7FF));
}

Output:

0 has 0 consecutive 1's
0 has 32 consecutive 0's
f00000 has 20 consecutive 0's
fff0f7ff has 12 consecutive 1's

More Related Contents:

  1. What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C?
  2. Efficient Algorithm for Bit Reversal (from MSB->LSB to LSB->MSB) in C
  3. Arithmetic bit-shift on a signed integer
  4. Are the shift operators () arithmetic or logical in C?
  5. How can I multiply and divide using only bit shifting and adding?
  6. What is Bit Masking?
  7. What is CHAR_BIT?
  8. Find most significant bit (left-most) that is set in a bit array
  9. Fast computing of log2 for 64-bit integers
  10. Extracting bits with a single multiplication
  11. Bitfield manipulation in C
  12. Fastest way to clamp a real (fixed/floating point) value?
  13. What’s bad about shifting a 32-bit variable 32 bits?
  14. Casting float to int (bitwise) in C
  15. What does the statement if (counter & (1
  16. Compute fast log base 2 ceiling
  17. warning: left shift count >= width of type
  18. set the m-bit to n-bit [closed]
  19. Bitshift and integer promotion?
  20. Bit twiddling: which bit is set?
  21. How to define and work with an array of bits in C?
  22. Implementing Logical Right Shift in C
  23. How do I get bit-by-bit data from an integer value in C?
  24. Algorithm to generate bit mask
  25. How does this bitwise operation check for a power of 2?
  26. Check if a number is non zero using bitwise operators in C
  27. How to replace bits in a bitfield without affecting other bits using C
  28. Decimal to Binary
  29. C Programming – XOR Bitwise Operation
  30. Order of fields when using a bit field in C

Leave a Comment