JavaScriptで2進数表現の「1」の個数に基づいて配列を並べ替える方法

本記事では、数値の配列を受け取り、各数値を2進数表現に変換したときに含まれる「1」の個数が多い順（降順）に並べ替えるJavaScript関数の実装方法を解説します。

問題の概要

数値の配列を引数として受け取るJavaScript関数を作成します。この関数は、各数値の2進数表現に含まれる「1」の個数に基づいて要素を降順に並べ替え、その結果の配列を返す必要があります。

たとえば、数値 78 の2進数表現は 1001110 なので「1」が4個、数値 124 の2進数表現は 1111100 なので「1」が5個あります。この場合、「1」の個数が多い 124 の方が先頭に近い位置に来ます。

解き方のアプローチ

実装の手順は以下の通りです。

1. Number.prototype.toString(2) を使って、各数値を2進数の文字列に変換します。
2. 変換した文字列から「1」の出現回数をカウントします。
3. Array.prototype.sort() の比較関数で、両引数の「1」のカウント差を返すことで降順に並べ替えます。

コード例

const arr = [5, 78, 11, 128, 124, 68, 6];

// 数値を2進数文字列に変換し、「1」の個数を数える
const countOnes = (num) => {
   return num.toString(2).split('').filter(bit => bit === '1').length;
};

// 「1」の個数が多い順（降順）に並べ替える
const sortByHighBit = (arr = []) => {
   return [...arr].sort((a, b) => countOnes(b) - countOnes(a));
};

console.log(sortByHighBit(arr));

出力結果

[ 124, 78, 11, 5, 68, 6, 128 ]

コードの解説

countOnes 関数について

countOnes は、受け取った数値を num.toString(2) で2進数文字列に変換し、split('') で1文字ずつ配列に分解してから、filter() で「'1'」だけを抽出しています。最終的な配列の長さが、その数値の2進数表現における「1」の個数となります。

より簡潔に書きたい場合は、正規表現を使って次のように記述することもできます。

const countOnes = (num) => num.toString(2).replace(/0/g, '').length;

sortByHighBit 関数について

sortByHighBit では、sort() に比較関数 (a, b) => countOnes(b) - countOnes(a) を渡しています。比較関数が負の値を返せば a が先、正の値を返せば b が先に配置されるため、この式により「1」の個数が多い要素ほど前に来る降順の並びになります。

また、sort() は元の配列を直接変更する破壊的メソッドのため、スプレッド構文 [...arr] でコピーしてからソートしており、呼び出し元の配列はそのまま保持されます。

ビット演算を使った別解

文字列変換を行わず、ビット演算子だけで「1」の個数を数えることも可能です。

const countOnes = (num) => {
   let count = 0;
   while (num > 0) {
      count += num & 1; // 最下位ビットが1ならカウント
      num >>= 1;        // 右へ1ビットシフト
   }
   return count;
};

この方法は文字列を生成しないため、大きな数値を大量に処理する場合にも効率的です。

まとめ

2進数への変換には toString(2)、並べ替えには sort() の比較関数を活用すれば、「1」の個数によるソートは短いコードで実現できます。ビット演算を使った方法も併せて覚えておくと、アルゴリズムの学習やコーディング試験などで役立つでしょう。