Introduction

Notes during problem solving.

Problem Description

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.

Code

void memoize_bit_count(int *arr, int arr_length);
int *countBits(int n, int *returnSize);

int *countBits(int n, int *returnSize) {
    int arr_length = n + 1;
    *returnSize = arr_length;

    int *bit_count = (int *) malloc(sizeof(int) * arr_length);
    bit_count = (int *) memset((void *) bit_count, 0, sizeof(int) * arr_length);

    memoize_bit_count(bit_count, arr_length);

    return bit_count;
}

void memoize_bit_count(int *arr, int arr_length) {
    for (int i = 1; i < arr_length; i++) {
        arr[i] = (i & 1) + arr[i >> 1];
    }
}

Solution Explanation

After allocating memory to bit_count, it sets all values to 0 using memset().
Then, using memoization, the bit count is incremented.
The memoize_bit_count() function adds & 1 (i.e. x & 0x001) to a pre-obtained value.
For example, 0x101 (i.e. 5) is calculated by (0x101 & 0x001) + (0x010).
0x010 was already calculated using the following equation, (0x010 & 0x001) + (0x001). Which is 0 + 1.
Therefore, arr[0x101] is 2.

Code Explanation

  • Syntax
    While reading the C++ book, “C++ from the GROUND UP”, I found out why * were written before the variable not the type.
    int* x, y, this code may seem like a declaration of two int* types. However, this declaration creates an int* type x and an int type y.
    Due to these ambiguity issues, * derefences are written before the variable.

    I thought a lot about whether sizeof(int) * arr_length or arr_length * sizeof(int) would be better.
    The natural one would be the latter one because it represents the main unit, then the multiplier of the unit.
    However, in the perspective of coding, putting the former first would make it slightly simpler.
    For example, in some few situations, the code may require just the sizeof() operation.
    Also, the variable’s value is determined before the statement (so debugging it would happen before the statement) but the sizeof() would be requeired to be monitored on the statement.
    That is why putting the more critical one forward (두괄식) one can help the debugging process.
  • Functions
    • countBits: calls the process. Initializes the necessary memory and calls functions. Returns the array of bit counts.
    • memoize_bit_count: counts the bits in the numbers, 0 ~ n. Uses memoization, bottom-up method.
  • Variables
    • n: given max element of the array.
    • arr_length: length of the bit_count array.
    • returnSize: “out” variable that holds the length of the array. Used in the caller of countBits.
    • bit_count: array of bit counts from 0 ~ n.

Conclusion

Third entry of my [PS] series.
The logic was quite simple. When I got the hang of it, the rest came easily.
However, there was a problem with initializing bit_count. Other codes used calloc to allocate and intialize at once.
I wanted to separate these steps so I used malloc and memset().
In the process of calling memset(), I passed the size_t n parameter with the value arr_length.
This didn’t work because the parameter specified the n bytes of the memory area.
An int is 4 bytes so it requires the n value to be multiplied by 4. I verified inserting 4 instead of sizeof(int) works.