title: Custom IComparer for Int64
body: <p>I have a about 5000 Int64 in a sorted <a href="https://msdn.microsoft.com/en-us/library/6sh2ey19(v=vs.110).aspx" rel="nofollow noreferrer">List</a>.  </p>
  
  <p>I want to do a <a href="https://msdn.microsoft.com/en-us/library/w4e7fxsh(v=vs.110).aspx" rel="nofollow noreferrer">List.BinarySearch</a> but only based on the 39 bits on the left. 
  I am packing information in the bits to the right of the 39. 
  Basically the 39 bits to the left is the Key and I am packing a value in the 12 bits to the right.  </p>
  
  <p>For a class you just MyClass : <a href="https://msdn.microsoft.com/en-us/library/8ehhxeaf(v=vs.110).aspx" rel="nofollow noreferrer">IComparer</a></p>
  
  <p>How to add a custom IComparer for Int64?  </p>
  
  <p>I know how to use masking to efficiently extract the 39 bits.</p>
  
  <p>I know I could just use a Dictionary but I want to save some space and the way I use it I need the packed data.  I am receiving it has packed data.   </p>
  
  <p>I guess I could just write a custom binary search.</p>
  
  <p>I was asked for an example.  For example will use byte which has 8 bits. Each entry is identified by the 4 left bits.  And I am storing some data in the 4 right bits.  Basically the 4 bits on the left is the key and the 4 bits on the right is value.    </p>
  
  <pre><code>0000 1010
  0001 1010
  0010 1010
  0011 1010
  0100 1011
  0101 1011
  0110 1011 
  0111 1011
  </code></pre>
  
  <p>I want to be able to search on 0011 and get the index of 4th row (3). 
  When I search I don't know what the 4 bits on the right are. 
  Yes the 4 bits on the left are unique. I can just sort on the byte as the bits on the left will determine the proper sort.  </p>
  
  <p>If there is a better approach then great.  I have a packed Int64 where the key is the left 39 bit.  I want fast search based on that key.</p>
  
  <p>Simplified code sample </p>
  
  <pre><code>public void ListBinaryLeft()
  {
      List&lt;byte&gt; fourLeftFourRight = new List&lt;byte&gt;();
      for(int i = 0; i &lt; 16; i+= 2)
      {
          byte newRow = (byte)((i &lt;&lt; 4) | 1);
          fourLeftFourRight.Add(newRow);
          Debug.WriteLine("Hexadecimal value of {0} is {1} {2}  i {3}", newRow, String.Format("{0:X}", newRow), Convert.ToString(newRow, 2).PadLeft(8, '0'), i);
      }
      Debug.WriteLine("");
      fourLeftFourRight.Sort(); //actuall not necessary
      for (int i = 0; i &lt; 16; i += 2)
      {
          int findRow = fourLeftFourRight.BinarySearch((byte)(i &lt;&lt; 4));
          Debug.WriteLine("key index of {0} is {1} ", i, findRow); //strange getting a negative and off by 1
          findRow = fourLeftFourRight.BinarySearch((byte)((i &lt;&lt; 4) | 1));
          Debug.WriteLine("cheat index of {0} is {1} ", i, findRow);  //works but this is not what I need
      }          
      Debug.WriteLine("");
  }
  </code></pre>