Two's Complement

Interview

Time limit1sMemory limit512 MB

Summary

Given N up to 10^9, count how many of the 32 bits differ between N and its 32-bit two's complement.

Level: Easy3 of 10
Topics: Bit manipulation, Math, Implementation
Solved: No attempts yet

Problem

A computer uses two's complement internally when it performs subtraction. The two's complement of a number is obtained by flipping every bit of that number and then adding 1. Given a number written in 32 bits, print the number of bits in which it differs from its two's complement.

Input

The first line contains an integer N (1 ≤ N ≤ 10^9).

Output

On the first line, print the number of bits in which N and the two's complement of N differ.

Hint

Consider the two's complement of 22 in 32 bits. In binary, 22 is 0000 0000 0000 0000 0000 0000 0001 0110. Flipping these bits gives 1111 1111 1111 1111 1111 1111 1110 1001, and adding 1 gives 1111 1111 1111 1111 1111 1111 1110 1010.

The number of bits in which 0000 0000 0000 0000 0000 0000 0001 0110 and 1111 1111 1111 1111 1111 1111 1110 1010 differ is 30.

Examples1

Example 1
Input
```
2
```
Expected output
```
30
```