0
$\begingroup$
int counter(char c){
    int count = 0;
    while (c!=0){
       if((c & 1) !=0)
         count++;
       c = c >> 1;
}
}

I am trying to understand a program that counts the number of 1s in the binary representation of the input character. While I understand the & part and the count part, I don't get why we're checking for c!=0 in the while loop. I know each character is 8 bits. For instance, if the input character is "2" then the binary representation is 10. The count will be 1. So we start by checking the first binary number "1". Then we shift by 1 and it becomes 01? So then do we check 1 again? Or do we check 0? But if we check 0 then does the while loop not run at all?

An example of the steps would be really helpful.

$\endgroup$
2
$\begingroup$

The & operator is a bitwise "AND". Since the binary representation of 1 consists only of a 1 on the least significant bit, the operation c & 1 checks if $c$ contains a 1 on the least significant bit. Another way to say it is that c & 1 is the remainder of $c$ modulo 2, that is 0 if $c$ is even and 1 if $c$ is odd.

The >> is a logical shift right, that is the deletion of the least significant bit.

For example, if $c = 26 = (11010)_2$, the steps are:

  • c & 1 = 0 so count is not modified. $c$ becomes $1101$;
  • c & 1 = 1 so count is incremented. $c$ becomes $110$;
  • c & 1 = 0 so count is not modified. $c$ becomes $11$;
  • c & 1 = 1 so count is incremented. $c$ becomes $1$;
  • c & 1 = 1 so count is incremented. $c$ becomes $0$.
  • c != 0 is not true so the algorithm stops. count was incremented thrice, and three is indeed the number of 1's in the binary representation of $c$.
$\endgroup$
2
  • $\begingroup$ when we say c & 1, we are comparing let's say the last 1 from 1101 or the whole thing? It's compared digit/bit wise, right? $\endgroup$
    – x89
    Apr 4 at 11:08
  • $\begingroup$ The comparison concerns the whole number, but since $(1)_2 = (0001)_2$, then $(1101)_2 \& (0001)_2 = (0001)_2$, so only the last bit matters. $\endgroup$
    – Nathaniel
    Apr 4 at 11:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.