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

はじめに

本記事では、JavaScriptを使って、整数の配列を2進数表現における「1」の個数に基づいて昇順に並べ替える方法を解説します。

具体的には、以下のような要件を持つ関数を実装します。引数として整数の配列を1つ受け取り、各数値を2進数に変換したときに含まれる「1」の数が少ない順に並べ替えます。さらに、「1」の個数が同じ数値同士の場合は、その大小関係(値そのもの)に従って昇順にソートします。

処理の流れ

例えば、次の入力配列が与えられたとします。

const arr = [34, 37, 23, 89, 12, 31, 23, 89];

この場合、期待される出力は以下の通りです。

const output = [34, 12, 37, 23, 89, 23, 89, 31];

それぞれの数値を2進数に変換すると、「1」の個数は次のようになります。

• 34 → 100010 → 「1」が2個
• 12 → 1100 → 「1」が2個
• 37 → 100101 → 「1」が3個
• 23 → 10111 → 「1」が4個
• 89 → 1011001 → 「1」が4個
• 31 → 11111 → 「1」が5個

「1」の個数が同じ場合は値の小さい順に並ぶため、34と12の順序や、23と89の順序が決まります。

実装コード

以下が実際のコード例です。

const arr = [34, 37, 23, 89, 12, 31, 23, 89];
const sortByBinary = (arr = []) => {
   const calculateOne = (str = '') => {
      let res = 0;
      for(let i = 0; i < str.length; i++){
         if(str[i] === '1'){
            res++;
         };
      };
      return res;
   }
   const sorter = (a, b) => {
      const firstCount = calculateOne((a >>> 0).toString(2));
      const secondCount = calculateOne((b >>> 0).toString(2));
      return firstCount - secondCount;
   };
   arr.sort(sorter);
};
sortByBinary(arr);
console.log(arr);

コードの解説

この実装のポイントを整理します。

• calculateOne関数: 引数として渡された文字列(2進数表現)の中に「1」が何個含まれているかをカウントして返します。
• (a >>> 0).toString(2): 符号なし右シフト演算子 >>> を使うことで負数も正しく扱い、toString(2) で数値を2進数の文字列に変換しています。
• sorter関数: 2つの数値の「1」の個数を比較し、その差を返すことでArray.prototype.sort()の比較関数として機能します。「1」の個数が同じ場合、差が0になるため元の順序(安定ソート)が維持されます。

出力結果

コンソールに出力される結果は以下の通りです。

[
   34, 12, 37, 23,
   89, 23, 89, 31
]

まとめ

このように、JavaScriptでは toString(2) による2進数変換と、カスタム比較関数を組み合わせることで、ビット単位の特性に基づいた柔軟なソート処理を簡単に実装できます。ビットカウントのロジックは、アルゴリズムの学習やコーディング面接でも頻出のテーマなので、ぜひ参考にしてください。