Равенство битового массива
Мне нужно что-то немного больше, чем System.Collections.BitArray класс в моем приложении. А именно, мне нужен битовый массив:
- Быть неизменным
- Реализовать равенство с помощью семантики значения
Я создал свое собственное struct, в основном копируя внутренности BitArray реализация. (Спасибо.Net Reflector!)
Я каждый день не имею дело с битовыми операциями, таким образом, у меня нет самой высокой степени уверенности в моей реализации равенства. (Это передает модульные тесты, которые я бросаю в него, но я могу пропускать пограничные случаи.) У меня есть свои предлагаемые решения как ответы ниже. Я ценил бы обратную связь других и ответы для чего-то, что может быть более корректным или эффективным.
Точно так же, как CLR BitArray, length поле относится к числу битов в структуре и array поле (или Array свойство), относится к 32-разрядному целочисленному массиву, который представляет биты.
[РАЗЪЯСНЕНИЕ] я принял решение следовать легким маршрутом в своих конструкторах и других методах так, чтобы я не мог полагаться на ненужные биты, являющиеся нулями. Например,
Not()реализован поразрядным отрицанием (~) на целочисленных элементах массива.- Конструктор доступен, который берет длину и булевскую переменную для инициализации всех битов. Если значение инициализации истинно, я установил все элементы международного массива к-1 (в дополнении two, представленном всеми 1's)
- И т.д.
Таким образом я должен обработать (или, скорее проигнорировать), их в сравнении. Прекрасное решение состояло бы в том, чтобы также сохранить те биты обнуленными в любом случае, но в моей ситуации, которая приведет к большему количеству работы (и для компьютера и для меня!)
3 ответа
Обновление : мой первоначальный анализ, приведенный ниже, был неверным ...
К сожалению, я ошибался в отношении поведения << 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 () .
Метод равенства:
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;
}
Если в конструкторе 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;
}