## DEV Community is a community of 641,972 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# UVA 11933 - Splitting Numbers

Nithin SJ
An Aspiring Competitive Programmer, Self taught Full Stack Developer. Looking to give back to the community.

Problem statement
We define the operation of splitting a binary number n into two numbers a(n), b(n) as follows. Let 0 ≤ i1 < i2 < . . . < ik be the indices of the bits (with the least significant bit having index 0) in n that are 1. Then the indices of the bits of a(n) that are 1 are i1, i3, i5, . . . and the indices of the bits of b(n) that are 1 are i2, i4, i6, . . . For example, if n is 110110101 in binary then, again in binary, we have a = 010010001 and b = 100100100.
Input
Each test case consists of a single integer n between 1 and 231 − 1 written in standard decimal (base 10) format on a single line. Input is terminated by a line containing ‘0’ which should not be processed.
Output
The output for each test case consists of a single line, containing the integers a(n) and b(n) separated by a single space. Both a(n) and b(n) should be written in decimal format.
Sample Input
6
7
13
0
Sample Output
2 4
5 2
9 4

Observation
Here, for every time ith bit is set, set ith bit of a and b alternatively.

Code

``````/*
Author : humanbeeng
*/
#include <bits/stdc++.h>
using namespace std;
#define fo(i, n) for (int i = 0; i < n; i++)
#define pb(num) push_back(num)
#define ppb pop_back()
#define all(arr) arr.begin(), arr.end()
#define pi(arr)                                            \
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) \
cout << arr[i] << ' '
#define imn INT_MIN
#define imx INT_MAX
#define mod 1000000007
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<ii> vii;
typedef vector<char> vc;
typedef unsigned long long ull;
typedef set<string, int> ssi;
typedef set<int> si;
typedef set<string> ss;

void setio(string s) {
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}

int main() {
//setio("");
int num;
while (cin >> num && num != 0) {
bitset<32> a(0);
bitset<32> b(0);
bitset<32> n(num);
int sw = 0;
int i = 0;
while(i<32){
if(n.test(i) && sw == 0){
a.set(i);
sw = 1;
}else if(n.test(i) && sw == 1){
b.set(i);
sw = 0;
}
i++;
}
int aa = a.to_ulong();
int bb = b.to_ulong();
cout << aa << " " << bb << endl;

}

return 0;
}
``````