Count Set Bits

Lab C Intermediate 20 points

For each input number print its binary form (no leading zeros) and the number of 1 bits, using & and >>.

Input

n, then n non-negative integers.

Output

n lines: binary count

Example

Input

Output

101 2
0 0
11111111 8

Sample input available Sample output available

Editor

Hints

(x >> bit) & 1 extracts one bit.

Solution explanation

Bit tricks are used for flags, permissions, compression and fast arithmetic.

Show solution

#include <stdio.h>

int main() {
    int n, x;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        int ones = 0, started = 0;
        for (int bit = 30; bit >= 0; bit--) {
            int b = (x >> bit) & 1;
            if (b) started = 1;
            if (started) printf("%d", b);
            ones += b;
        }
        if (!started) printf("0");
        printf(" %d\n", ones);
    }
    return 0;
}

Output

Answer