побитовая битманипуляционная головоломка - PullRequest
0 голосов
/ 25 марта 2012

Здравствуйте, есть вопрос для школьного задания, мне нужно:

Считать округленное число с внутренним бинарным кодом с битом 0 справа и битом 7 слева.

Теперь мне нужно изменить: бит 0 с битом 7 бит 1 с битом 6 бит 2 с битом 5 бит 3 с битом 4

по примеру:

если я использую hex, F703 становится F7C0 потому что 03 = 0000 0011 и C0 = 1100 0000 (только правильный байт (8 бит) должен быть переключен. Урок был о бит-манипуляции, но я не могу найти способ исправить это для всех 16-ти чисел. enter image description here

Теперь я озадачен хитростью,

Я думаю об использовании массива для этой проблемы, или кто-то может сказать, что я могу сделать это только с помощью побитовых ^, &, ~, <<, >>, операторов ???

Ответы [ 3 ]

0 голосов
/ 25 марта 2012

Это выполняет одну четверть работы, но я не собираюсь оказывать вам больше помощи, чем эта;если вы сможете понять, почему я это сказал, тогда вы сможете заполнить оставшуюся часть кода.

if ((i ^ (i >> (5 - 2))) & (1 >> 2))
  i ^= (1 << 2) | (1 << 5);
0 голосов
/ 25 марта 2012

Изучите следующие две функции:

bool GetBit(int value, int bit_position)
{
    return value & (1 << bit_position);
}

void SetBit(int& value, int bit_position, bool new_bit_value)
{
    if (new_bit_value)
        value |= (1 << bit_position);
    else
        value &= ~(1 << bit_position);
}

Итак, теперь мы можем читать и записывать произвольные биты, как массив.

1 << N

дает вам:

000...0001000...000

Где 1 находится в N-й позиции.

Итак

1 << 0 == 0000...0000001
1 << 1 == 0000...0000010
1 << 2 == 0000...0000100
1 << 3 == 0000...0001000
...

и т. Д.

Что теперь произойдет, если я BINARY И один из приведенных выше чиселс каким-то другим числом Y?

X = 1 << N
Z = X & Y

Как будет выглядеть Z?Ну, каждый бит кроме Nth определенно будет 0, не так ли?потому что эти биты равны 0 в X.

Каким будет N-й бит Z?Это зависит от значения N-го бита Y, не так ли?Итак, при каких обстоятельствах Z ноль?Именно тогда, когда N-й бит Y равен 0. Поэтому, преобразовав Z в логическое значение, мы можем отделить значение N-го бита Y. Еще раз взглянем на приведенную выше функцию GetBit, это именно то, что она делает.

Теперь, когда мы читаем биты, как мы можем установить бит?Ну, если мы хотим установить бит, мы можем использовать BINARY OR с одним из (1 << N) чисел сверху: </p>

X = 1 << N
Z = Y | X

Что Z будет здесь?Ну, каждый бит будет таким же, как Y, кроме N-го, верно?И N-й бит всегда будет равен 1. Итак, мы установили N-й бит.

Как насчет установки бита в ноль?То, что мы хотим сделать, это взять число типа 11111011111, где только N-й бит выключен, и затем использовать BINARY AND.Чтобы получить такое число, мы просто используем BINARY NOT:

X = 1 << N   // 000010000
W = ~X       // 111101111
Z = W & Y

Таким образом, все биты в Z, кроме N-го, будут копиями Y. N-й всегда будет выключен.Таким образом, мы фактически установили N-й бит равным 0.

Используя вышеописанные два метода, мы реализовали SetBit.

Так что теперь мы можем читать и записывать произвольные биты.Теперь мы можем обратить биты числа так же, как это было в массиве:

int ReverseBits(int input)
{
    int output = 0;

    for (int i = 0; i < N; i++)
    {
        bool bit = GetBit(input, i); // read ith bit

        SetBit(output, N-i-1, bit); // write (N-i-1)th bit
    }

    return output;
}

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

Если вам понравилось, попробуйте некоторые из них:

http://graphics.stanford.edu/~seander/bithacks.html

И / или получите эту книгу:

http://www.amazon.com/exec/obidos/ASIN/0201914654/qid%3D1033395248/sr%3D11-1/ref%3Dsr_11_1/104-7035682-9311161

0 голосов
/ 25 марта 2012

По сути, вам нужно изменить порядок следования битов. Мы не собираемся решать это за вас ... но вот подсказка:

Что, если у вас есть 2-битное значение. Как бы вы изменили эти биты?

Простой обмен будет работать, верно? Подумайте, как закодировать этот обмен с доступными вам операторами.

Теперь допустим, что у вас есть 4-битное значение. Как бы вы изменили эти биты?

Не могли бы вы разделить его на два 2-битных значения, перевернуть каждое из них, а затем поменять их местами? Это даст вам правильный результат? Теперь код это.

Обобщение этого решения для 8-битного значения теперь должно быть тривиальным.

Удачи!

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...