Finding the Maximum Number of Consecutive Set Bits in a Byte Array

Overview :

Finding the Maximum Number of Consecutive Set Bits in a Byte Array

This blog post will delve into a C program designed to find the maximum number of consecutive set bits (bits with a value of 1) within an array of bytes.

Understanding the Code : 

#include "stdio.h"
#include "stdint.h"

uint32_t findMaxNumberOfSetBits(uint8_t *arr, size_t size) 
{
    uint32_t maxSetBitsCount = 0;
    uint32_t currentSetBitsCount = 0;

    for (size_t i = 0; i < size; ++i)
    {
        uint8_t byte = arr[i];

        while (byte) 
        {
            if (byte & 1)
            {
                ++currentSetBitsCount;
            } 
            else 
            {
                maxSetBitsCount = (currentSetBitsCount > maxSetBitsCount) ? currentSetBitsCount : maxSetBitsCount;
                currentSetBitsCount = 0; 
            }
            byte >>= 1;
        }

        // Check for consecutive 1s at the end of the byte
        maxSetBitsCount = (currentSetBitsCount > maxSetBitsCount) ? currentSetBitsCount : maxSetBitsCount;
        currentSetBitsCount = 0; 
    }

    return maxSetBitsCount;
}

int main() 
{
    uint8_t bytesStream[] = {0x12, 0x34, 0x56, 0x78}; 
    printf("Combined bytes: 0x%04x\n", *(uint32_t*)&bytesStream[0]); 
    printf("Max consecutive set bits: %d\n", findMaxNumberOfSetBits(bytesStream, sizeof(bytesStream)));

    return 0;
}

Code : 

• #include "stdint.h": This line includes the standard input/output library, which provides functions like printf for printing output to the console.
• #include "stdio.h" : This line includes the standard integer types library, which defines fixed-width integer types such as uint8_t (unsigned 8-bit integer) and uint32_t (unsigned 32-bit integer). These types ensure consistent data sizes across different platforms.

2. Function Declaration:

• uint32_t findMaxNumberOfSetBits(uint8_t *arr, size_t size): This declares a function named findMaxNumberOfSetBits.
• uint32_t: Specifies that the function will return an unsigned 32-bit integer value (the maximum number of consecutive set bits).
• uint8_t *arr: This is a pointer to an array of unsigned 8-bit integers (bytes).
• size_t size: This represents the size of the input byte array.

3. Function Implementation:

• uint32_t maxSetBitsCount = 0 : Initializes a variable to store the maximum number of consecutive set bits found so far.
• uint32_t currentSetBitsCount = 0 : Initializes a variable to track the current count of consecutive set bits within a single byte.
• for (size_t i = 0; i < size; ++i) { ... }: This loop iterates through each byte in the array.
• uint8_t byte = arr[i] : Retrieves the current byte from the array.
• while (byte) { ... } : This inner loop iterates through each bit of the current byte.
• if (byte & 1) : Checks if the least significant bit (LSB) of the current byte is set (1).
  ++currentSetBitsCount : If the LSB is set, increments the currentSetBitsCount.
• else : If the LSB is not set:

maxSetBitsCount = (currentSetBitsCount > maxSetBitsCount) ? currentSetBitsCount : maxSetBitsCount : Updates maxSetBitsCount with the maximum value between the current currentSetBitsCount and the previous maxSetBitsCount.

• currentSetBitsCount = 0 : Resets currentSetBitsCount as the sequence of consecutive set bits has been interrupted.
• byte >>= 1 : Right-shifts the byte by one position, effectively moving all bits one position to the right and discarding the LSB.
• maxSetBitsCount = (currentSetBitsCount > maxSetBitsCount) ? currentSetBitsCount : maxSetBitsCount : This handles the case where the last bits of a byte are consecutive 1s.
• currentSetBitsCount = 0 : Resets currentSetBitsCount for the next byte.
• return maxSetBitsCount : Returns the maximum number of consecutive set bits found in the array.

4. Main Function:

• uint8_t bytesStream[] = {0x12, 0x34, 0x56, 0x78} : Declares and initializes an array of bytes with sample values.

• printf("Combined bytes: 0x%04x\n", *(uint32_t*)&bytesStream[0]) : Prints the combined bytes as a 32-bit hexadecimal value (note that this line might not be relevant to the core logic of finding consecutive set bits).
• printf("Max consecutive set bits: %d\n", findMaxNumberOfSetBits(bytesStream, sizeof(bytesStream))) : Calls the findMaxNumberOfSetBits function with the array and its size as arguments and prints the result.

5 . Key Points:

The code effectively iterates through each byte and bit within the array to determine the maximum number of consecutive set bits.
The use of bitwise operators (& for bitwise AND and >>= for right shift) is crucial for efficiently manipulating individual bits.
The code demonstrates a clear and concise approach to solving this specific problem.

As per byte stream max sets continious bit set is 4.