// Arup Guha
// 12/5/2023
// Code for 2023 COP 3502 Final Exam Part B Question 4 - Both Versions

#include <stdio.h>

// Returns a times b.
int f(int a, int b) {

    // Base case.
    if (b == 0) return 0;

    // We add a if this bit is on in b.
    int res = a * (b & 1);

    // If we left shift the recursive call, then if a bit in b is on, say bit 3, then we'll add 8a
    // So basically this will return a times b by spitting up the contribution of each bit in b times a.
    return res + (f(a, b>>1) << 1);
}

// Returns a*numonebits(b)
int g(int a, int b) {

    // Base case.
    if (b == 0) return 0;

    // We add a if a bit in b is on.
    int res = a * (b & 1);

    // Do the rest of the bits in b and add to this contribution.
    return res + g(a, b>>1) ;
}

// Test.
int main() {

    printf("%d\n", f(13,12));
    printf("%d\n", g(12,123));

    return 0;
}