bitwise operations in recursive function using C

Question

So I'm pretty new to working with C and I'm taking an online course that provides me with exercises to practice with.

What I'm trying to do is take a long data type and return an int value according to it's binary representation. The rule is if the 2 most-right bits are different from zero (01, 10, 11) count this as one and move to the next 2 bits and so on. For example:

00000000-00000000-00000000-00000001- should return 1.

00000000-00000011-00000001-00000010- should return 3.

00001000-11000011-00001001-00110010- should return 7.

int abcLength(long abcCode) {
  if(abcCode&3) {   /*** <--- Try to do this using only bitwise and logical operators !  ***/
    return 0;
  }
  return 1 + abcLength((((unsigned)abcCode>>2)); /*** <--- Try to do this using only bitwise and logical operators !  ***/
}

The problem is I can't figure out how to deal with cases that have 00 in the middle of the binary string. They told me to use only one if statement but as it is now it would count 00 when it shouldn't.

Any ideas on how to make this work?

Answer 1

There are two problems in your code:

• you return 0 immediately when one of the 2 low bits is set. This is incorrect. You should return 0 if the argument is 0 and add one the recursion value if the 2 low bits are non 0.
• you cast abcCode as (unsigned) when recursing, which may mask off the most significant bits. You should cast as (unsigned long) instead.

Here is a modified version:

int abcLength(long abcCode) {
    int n = 0;
    if (abcCode == 0)
        return 0;
    if (abcCode & 3)
        n++;
    return n + abcLength((unsigned long)abcCode >> 2);
}

This can be obfuscated as:

int abcLength(long code) {
    return code ? !!(code & 3) + abcLength((unsigned long)code >> 2) : 0;
}

Here is a solution with a loop:

• combine the bits in even and odd positions
• iterate to count the number of bytes with a low bit set

Simple implementation:

int abcLength(long x) {
    unsigned long code = x;
    int n;
    for (n = 0; code != 0; code >>= 2) {
        if (code & 3)
            n++;
    }
    return n;
}

And here is a potentially faster one without any loops:

int abcLength(long code) {
    code = (code | (code >> 1)) & 0x5555555555555555;
    code = (code + (code >> 2)) & 0x3333333333333333;
    code = (code + (code >> 4)) & 0x0F0F0F0F0F0F0F0F;
    return (code * 0x101010101010101) >> 56;
}