# UVa 10019

## Summary

Given a string of digits S:

• interpret S as a base-10 number, figure out the number of 1's in its binary representation
• interpret S as a base-16 number, figure out the number of 1's in its binary representation

## Explanation

The straightforward way is to implement four separate conversions as described above.

The code can be simplified by observing that the only thing you need to implement is counting bits in the binary representation of an integer variable. This can be done cleverly using bitwise operations. For the base-16 case, you can simply process the characters of S one at a time, for each of them count the number of 1's its binary representation, and sum the results.

## Implementation

An elegant way of counting 1's in the binary representation of N (C++):

```int countSetBits(int N) {
int result = 0;
while (N) { result++; N &= N-1; }
return result;
}
```

(This is one of the less brain-bending implementations of popcount aka Wikipedia: Hamming weight ).

```3
265
111
1234
```

```3 5
6 3
5 5
```