登录位运算和排序，看完你能写出上百种答案。
解题思路
第一步：先求出位 1 的个数
这题是让按照位 1 的个数来排序，首先要求出 1 的个数才能参与后面的排序，关于求一个数二进制中 1 的个数，我之前写了 18 种写法，这里直接列出来，就不在详细介绍，如果有看不懂的可以在下面留言，我给你一一解答。
1、把 $n$ 往右移 32 次，每次都和 1 进行与运算
public int hammingWeight(int n) {
int count = 0;
for (int i = 0; i < 32; i++) {
if (((n >>> i) & 1) == 1) {
count++;
}
}
return count;
}
2、原理和上面一样，做了一点优化
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
count += n & 1;
n = n >>> 1;
}
return count;
}
3、每次往左移一位，再和 $n$ 进行与运算
public int hammingWeight(int n) {
int count = 0;
for (int i = 0; i < 32; i++) {
if ((n & (1 << i)) != 0) {
count++;
}
}
return count;
}
4、每次往左移一位，把运算的结果在右移判断是否是 1
public int hammingWeight(int i) {
int count = 0;
for (int j = 0; j < 32; j++) {
if ((i & (1 << j)) >>> j == 1)
count++;
}
return count;
}
5、这个是最常见的，每次消去最右边的 1，直到消完为止
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n &= n - 1;
count++;
}
return count;
}
6、把上面的改为递归
public int hammingWeight(int n) {
return n == 0 ? 0 : 1 + hammingWeight(n & (n - 1));
}
7、查表
public int hammingWeight(int i) {
//table是0到15转化为二进制时1的个数
int table[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
int count = 0;
while (i != 0) {//通过每4位计算一次，求出包含1的个数
count += table[i & 0xf];
i >>>= 4;
}
return count;
}
8、每两位存储，使用加法（先运算再移位）
public int hammingWeight(int n) {
n = ((n & 0xaaaaaaaa) >>> 1) + (n & 0x55555555);
n = ((n & 0xcccccccc) >>> 2) + (n & 0x33333333);
n = (((n & 0xf0f0f0f0) >>> 4) + (n & 0x0f0f0f0f));
n = n + (n >>> 8);
n = n + (n >>> 16);
return n & 63;
}
9、每两位存储，使用加法（先移位再运算）
public int hammingWeight(int n) {
n = ((n >>> 1) & 0x55555555) + (n & 0x55555555);
n = ((n >>> 2) & 0x33333333) + (n & 0x33333333);
n = (((n >>> 4) & 0x0f0f0f0f) + (n & 0x0f0f0f0f));
n = n + (n >>> 8);
n = n + (n >>> 16);
return n & 63;
}
10、和第 8 种思路差不多，只不过在最后几行计算的时候过滤的比较干净
public int hammingWeight(int n) {
n = ((n & 0xaaaaaaaa) >>> 1) + (n & 0x55555555);
n = ((n & 0xcccccccc) >>> 2) + (n & 0x33333333);
n = (((n & 0xf0f0f0f0) >>> 4) + (n & 0x0f0f0f0f));
n = (((n & 0xff00ff00) >>> 8) + (n & 0x00ff00ff));
n = (((n & 0xffff0000) >>> 16) + (n & 0x0000ffff));
return n;
}
11、每 4 位存储，使用加法
public int hammingWeight(int n) {
n = (n & 0x11111111) + ((n >>> 1) & 0x11111111) + ((n >>> 2) & 0x11111111) + ((n >>> 3) & 0x11111111);
n = (((n & 0xf0f0f0f0) >>> 4) + (n & 0x0f0f0f0f));
n = n + (n >>> 8);
n = n + (n >>> 16);
return n & 63;
}
12、每 3 位存储，使用加法
public int hammingWeight(int n) {
n = (n & 011111111111) + ((n >>> 1) & 011111111111) + ((n >>> 2) & 011111111111);
n = ((n + (n >>> 3)) & 030707070707);
n = ((n + (n >>> 6)) & 07700770077);
n = ((n + (n >>> 12)) & 037700007777);
return ((n + (n >>> 24))) & 63;
}
13、每 5 位存储，使用加法
public int hammingWeight(int n) {
n = (n & 0x42108421) + ((n >>> 1) & 0x42108421) + ((n >>> 2) & 0x42108421) + ((n >>> 3) & 0x42108421) + ((n >>> 4) & 0x42108421);
n = ((n + (n >>> 5)) & 0xc1f07c1f);
n = ((n + (n >>> 10) + (n >>> 20) + (n >>> 30)) & 63);
return n;
}
14、每两位存储，使用减法（先运算再移位）
public int hammingWeight(int i) {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
15、每 3 位存储，使用减法
public int hammingWeight(int n) {
n = n - ((n >>> 1) & 033333333333) - ((n >>> 2) & 011111111111);
n = ((n + (n >>> 3)) & 030707070707);
n = ((n + (n >>> 6)) & 07700770077);
n = ((n + (n >>> 12)) & 037700007777);
return ((n + (n >>> 24))) & 63;
}
16、每 4 位存储，使用减法
public int hammingWeight(int n) {
int tmp = n - ((n >>> 1) & 0x77777777) - ((n >>> 2) & 0x33333333) - ((n >>> 3) & 0x11111111);
tmp = ((tmp + (tmp >>> 4)) & 0x0f0f0f0f);
tmp = ((tmp + (tmp >>> 8)) & 0x00ff00ff);
return ((tmp + (tmp >>> 16)) & 0x0000ffff) % 63;
}
17、每 5 位存储，使用减法
public int hammingWeight(int n) {
n = n - ((n >>> 1) & 0xdef7bdef) - ((n >>> 2) & 0xce739ce7) - ((n >>> 3) & 0xc6318c63) - ((n >>> 4) & 0x02108421);
n = ((n + (n >>> 5)) & 0xc1f07c1f);
n = ((n + (n >>> 10) + (n >>> 20) + (n >>> 30)) & 63);
return n;
}
18、每次消去最右边的 1，可以参照第 5 种解法
public static int hammingWeight(int num) {
int total = 0;
while (num != 0) {
num -= num & (-num);
total++;
}
return total;
}
第二步：再根据位 1 的个数进行排序
关于排序算法我之前也写了十几种
101，排序-冒泡排序
102，排序-选择排序
103，排序-插入排序
104，排序-快速排序
105，排序-归并排序
106，排序-堆排序
107，排序-桶排序
108，排序-基数排序
109，排序-希尔排序
110，排序-计数排序
111，排序-位图排序
112，排序-其他排序
第三步：最终答案
有了计算位 1 的方法，又有了排序的方法，所以我们可以随便自由组合，如果都组合一遍估计要写上百种答案了，这里不可能写那么多，我们只写一个看看，这里就用 位运算的第 5 种方式 和排序的第 3 种方式 插入排序 来写下
public int[] sortByBits(int[] arr) {
int[][] temp = new int[arr.length][2];
for (int i = 0; i < arr.length; i++) {
temp[i][0] = arr[i];
temp[i][1] = hammingWeight(arr[i]);
}
insertSort(temp);
for (int i = 0; i < arr.length; i++) {
arr[i] = temp[i][0];
}
return arr;
}
private void insertSort(int[][] array) {
for (int i = 1; i < array.length; i++) {
int j;
int[] temp = array[i];
for (j = i - 1; j >= 0; j--) {
//先比较位1的大小，如果相同再比较数字的大小
if (array[j][1] > temp[1] || (array[j][1] == temp[1] && array[j][0] > temp[0])) {
array[j + 1] = array[j];//往后挪
} else {
break;//没有交换就break
}
}
array[j + 1] = temp;
}
}
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n &= n - 1;
count++;
}
return count;
}
当然我们还可以使用官方的提供的类 PriorityQueue 也是可以的
public int[] sortByBits(int[] arr) {
PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]);
for (int i = 0; i < arr.length; i++) {
priorityQueue.add(new int[]{arr[i], hammingWeight(arr[i])});
}
int index = 0;
while (!priorityQueue.isEmpty()) {
arr[index++] = priorityQueue.poll()[0];
}
return arr;
}
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n &= n - 1;
count++;
}
return count;
}
我把部分算法题整理成了PDF文档，截止目前总共有900多页，大家可以下载阅读
链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
