My name
is
Jon Skeet

Custom IComparer for Int64

I have a about 5000 Int64 in a sorted List.

I want to do a List.BinarySearch 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.

For a class you just MyClass : IComparer

How to add a custom IComparer for Int64?

I know how to use masking to efficiently extract the 39 bits.

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.

I guess I could just write a custom binary search.

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.

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.

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.

Simplified code sample

public void ListBinaryLeft()
{
    List<byte> fourLeftFourRight = new List<byte>();
    for(int i = 0; i < 16; i+= 2)
    {
        byte newRow = (byte)((i << 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 < 16; i += 2)
    {
        int findRow = fourLeftFourRight.BinarySearch((byte)(i << 4));
        Debug.WriteLine("key index of {0} is {1} ", i, findRow); //strange getting a negative and off by 1
        findRow = fourLeftFourRight.BinarySearch((byte)((i << 4) | 1));
        Debug.WriteLine("cheat index of {0} is {1} ", i, findRow);  //works but this is not what I need
    }          
    Debug.WriteLine("");
}

Your comparer just needs to compare by masking and then comparing the results. (Shifting works too - they're basically equivalent here, although masking allows your key to be any set of bits in the input, rather than necessarily the most significant bits.) To use your example - but as a minimal complete console app:

using System;
using System.Collections.Generic;

class Test
{
    static void Main()
    {
        List<byte> list = new List<byte>();
        for(int i = 0; i < 16; i+= 2)
        {
            byte newRow = (byte)((i << 4) | 1);
            list.Add(newRow);
        }

        var comparer = new MaskingComparer(0xf0);
        // Only needed if the values aren't added in order to start with
        list.Sort(comparer);

        for (int i = 0; i < 16; i += 2)
        {
            int index = list.BinarySearch((byte)(i << 4), comparer);
            Console.WriteLine($"Key index of {i} is {index}");
            if (index >= 0)
            {
                byte value = (byte) (list[index] & 0xf);
                Console.WriteLine($"Associated value: {value}");
            }
        }          
    }
}

class MaskingComparer : IComparer<byte>
{
    private readonly byte mask;

    public MaskingComparer(byte mask)
    {
        this.mask = mask;
    }

    public int Compare(byte lhs, byte rhs) =>
        (lhs & mask).CompareTo(rhs & mask);
}

See more on this question at Stackoverflow