c++algorithmbinary

Find sum of bits of a char

I need a queue of size about 8 booleans. Every push should destroy an item from the tail. This can be achieved by a char in the resource limited application.

However I only care about the sum of those "flags", not their individual status. How can I find the sum of the set bits of an 8 bit char?

Solution

  • I come up with two methods.

    A method is using a varible to count the sum, whenever you push, you maintain the varible, the change of the varible depends on what you push and what will pop.

    Another method is an algorithm called "lowbit"

    int lowbit(int x) {
    return x & -x;
}

    it will return the last 1 int the binary representation of the x.

    So this can get the number of '1' in the binary representation of x.

    for example, code like this.

    int sum_of_1(int x) {
    int res = 0;
    while (x != 0) res++, x -= lowbit(x);
    return res;
}