sortByBits

Hôm nay, Nâm đến chơi nhà một người bạn có bố là một kỹ sư máy tính. Đến nơi, Nâm thấy nhà bạn mình bừa bộn những chiếc hộp chứa các số tự nhiên không âm. Bạn của Nâm thấy vậy đã rủ Nâm chơi một trò chơi:

Sắp xếp những chiếc hộp chứa các số tự nhiên này theo thứ tự tăng dần nhưng với điều kiện số nào nhiều bit 1 hơn trong hệ cơ số nhị phân thì nó sẽ đứng sau, nếu số bit 1 bằng nhau thì sắp xếp tăng dần theo giá trị của số tự nhiên ấy.

Đúng là con của kỹ sư tin học! Hãy giúp Nâm sắp xếp dãy hộp này nhé.

Ví dụ:

• Với array = [0,1,2,3,4,5,6,7,8] thì sort_by_bits(array) = [0,1,2,4,8,3,5,6,7].
  Giải thích:
  • Vì 0 thì không có bit 1 nào
  • 1, 2, 4, 8 đều có 1 bit 1
  • 3, 5, 6 thì đều có 2 bit 1
  • 7 thì có 3 bit 1.

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.1s với C++, 0.6s với Java và C#, 0.8s với Python, Go và JavaScript.
• [Đầu vào] Array.Integer array
  1 ≤ array.length ≤ 105 
0 ≤ array[i] ≤ 109 
• [Đầu ra] Array.Integer
  Mảng đã sắp xếp theo đề bài.