CODEWITHSUNDEEP
c++c
kryticrecte
kryticrecte

Reputation: 377

Determining number of set bits in a char

This program is supposed to determine how many units are stored in the value of the variable c_val, if each unit is stored as a set bit. My question is: why did the author write if (c % 2 == 1) count++; then shift c to the right with this statement c = c >> 1;?

#include <stdio.h>
#include <cstdlib>

int main(){
    unsigned char c_val;
    printf("char value = ");
    scanf("%c", &c_val);
    int count = 0;
    unsigned char c = c_val;
    while(c){
        if (c % 2 == 1) count++;
        c = c >> 1;
    }
    printf("%d bits are set", count);
    system("pause");
}

Upvotes: 3

Views: 3397

Answers (4)

kapilddit
kapilddit

Reputation: 1769

Other way to do the same:

#include <stdio.h>
#include <conio.h>

unsigned int f (unsigned int a , unsigned int b);

unsigned int f (unsigned int a , unsigned int b)
{
   return a ?   f ( (a&b) << 1, a ^b) : b;
}

int bitcount(int n) {
    int tot = 0;

    int i;
    for (i = 1; i <= n; i = i<<1)
        if (n & i)
            ++tot;

    return tot;
}

int bitcount_sparse_ones(int n) {
    int tot = 0;

    while (n) {
        ++tot;
        n &= n - 1;
    }

    return tot;
}

int main()
{

int a = 12;
int b = 18;

int c = f(a,b);
printf("Sum = %d\n", c);

int  CountA = bitcount(a);
int  CountB = bitcount(b);

int CntA = bitcount_sparse_ones(a);
int CntB = bitcount_sparse_ones(b);

printf("CountA = %d and CountB = %d\n", CountA, CountB);
printf("CntA = %d and CntB = %d\n", CntA, CntB);
getch();

return 0;

}

Upvotes: 0

Adam Mihalcin
Adam Mihalcin

Reputation: 14468

The data size of type char is always one byte - no exceptions. This code, however, calculates the popcount - that is, the number of 1 bits - in c_val.

We can translate the relevant code from

while (c) {
    if (c % 2 == 1) count++;
    c = c >> 1;
}

to

while (c != 0) {
    if (c & 0x1 == 1) count++; /* if the rightmost bit of c is 1, then count++ */
    c = c / 2;
}

The last change I made works because right-shifting an unsigned integral data type (in this case, unsigned char) is equivalent to dividing by 2, with round-toward-zero semantics.

We can think of c as a conveyor belt of bits - zero bits come in from the left, and one bit falls off the right on each loop iteration. If the rightmost bit is a 1, we increase the count by 1, and otherwise the count remains unchanged. So, once c is filled with zero bits, we know that we have counted all the one bits, and exactly the one bits, so count contains the number of one bits in c_val.

Upvotes: 8

zsxwing
zsxwing

Reputation: 20836

Your code is just coding how many 1 bits in char c. "c % 2 === 1" checks if the last bit in "c" is 1. So we must use "c = c >> 1" to shift the other bits in "c" to the last position.

Upvotes: 2

Ray Toal
Ray Toal

Reputation: 88428

This isn't a function to determine the "size" of instances of the type char at all, but rather to determine the number of bits in a character that are set to 1.

The expression

c % 2 == 1

determines whether or not the least significant bit is a 1.

The shifting brings the second to last bit into the last position so it can be tested.

The condition while (c) means to keep counting 1s and shifting until the whole byte is all zeros.

Upvotes: 3

Related Questions