Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- long long isBit (long long num, int bit_number) {
- return (1 & (num >> bit_number));
- }
- int Partition (std::vector<long long>& numbers, int left, int right, int bit_number) {
- if (right <= left)
- return left;
- int i = left, j = right;
- while (i <= j) {
- for(;i <= right && isBit(numbers[i], bit_number) == 0; ++i) {}
- for(;j >= left && isBit(numbers[j], bit_number) == 1; --j) {}
- if (i < j) {
- long long i2 = i;
- i = j;
- j = i2;
- i++;
- j--;
- }
- }
- }
- void BinaryMSD (std::vector <long long>& numbers, int left, int right, int bit_number) {
- int q = Partition (numbers, left, right, bit_number);
- if (bit_number > 0) {
- if (q < right) {
- BinaryMSD(numbers, q, right, bit_number - 1);
- }
- if (q > left) {
- BinaryMSD(numbers, left, q - 1, bit_number - 1);
- }
- }
- }
- int main () {
- int n;
- std::cin >> n;
- std::vector <long long> numbers;
- for (int i = 0; i < n; ++i) {
- int a;
- std::cin >> a;
- numbers.push_back(a);
- }
- BinaryMSD (numbers, 0, numbers.size() - 1, 63);
- for (int i = 0; i < n; ++i) {
- std::cout << numbers[i] << ' ';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement