# UVa 10019

Jump to navigation
Jump to search

## Contents

## 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