Битовые поля в C #
-
05-07-2019 - |
Вопрос
Итак, битовые поля. В частности, большие битовые поля. Я понимаю, как манипулировать отдельными значениями в битовом поле, но как бы я делал это на большом наборе, например, скажем:
uint[] bitfield = new uint[4] { 0x0080000, 0x00FA3020, 0x00C8000, 0x0FF00D0 };
Конкретная проблема, с которой я сталкиваюсь, - это сдвиги влево и вправо по всему массиву. Так, например, если бы я сделал > > 4
в приведенном выше массиве, я бы в итоге:
uint[4] { 0x0008000, 0x000FA302, 0x000C800, 0x00FF00D };
Теперь (чрезмерно) упрощенный алгоритм здесь может выглядеть примерно так (это я пишу код на лету):
int shift = 4;
for (int i = 0; i <= shift; i++) {
for (int j = bitfield.GetUpperBound(0); j > 0; j--) {
bitfield[j] = bitfield[j] >> 1;
bitfield[j] = bitfield[j] + ((bitfield[j-1] & 1) << (sizeof(uint)*8));
}
bitfield[0] = bitfield[0] >> 1;
}
Есть ли что-нибудь, что могло бы облегчить работу с данными такого рода? Р>
Решение
С чего вы взяли, что BitArray использует bools для внутреннего использования? Он использует логические значения для представления битов в терминах API, но я считаю, что он использует int [].
Другие советы
Я не уверен, что это лучший способ сделать это, но это может сработать (ограничение сдвигов должно быть в диапазоне 0-31.
public static void ShiftLeft(uint[] bitfield, int shift) {
if(shift < 0 || shift > 31) {
// handle error here
return;
}
int len = bitfield.Length;
int i = len - 1;
uint prev = 0;
while(i >= 0) {
uint tmp = bitfield[i];
bitfield[i] = bitfield[i] << shift;
if(i < len - 1) {
bitfield[i] |= (uint)(prev & (1 >> shift) - 1 ) >> (32 - shift);
}
prev = tmp;
i--;
}
}
public static void ShiftRight(uint[] bitfield, int shift) {
if(shift < 0 || shift > 31) {
// handle error here
return;
}
int len = bitfield.Length;
int i = 0;
uint prev = 0;
while(i < len) {
uint tmp = bitfield[i];
bitfield[i] = bitfield[i] >> shift;
if(i > 0) {
bitfield[i] |= (uint)(prev & (1 << shift) - 1 ) << (32 - shift);
}
prev = tmp;
i++;
}
}
PD: с этим изменением вы сможете обрабатывать сдвиги, превышающие 31 бит. Может быть изменен, чтобы он выглядел немного менее уродливо, но в моих тестах это работает, и это не кажется слишком плохим с точки зрения производительности (разве что на самом деле есть что-то встроенное для обработки больших наборов битов, что может иметь место). р>
public static void ShiftLeft(uint[] bitfield, int shift) {
if(shift < 0) {
// error
return;
}
int intsShift = shift >> 5;
if(intsShift > 0) {
if(intsShift > bitfield.Length) {
// error
return;
}
for(int j=0;j < bitfield.Length;j++) {
if(j > intsShift + 1) {
bitfield[j] = 0;
} else {
bitfield[j] = bitfield[j+intsShift];
}
}
BitSetUtils.ShiftLeft(bitfield,shift - intsShift * 32);
return;
}
int len = bitfield.Length;
int i = len - 1;
uint prev = 0;
while(i >= 0) {
uint tmp = bitfield[i];
bitfield[i] = bitfield[i] << shift;
if(i < len - 1) {
bitfield[i] |= (uint)(prev & (1 >> shift) - 1 ) >> (32 - shift);
}
prev = tmp;
i--;
}
}
public static void ShiftRight(uint[] bitfield, int shift) {
if(shift < 0) {
// error
return;
}
int intsShift = shift >> 5;
if(intsShift > 0) {
if(intsShift > bitfield.Length) {
// error
return;
}
for(int j=bitfield.Length-1;j >= 0;j--) {
if(j >= intsShift) {
bitfield[j] = bitfield[j-intsShift];
} else {
bitfield[j] = 0;
}
}
BitSetUtils.ShiftRight(bitfield,shift - intsShift * 32);
return;
}
int len = bitfield.Length;
int i = 0;
uint prev = 0;
while(i < len) {
uint tmp = bitfield[i];
bitfield[i] = bitfield[i] >> shift;
if(i > 0) {
bitfield[i] |= (uint)(prev & (1 << shift) - 1 ) << (32 - shift);
}
prev = tmp;
i++;
}
}
Используя методы расширения, вы можете сделать это:
public static class BitArrayExtensions
{
public static void DownShift(this BitArray bitArray, int places)
{
for (var i = 0; i < bitArray.Length; i++)
{
bitArray[i] = i + places < bitArray.Length && bitArray[i + places];
}
}
public static void UpShift(this BitArray bitArray, int places)
{
for (var i = bitArray.Length - 1; i >= 0; i--)
{
bitArray[i] = i - places >= 0 && bitArray[i - places];
}
}
}
К сожалению, я не смог придумать способ перегрузки операторов сдвига. (В основном потому, что BitArray
запечатан.)
Если вы намереваетесь манипулировать int
или uint
, вы можете создать методы расширения для вставки битов в / извлечения битов из BitArray
, ( BitArray
имеет конструктор, который принимает массив из int
, но это только приводит вас к этому.)
Это не касается конкретно сдвига, но может быть полезно для работы с большими наборами. Это в C, но я думаю, что это может быть легко адаптировано к C #