Thread: Segments of consecutive equal bits

  1. #1
    Registered User
    Join Date
    Oct 2020
    Posts
    69

    Segments of consecutive equal bits

    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)

  2. #2
    Registered User
    Join Date
    Dec 2017
    Posts
    1,127
    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;
    }
    Last edited by john.c; 11-17-2020 at 04:15 PM.
    The best argument against democracy is a five minute conversation with the average voter. - Churchill

  3. #3
    Registered User
    Join Date
    Feb 2019
    Posts
    866
    Quote Originally Posted by john.c View Post
    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.

  4. #4
    Registered User
    Join Date
    Oct 2020
    Posts
    69
    Thank you!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Changing particular bits and detecting toggled bits
    By Nordomus in forum C++ Programming
    Replies: 11
    Last Post: 04-13-2018, 12:07 PM
  2. byte is equal 8 bits???
    By Micko in forum C Programming
    Replies: 3
    Last Post: 10-15-2004, 10:12 AM
  3. copy some bits into a 8 bits binary number
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 05-29-2002, 10:54 AM
  4. segments
    By stupid_mutt in forum C Programming
    Replies: 1
    Last Post: 10-03-2001, 01:40 AM
  5. segments
    By stupid_mutt in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 10-02-2001, 01:28 PM

Tags for this Thread