Bdtjtk

i don't understand this code

void function(int a){

    if(a){

        function(a>>1);

        cout<<(a&1);

    }

}

can somebody explain this function to me step by step?

// Step 1: You call a function defined as `void function(int a)`

// which accepts one parameter of type int and returns a void.

void function(int a)

{

    // Step 2: This function checks if a is zero or some other value. 

    // If it is zero, nothing happens and the function returns.

    // If it is non-zero, we proceed inside the if block.

    if(a){

        // Step 3: we do two things here.

        // First we right-shift whatever value is stored in a.

        // Right-shifting means if we have e.g. a=8, which is 1000 in binary,

        // then rightshifting 8 would be 0100 or 4. Basically it is division by 2.

        // This continues until we have 0000.



        // Secondly, this function will call itself then. This is called recursion.

        // So the "void function(4)-> void function(2) -> void function(1)" calls will run.

        function(a>>1);



        // Here we will bitwise AND with 1.

        // So, 0001 & 0001 = 1

        // 0010 & 0001 = 0

        // 0100 & 0001 = 0

        // 1000 & 0001 = 0

        // And this is what you will see on the terminal as output: 1000

        // The 1 gets printed first, because the inner most call in the recursion

        // finishes first and the call stack unwraps back up.

        cout<<(a&1);

    }

}

Recursive function

void function(int a){

    if(a){                 // if a is not 0, continue calling recursively

        function(a>>1);    // right shift a one step i.e. divide by 2, then call ourselves

        cout<<(a&1);       // bitwise & with a i.e print if a is odd or even.

    }

}

Example

function(4);

a = 4, a>>1 == 2

function(2);

a = 2, a>>1 == 0

function(0); will end recursion

cout << (2&1) will print 0 since 0x10 & 0x01 == 0x00

cout << (4&1) will print 0 since 0x20 & 0x01 == 0x00

void function(int a)    // function declaration

{

    if(a)               // a != 0?

    {

        function(a>>1); // recursive call to function with a shifted right one bit

        cout<<(a&1);    // print out least significant bit of a

    }

}

This function prints out a binary representation of a number given, e. g. a initially 13:

f(13)            // 13 == 0b1101

{

    f(6)         // 0b1101 >> 1 == 0b0110

    {

        f(3)     // 0b0110 >> 1 == 0b0011

        {

            f(1) // etc

            {

                f(0)

                { }  // does nothing

                std::cout << (1 & 1); // 1, most significant bit of original 13

            }

            std::cout << (3 & 1);     // 1

        }

        std::cout << (6 & 1);         // 0

    }

    std::cout << (13 & 1);            // 1

}



1101 in total

Signature is dangerous, though; wheras it is implementation defined if the shift is logic (always 0 shifted in at the left) or arithmetic (shift in current sign bit again), usually (question is C, but applies for C++ as well) arithmetic shift is implemented for signed values.

So you would end up in an endless recursion if you pass a negative value to the function. Better:

void function(unsigned int a);

//            ^^^^^^^^

For unsigned values, logic and arithmetic shift are the same...

Side note: if you pass 0 initially to the function, you don't get any output at all (either variant).