Разрядное Реверсирование, использующее поразрядно
Я пытаюсь сделать разрядное реверсирование в байте. Я использую код ниже
static int BitReversal(int n)
{
int u0 = 0x55555555; // 01010101010101010101010101010101
int u1 = 0x33333333; // 00110011001100110011001100110011
int u2 = 0x0F0F0F0F; // 00001111000011110000111100001111
int u3 = 0x00FF00FF; // 00000000111111110000000011111111
int u4 = 0x0000FFFF;
int x, y, z;
x = n;
y = (x >> 1) & u0;
z = (x & u0) << 1;
x = y | z;
y = (x >> 2) & u1;
z = (x & u1) << 2;
x = y | z;
y = (x >> 4) & u2;
z = (x & u2) << 4;
x = y | z;
y = (x >> 8) & u3;
z = (x & u3) << 8;
x = y | z;
y = (x >> 16) & u4;
z = (x & u4) << 16;
x = y | z;
return x;
}
Это может инвертор бит (на 32-разрядной машине), но существует проблема, Например, вход 10001111101, я хочу добраться 10111110001, но этот метод инвертировал бы целый байт включая заголовок 0s. Вывод 10111110001000000000000000000000. Там какой-либо метод должен только инвертировать фактическое число? Я не хочу преобразовывать его для строкового представления и инвертор, затем преобразовываю снова. Есть ли какой-либо чистый математический метод или метод битовой операции?
С уважением,
5 ответов
Простой способ - сдвигаться, пока не получится 1 справа:
if (x != 0) {
while ((x & 1) == 0) {
x >>= 1;
}
}
Примечание: вы должны переключить все переменные на unsigned int . Как написано, вы можете получить нежелательное расширение знака в любое время, когда вы сдвинетесь вправо.
Один из методов может заключаться в том, чтобы найти начальное количество битов знака в числе n, сдвинуть влево n на это число и затем запустить его через описанный выше алгоритм.
Предполагается, что все 32 бита являются значимыми, и полностью меняет направление. Вы МОЖЕТЕ попытаться заставить его угадать количество значащих битов, найдя наибольшее значение 1, но это не обязательно точно, поэтому я предлагаю вам изменить функцию, чтобы она принимала второй параметр, указывающий количество значащих битов. Затем, переставив биты, просто сдвиньте их вправо.
Получите наибольший бит числа, используя аналогичный подход, и сдвиньте получившиеся биты вправо на 33 - #бит и вуаля!