Thread: Requesting assistance regarding bit(wise) example

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

    Requesting assistance regarding bit(wise) example

    Hi all, I have just started on the low level programming chapter in KNKING C programming book, and am confused by this exercise. This is what it does.

    (a) Write the following function
    intcount_ones(unsignedchar ch);
    count_ones should return the number of 1 bits in ch.

    This is what I came up with (and apparently is correct as i cross checked with online answers)
    Code:
    int count_ones_v1(unsigned char ch)
    {
        short count;
        while (ch > 0) {
            if (ch & 1) {
                count++;
            }
            ch >>= 1;
        }
    }

    From my understanding, what my code does is it uses & to check if the right most bit of ch contains a 1. If it does, then it adds to the "count" variable. It then uses >> to move ch to the right, and repeats until ch ==0 and the loop is broken.

    The 2nd part of the exercise goes "Write the function without using a loop" and this is what the online answer has shown.

    Code:
    int count_ones(unsigned char ch)
    Code:
    {
        if (ch == 0)
            return 0;
        return count_ones(ch & ch - 1) + 1;
    }
    


    I understand that this function is recursive, but I dont understand how (ch & ch - 1) works, and why afterwards there is an additonal "+1". Isnt "ch-1" basically just subtracting a decimal value of 1 from ch? Would appreciate any help and guidance.

    Also is it expected to be able to convert decimal numbers to hexadecimal form with ease? Trying to convert hex values to decimal makes me feel dumb haha. Thank you kind sirs.

  2. #2
    Registered User
    Join Date
    May 2012
    Posts
    505
    You need to set count to zero before using it to increment.

    The & operator performs a bitwise Boolean AND operation. Here it is masking off the lowest bit.

    You can always turn a loop into recursion. That's nothing much to do with bitwise operations.
    The manipulation is "tricky". I can't follow it myself, but if you trace out the Boolean logic you'll be able to see if it is right or not.
    Last edited by Malcolm McLean; 11-04-2020 at 07:43 AM.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    https://github.com/MalcolmMcLean


  3. #3
    Registered User
    Join Date
    May 2012
    Posts
    505
    Quote Originally Posted by Malcolm McLean View Post
    You need to set count to zero before using it to increment.

    The & operator performs a bitwise Boolean AND operation. Here it is masking off the lowest bit.

    You can always turn a loop into recursion. That's nothing much to do with bitwise operations.
    The manipulation is "tricky". I can't follow it myself, but if you trace out the Boolean logic you'll be able to see if it is right or not.
    I've worked it out now. It is right.


    By subtracting one, if the number is odd, you zero out the last bit. If it is even, you zero out the fist set bit, and set all the following bits to one. But they are already zeroed by previous calls.

    However it's best to work through a few examples yourself.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    https://github.com/MalcolmMcLean


  4. #4
    Registered User
    Join Date
    Oct 2020
    Posts
    18
    Quote Originally Posted by Malcolm McLean View Post
    I've worked it out now. It is right.


    By subtracting one, if the number is odd, you zero out the last bit. If it is even, you zero out the fist set bit, and set all the following bits to one. But they are already zeroed by previous calls.

    However it's best to work through a few examples yourself.
    Hi sir, thank you so much for your help. Ive managed to figure it out how it works. Bless you

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Requesting feedback on my code
    By Richardcavell in forum C Programming
    Replies: 2
    Last Post: 02-06-2017, 02:27 AM
  2. Bit Wise Functions
    By Prediluted in forum C Programming
    Replies: 4
    Last Post: 06-15-2011, 01:03 AM
  3. Requesting Some Guidance
    By London Fog in forum C Programming
    Replies: 4
    Last Post: 05-31-2009, 11:25 PM
  4. Requesting a challenge
    By RealityFusion in forum C++ Programming
    Replies: 8
    Last Post: 08-18-2003, 08:24 PM

Tags for this Thread