Битовое равенство

Question

Мне нужно нечто большее, чем класс System.Collections.BitArray в моем приложении. В частности, мне нужен массив битов:

• Быть неизменным
• Для реализации равенства используется семантика значений

Я создал свой собственный struct, в значительной степени копируя внутреннюю часть реализации BitArray. (Спасибо, .Net Reflector !)

Я не занимаюсь каждодневными побитовыми операциями, поэтому не уверен в своей реализации равенства. (Он проходит модульные тесты, которые я использую, но у меня могут отсутствовать крайние случаи.) У меня есть предлагаемые решения в качестве ответов ниже. Буду признателен за отзывы и ответы других за то, что может быть более правильным или эффективным.

Как и CLR BitArray, поле length относится к числу битов в структуре, а поле array (или свойство Array) относится к 32-битному целочисленному массиву, который представляет биты. .

[РАЗЪЯСНЕНИЕ] Я выбрал легкий путь в своих конструкторах и других методах, чтобы не полагаться на ненужные биты, являющиеся нулями. Например,

• Not() реализуется путем побитового отрицания (~) для элементов целочисленного массива.
• Доступен конструктор, который принимает длину и логическое значение для инициализации всех битов. Если значение инициализации равно true, я устанавливаю все элементы массива int на -1 (в дополнении до двух, представленного всеми 1)
• 1035 * Etc. *

Таким образом, мне нужно обрабатывать (или, скорее, игнорировать) их при сравнении. Хорошим решением также было бы постоянно обнулять эти биты, но в моей ситуации это приведет к увеличению объема работы (как для компьютера, так и для меня!)

Answer 1

Если в конструкторе ImmutableBitArray неиспользуемые «биты заполнения» в последнем элементе обнуляются, вам не нужно прыгать через обручи, чтобы проверять только действительные биты в последнем элементе, так как заполнение быть одинаковым в равных случаях.

Это значительно упростит методы Equals() и GetHashCode():

public bool Equals(ImmutableBitArray other)
{
    if (this.length != other.length)
    {
        return false;
    }

    for (int i = 0; i < this.Array.Length; i++)
    {
        if (this.Array[i] != other.Array[i])
        {
            // since padding bits are forced to zero in the constructor,
            //  we can test those for equality just as well and the valid
            //  bits
            return false;
        }
    }

    return true;
}


public override int GetHashCode()
{
    int hc = this.length;

    for (int i = 0; i < this.Array.Length; i++)
    {
        // since padding bits are forced to zero in the constructor,
        //  we can mix those into the hashcode no problem

        hc ^= this.Array[i];
    }

    return hc;
}

Answer 2

Обновление : мой оригинальный анализ ниже был неверным ...

К сожалению, я ошибся в поведении << 32 - C # заставляет оператор левого сдвига ограничивать число сдвигов младшими 5 битами правого операнда (6 бит для сдвига с участием 64-битного левый операнд). Таким образом, ваш исходный код был четко определен и корректен в C # (это неопределенное поведение в C / C ++). По сути, это выражение сдвига:

(this.Array[i] << shift)

эквивалентно:

(this.Array[i] << (shift & 0x1f))

Я бы, вероятно, все еще изменил бы сдвиг, чтобы сделать это явным (если бы по другой причине, что, когда я посмотрел на этот код 6 месяцев спустя, я бы не наткнулся на тот же ошибочный анализ), используя вышеприведенное вместо if (shift == 32) проверьте.

Оригинальный анализ:

---

Хорошо, вот второй ответ. Самое главное, я думаю, что ваше оригинальное решение имеет ошибку в том случае, если длина вашего ImmutableBitArray в битах кратна 32 битам, вы вернете true для 2 массивов, которые отличаются в последнем массиве Int32[] элемент.

Например, рассмотрим ImmutableBitArray с длиной битов 32 бита, которые отличаются. Исходный метод Equals() будет выполнять операцию сдвига для единственного и единственного Int32 в массиве - но он сместит значения 32 бита, поскольку

int shift = 0x20 - (this.length % 0x20);

будет оцениваться до 32.

Это означает следующий тест:

if (this.Array[i] << shift != other.Array[i] << shift)

Будет проверено на (0 != 0), и, следовательно, return false не будет выполнено.

Я бы изменил ваш Equals() метод на что-то вроде следующего, что не является существенным изменением - я думаю, что он устраняет вышеупомянутую ошибку и изменяет пару других вещей, которые строго связаны со стилем, поэтому могут не имеет никакого интереса к вам. Также обратите внимание, что я на самом деле не скомпилировал и не протестировал свой метод Equals(), так что есть почти 100% вероятность, что есть ошибка (или, по крайней мере, синтаксическая ошибка):

public bool Equals(ImmutableBitArray other)
{
    if (this.length != other.length)
    {
        return false;
    }

    int finalIndex = this.Array.Length - 1;

    for (int i = 0; i < finalIndex; i++)
    {
        if (this.Array[i] != other.Array[i])
        {
            return false;
        }
    }

    // check the last array element, making sure to ignore padding bits

    int shift = 32 - (this.length % 32);
    if (shift == 32) {
        // the last array element has no padding bits - don't shift
        shift = 0;
    }

    if (this.Array[finalIndex] << shift != other.Array[finalIndex] << shift)
    {
        return false;
    }

    return true;
}

Обратите внимание, что, строго говоря, оригинальный метод GetHashCode() не содержит ошибок, даже если он имеет тот же недостаток, потому что даже если вы неправильно смешиваете последний элемент, когда длина в битах кратна 32, равный объект будет по-прежнему возвращать тот же хэш-код. Но я все же, вероятно, решил бы исправить ошибку таким же образом в GetHashCode().

Answer 3

После нескольких часов поиска и изучения я наконец получил ответ и хотел бы поделиться. Я не проверял производительность, так как меня заботит только читабельность.

if (input1.length != input2.length)
{
    return false;
}

var result = new BitArray(input1);
result = result.Xor(input2);

if (result.Cast<bool>().Contains(true))
    return false;
return true;

Answer 4

Метод равенства:

public bool Equals(ImmutableBitArray other)
{
    if (this.length != other.length)
    {
        return false;
    }

    for (int i = 0; i < this.Array.Length; i++)
    {
        if (this.Array[i] != other.Array[i])
        {
            // This does not necessarily mean that the relevant bits of the integer arrays are different.
            // Is this before the last element in the integer arrays?
            if (i < this.Array.Length - 1)
            {
                // If so, then the objects are not equal.
                return false;
            }

            // If this is the last element in the array we only need to be concerned about the bits
            // up to the length of the bit array.
            int shift = 0x20 - (this.length % 0x20);
            if (this.Array[i] << shift != other.Array[i] << shift)
            {
                return false;
            }
        }
    }

    return true;
}

И необходимое переопределение GetHashCode:

public override int GetHashCode()
{
    int hc = this.length;

    for (int i = 0; i < this.Array.Length; i++)
    {
        if (i < this.Array.Length - 1)
        {
            hc ^= this.Array[i];
        }
        else
        {
            int shift = 0x20 - (this.length % 0x20);
            hc ^= this.Array[this.Array.Length - 1] << shift;
        }
    }

    return hc;
}