UVa 10019

From Algorithmist
Jump to navigation Jump to search

10019 - Funny Encryption Method[edit]

Summary[edit]

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[edit]

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[edit]

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 ).

Input[edit]

3
265
111
1234

Output[edit]

3 5
6 3
5 5