根据数字二进制下1的数目排序（1356）

题目

给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。

如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。

请你返回排序后的数组。

示例

输入：arr = [0,1,2,3,4,5,6,7,8] 输出：[0,1,2,4,8,3,5,6,7]

输入：arr = [1024,512,256,128,64,32,16,8,4,2,1] 输出：[1,2,4,8,16,32,64,128,256,512,1024] 解释：数组中所有整数二进制下都只有 1 个 1 ，所以你需要按照数值大小将它们排序。

输入：arr = [10000,10000] 输出：[10000,10000]

输入：arr = [2,3,5,7,11,13,17,19] 输出：[2,3,5,17,7,11,13,19]

输入：arr = [10,100,1000,10000] 输出：[10,100,10000,1000]

提示

• 1 <= arr.length <= 500
• 0 <= arr[i] <= 10^4

算法

暴力法

通过 js 内置 sort() 排序函数比较参数的二进制下1的数目多少来排序

export const sortByBits = (arr) => {
	return arr.sort((a, b) => {
		const num1 = a
			.toString(2)
			.split("")
			.reduce((acc, cur) => (cur === "1" ? acc + 1 : acc), 0);
		const num2 = b
			.toString(2)
			.split("")
			.reduce((acc, cur) => (cur === "1" ? acc + 1 : acc), 0);
		if (num1 < num2) return -1;
		if (num1 > num2) return 1;
		if (num1 === num2) {
			if (a < b) return -1;
			if (a > b) return 1;
		}
		return 0;
	});
};

位运算符&和>>

求一个数字的二进制可以使用辗转相除法，因为要求1的次数，而二进制每一位只能出现1或0，统计1出现的次数时将数字加上就好

辗转相除法会对数做除法运算，取商做下一次计算的被除数，取余数做二进制结果的对应位，所以这里可以使用位运算符&和>>实现：

• &实现除以2取余：3 & 1 === 1
• >>实现除以2得商：5 >> 1 === 2

其余思想类似方法一

export const sortByBits = (arr) => {
	const getBits = (num) => {
		let count = 0;
		while (num !== 0) {
			count += num & 1;
			num = num >> 1;
		}
		return count;
	};
	return arr.sort((a, b) => getBits(a) - getBits(b) || a - b);
};