バイナリ三値ビットマジック

インタビューには古典的なタスクがあり、多くの場合次のように定式化されます。

自然数の配列があります。 各数値は配列に正確に2回存在し、1つの数値にのみペアがありません。 配列を通るパスの最小数について、ペアを持たない数を決定するアルゴリズムを提案する必要があります。

私はすぐに問題の解決策を与えれば誰も気分を害することはないと思います：ユニークな要素は $$$xor$ -線形時間で計算された、配列のすべての要素の合計。

この問題の別のバリエーションを検討することを提案します。 必要な要素以外のすべての要素がペアではなく、トリプルで配列に存在する場合はどうなりますか？ ソリューションはどのくらい複雑になり、線形のままですか？

---

アナロジーで解決してみましょう。 $$$xor$ それは2つの注目すべき特性を持っているという事実のために出てきました（もちろん、結合性と可換性に加えて）：

1. $$$\ forall a：a \ oplus 0 = a$
2. $$$\ forall a：a \ oplus a = 0$

記号 $$$\ oplus$ このレコードの操作の数学的な指定です $$$xor$ 。 ある操作があると仮定します $$$xor_3$ 同様の特性を満たす：

1. $$$\ forall a：a \ oplus_3 0 = a$
2. $$$\ forall a：a \ oplus_3 a \ oplus_3 a = 0$

この場合 $$$xor_3$ 配列のすべての要素の合計が正しい答えを与えるでしょう。 そのため、このような機能の構築に取り組んでいきます。

私たちはみな知覚に慣れています $$$xor$ 「ビット単位の排他的OR」（選択した名前でも適切です-排他的OR）ですが、この操作を「ビット単位のモジュロ2加算」としてわずかに異なる角度から見ることをお勧めします。 シンボルも不思議ではない $$$\ oplus$ プラスに似ています。

名前だけが変更されたようですが、考えは完全に異なって見えます。 整数のビット単位の表現は、単に2進位置番号システムでの表現です。 そして、各ビットが0または1の数として使用される場合、 $$$xor$ -これは正確にモジュロ2加算です。

同様の推論に従って、 $$$xor_3$ 3進数で3を法とするビット単位の加算を行うことができます。 必要なすべてのプロパティを満たしますが、実装を記述するだけです。

---

記事のタイトルの秘密を明らかにします。 数値をエンコードするかなり一般的な方法があります- バイナリ10進形式。 その本質は、データの4ビットごとに数値の小数点以下1桁を格納することです。これにより、文字列表現への変換が非常に容易になります。

同様に、各3進数を2つのデータビットに個別に格納することは、数値の2進数3進数エンコーディングと呼ばれます。 例：

$$

$$47_ {10} = 101111_ {2} = 1202_ {3} = 01 \：10 \：00 \：10 \：_ {2/3}$$

明確なビジネス。通常の符号なし32ビット整数のストレージには、より多くのデータが必要です。 すなわち $$$2 \ cdot \ lceil {\ log_3 {（2 ^ {32} -1）}} \ rceil = 2 \ cdot \ lceil {20 {、} 189752114} \ rceil = 42$ 64ビットのlong



形式に簡単に移行する少しの情報。

バイナリ形式からバイナリ三元形式への変換の実装はかなり不格好です-オフセットによって必要なビットを読み書きする定期的なサイクル：

 static long to3(int n) { long ln = ((long) n) & 0xFFFFFFFFL; long result = 0L; for (int offset = 0; ln != 0L; ln /= 3, offset += 2) { result |= (ln % 3) << offset; } return result; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 static int from3(long n) { long result = 0L; for (int offset = 40; offset >= 0; offset -= 2) { result = (result * 3) + ((n >> offset) & 0x3L); } return (int) result; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

操作は $$$xor_3$ 、それから単純な実装も利用可能です：

 static long xor3(long a, long b) { long result = 0L; for (int offset = 0; offset < 42; offset += 2) { long digit = ((a >> offset) & 0x3L) + ((b >> offset) & 0x3L); result |= (digit % 3) << offset; } return result; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それはすでにテストされています（そして動作します！）、しかし私はそれに満足していません。

「ビット」関数は通常、次のようになります（これはLong



クラスのメソッドです）。

 public static long reverse(long i) { i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L; i = (i & 0x3333333333333333L) << 2 | (i >>> 2) & 0x3333333333333333L; i = (i & 0x0f0f0f0f0f0f0f0fL) << 4 | (i >>> 4) & 0x0f0f0f0f0f0f0f0fL; i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL; i = (i << 48) | ((i & 0xffff0000L) << 16) | ((i >>> 16) & 0xffff0000L) | (i >>> 48); return i; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このコードは、おそらく非常に最適であり、一見、どのように機能するか完全に理解できないため、私を喜ばせます。 そのようなアルゴリズムから、私は特別な喜びを得ます。

だからこそ、 xor3



の実装を書き直して、ループと条件を取り除きます。

 static long xor3(long a, long b) { long o = a & b & 0xAAAAAAAAAAAAAAAAL; long c = (a + b) - (o << 1); long m = c & (c >>> 1) & 0x5555555555555555L; return (c & ~(m | m << 1)) | (o >>> 1); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、一般的に発生する説明と、これに到達する方法について説明します。

---

そのため、タスクは、次のルールに従って、21番目のビットペア（さらに多くの場合もあります）を同時に処理することです。

$$ $$ display $$ \ begin {array} {|} \ hline \ oplus_3＆00＆01＆10 \\ \ hline 00＆00＆01＆10 \\ \ hline 01＆01＆10＆00 \\ \ hline 10＆10＆00＆01 \\ \ hline \ end {array} $$ display $$

ビットのペア "11"は、3進数では発生しない値3の数字に対応するため、単純に捕捉できません。

引数a



とb



を単純に追加するとどうなりますか？ この操作により、ほとんどすべての入力データバリアントのビットペアの「局所性」が保持されます。 唯一の例外は10



と10



合計で、オーバーフローすると、隣接するカップルの領土にい込みます。

この問題には、結果の防止または修正という2つのアプローチがあります。 2番目のオプションははるかに簡単です。 結果の量から、すべてのオーバーフロービットを減算するだけです。 それらは、各ペアの最上位ビットが1に等しい場合にのみ検出されます。 ここから最初の魔法の変数が生まれます：

 long o = a & b & 0xAAAAAAAAAAAAAAAAL;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

一見理解できない、バイナリ表現の定数は非常に単純に見えます： 0b101010...10



。 その中で、ユニットは最下位ビットをスキップして1つを通過します。 これは、現在興味のないすべてをa & b



から切り離すのに役立ちます。 o



1ビット左にシフトすると、加算中に表示されるすべてのオーバーフロービットが取得されます。

 long c = (a + b) - (o << 1);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

変数c



は、結果に非常に近い値を格納しますが、エラーが発生します。

1. ビット11
   
   
   
   ペアが含まれており、モジュロ3は00
   
   
   
   に置き換えられます。
2. 加算10
   
   
   
   と10
   
   
   
   結果はすべて00
   
   
   
   であり、 01
   
   
   
   でなければなりません。

これらのエラーを順番に修正してください。 11



等しいビットのペアを見つけることは難しくありません。すでに非常によく似たことが行われています。

 long m = c & (c >>> 1) & 0x5555555555555555L;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでの魔法の定数は~0xAAAAAAAAAAAAAAAAL



過ぎません。つまり、最も若いものから順に、1つのビットが1を介して~0xAAAAAAAAAAAAAAAAL



数です。 したがって、 m



の値でm



単位ビットはc



の値のペア11



に対応するペアの最下位ビットになりc



。

式m | m << 1



m | m << 1



は、これらのペア全体を表します。 それらを取り除くには2つの方法があります。 どちらを選ぶかは好みの問題です。

• c -= m | m << 1;
  
  
  
  
• c &= ~(m | m << 1);
  
  
  
  

最後の間違いを見つけるのは簡単です10



と10



を追加した場所にビットを追加する必要があります。 そして、それらはまったく同じo >>> 1



です。 したがって、最終的なコードは次のようになります。

 return (c & ~(m | m << 1)) | (o >>> 1);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

---

しかし、それだけではありません。 関数の1つでループと条件をto3



、残りの2つのループと条件to3



およびfrom3



を完全に忘れfrom3



。 この方法で最適化できますか？

それはあなたがどのように見えるかに依存します。 正直に3進数に変換したい場合は、3で割る/乗算する必要があります。 ただし、操作自体をより最適なものに置き換えることができます：32ビットの2進数を別の32ビットの3進数に割り当てて、異なる3進数が異なる2進数に対応するようにします（このようなマッピングは単射と呼ばれます）が、2進数と3進数の値は一致する必要はありません。

たとえば、2進数の3進数への直接マッピング（ $$$11001_2 \ rightarrow 11001_3$ ） ただし、ここでの実装は依然として不快です。 私の頭に浮かぶ最も簡単なオプションは、 long



値の半分に偶数のint



ビットを入れ、もう一方に奇数のビットを入れることです。 コードは基本になります：

 static long to3(int n) { long ln = ((long) n) & 0xFFFFFFFFL; return (ln & 0xAAAAAAAAAAAAAAAAL) | (ln & 0x5555555555555555L) << 32; } static int from3(long n) { return (int) (n | n >>> 32); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このようなメソッドをインライン化できます。つまり、元の問題の解決策は次のようになります。

 static int find(int[] v) { long res = 0L; for (int n : v) { long ln = ((long) n) & 0xFFFFFFFFL; res = xor3(res, (ln & 0xAAAAAAAAAAAAAAAAL) | (ln & 0x5555555555555555L) << 32); } return (int) (res | res >>> 32); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ご覧のとおり、それほど難しくありません。 コードはきれいに見えるとさえ言えます（ただし、説明が必要です）。 私の意見を共有してください。

ご清聴ありがとうございました！