Segments of consecutive equal bits

**rmmstn** · 11-17-2020

I'm new to C and still trying to grasp bitwise operators, I'm currently stuck on this problem:

Write a function that given an unsigned n returns the number of segments of consecutive equal bits in the binary representation of n.
Example: 000100 has three segments: 000, 1, 00.

Code:

#include <stdio.h>
 unsigned countSegments(unsigned n){
    unsigned counter = 0;
    unsigned size = sizeof(n)*8;
    for(int i = 0; i < size; i++){
       unsigned mask_1 = n & (1<<i);
        unsigned mask_2 = n & (1<<i+1); //if two consecutive bits are different => a segment
        if((mask_1<<1) != (mask_2)) // if we left shift the first mask by 1 it should be equal to the 2nd mask => 1 segment else => not a segment
            counter ++;


    }
    return counter;
 }
 int main(){
    unsigned num = 13;
    printf("The number %d has %d segments of consecutive equal bits", num, countSegments(num));
    return 0;


 }

I know my approach probably isn't the best but here it is: I put two masks in the loop, the first starting at 0 and the other at 1 (so basically the second one will always be one value ahead from the first). Now I figured that if 2 consecutive bits are different, I have a segment so the counter is incremented, but since I can't compare the values bit by bit, I thought if I leftshift the first mask with 1, I should get the value of the 2nd mask so if they're different the counter increases. The program works fine for some values (eg: 0-10), but not for others (eg: 11, 13, 0xAB). Could you help me a bit? (no pun intended)

**john.c** · 11-17-2020

A couple of problems.

You should only loop up to i < size - 1 since otherwise 1u<<(i+1) will create 0u on the last iteration.

You should also start counter at 1, since there will always be at least 1 segment.

Code:

#include <stdio.h>
#include <limits.h>
 
int countSegments(unsigned n)
{
    const unsigned size = sizeof(n) * CHAR_BIT;
    int counter = 1;
    for (unsigned i = 0; i < size - 1; i++)
    {
        unsigned mask1 = n & (1u << i);
        unsigned mask2 = n & (1u << (i + 1));
        if ((mask1 << 1) != mask2)
            ++counter;
    }
    return counter;
}
 
void bits(unsigned n)
{
    unsigned mask = 1u << (sizeof(n) * CHAR_BIT - 1);
    for ( ; mask; mask >>= 1) putchar('0' + !!(n & mask));
}
 
int main()
{
    unsigned nums[] = {
        0, // 0000
        1, // 0001
        2, // 0010
        3, // 0011
        4, // 0100
        5, // 0101
        0xFFFFFFFF,
        0x80000000,
        0xAB,   // 1010 1011             (8)
        0x68B9  // 0110 1000 1011 1001   (10)
    };
 
    for (unsigned i = 0; i < sizeof nums/sizeof *nums; ++i)
    {
        // Note that you should use %u to print an unsigned int.
        printf("%10u (0x%08X) ", nums[i], nums[i]);
        bits(nums[i]);
        printf(" : %2d\n", countSegments(nums[i]));
    }
 
    return 0;
}

**flp1969** · 11-17-2020

Originally Posted by john.c

The worst mistake is a lack of parens around the i+1 here: (1<<i+1)
Since + has higher precedence than <<, it should be n & (1u << (i + 1)).

Since + has higher precedence than <<, (1U << i + 1) is correct, no parentesis needed.

I could agree that writing (1U << (i + 1)) makes the expression clearer, but the previous isn't wrong.

**rmmstn** · 11-18-2020

Thank you!

Thread: Segments of consecutive equal bits

Thread Tools

Search Thread

Display

Segments of consecutive equal bits

Similar Threads

Changing particular bits and detecting toggled bits

byte is equal 8 bits???

copy some bits into a 8 bits binary number

segments

segments

Tags for this Thread