Написать макрос, реализующих циклические перестановки (влево-вправо) на k бит, первых n бит, 32-хбитовоц структуры (unsigned).Обьясните ктонибудь что за циклические перестановки ?Ато я никак не могу врубиться
volvo
21.05.2008 16:13
Цитата
Обьясните ктонибудь что за циклические перестановки ?
При обычном сдвиге, скажем, влево, у тебя все биты, выходящие слева за разрядную сетку теряются, справа добавляются нули: 01010011 сдвиг влево на 2 01001100 Как видишь, 01 потерялось...
Твоя задача - написать макрос, который сдвинет заданное число циклически, то есть, бит, выходящий слева, добавляется справа (и наоборот, если сдвигаем вправо, то "убегающий бит" должен добавиться слева). Для предыдущего примера:
01010011 циклический сдвиг влево на 2 01001101
Так понятнее?
blackhard
21.05.2008 16:19
Цитата(volvo @ 21.05.2008 17:13)
При обычном сдвиге, скажем, влево, у тебя все биты, выходящие слева за разрядную сетку теряются, справа добавляются нули: 01010011 сдвиг влево на 2 01001100 Как видишь, 01 потерялось...
Твоя задача - написать макрос, который сдвинет заданное число циклически, то есть, бит, выходящий слева, добавляется справа (и наоборот, если сдвигаем вправо, то "убегающий бит" должен добавиться слева). Для предыдущего примера:
Стой, стой... Не так... Я сразу не очень внимательно прочел задание...
Тебе надо не просто циклически сдвинуть число на сколько-то бит, тебе надо сдвинуть N первых бит числа циклически на K бит. То есть, если возьмем N = 5, K = 3 и 32-битное число s: 00110101 00001010 00000000 000000002 = (13578 * 65536)10 (для простоты я рассматриваю только первые 16 бит, остальные пусть будут нулевыми, это как раз и даст умножение на 216 = 65536), то "зацикливать" надо только первые 5 бит, остальные должны остаться на своих местах, т.е., результат будет: XXXXX101 00001010 00000000 000000002, где выделенный фрагмент - это N (5 этом случае) бит 00110, сдвинутые циклически на K (т.е, на 3) : было 00110 стало 10001 Итого получаем: 10001101 00001010 00000000 000000002 = (36106 * 65536)10...
Теперь другое. Не стОит сразу бросаться и писать макросы. Их очень сложно отлаживать, поэтому сначала пишется программка, в которой это все делается без макросов, обычным способом:
#include <stdio.h> int main() { unsigned int T; char c = 'L'; unsigned s = 13578 * 65536; int n = 5, k = 3;
if(c == 'L') { T = s & ((0xffffffff >> (32 - n)) << (32 - n)); T = (T << k) | (T >> (n - k)); s = T | (s & (0xffffffff >> n)); } printf("%u", s / 65536); return 0; }
Как видишь, получилось именно 36106, значит, фрагмент работает правильно. Сделай аналогичные преобразования для сдвига вправо, чтоб оно работало правильно, а потом уже преобразуй в макрос...
blackhard
22.05.2008 18:33
Цитата(volvo @ 21.05.2008 20:02)
Стой, стой... Не так... Я сразу не очень внимательно прочел задание...
Тебе надо не просто циклически сдвинуть число на сколько-то бит, тебе надо сдвинуть N первых бит числа циклически на K бит. То есть, если возьмем N = 5, K = 3 и 32-битное число s: 00110101 00001010 00000000 000000002 = (13578 * 65536)10 (для простоты я рассматриваю только первые 16 бит, остальные пусть будут нулевыми, это как раз и даст умножение на 216 = 65536), то "зацикливать" надо только первые 5 бит, остальные должны остаться на своих местах, т.е., результат будет: XXXXX101 00001010 00000000 000000002, где выделенный фрагмент - это N (5 этом случае) бит 00110, сдвинутые циклически на K (т.е, на 3) : было 00110 стало 10001 Итого получаем: 10001101 00001010 00000000 000000002 = (36106 * 65536)10...
Теперь другое. Не стОит сразу бросаться и писать макросы. Их очень сложно отлаживать, поэтому сначала пишется программка, в которой это все делается без макросов, обычным способом:
#include <stdio.h> int main() { unsigned int T; char c = 'L'; unsigned s = 13578 * 65536; int n = 5, k = 3;
if(c == 'L') { T = s & ((0xffffffff >> (32 - n)) << (32 - n)); T = (T << k) | (T >> (n - k)); s = T | (s & (0xffffffff >> n)); } printf("%u", s / 65536); return 0; }
Как видишь, получилось именно 36106, значит, фрагмент работает правильно. Сделай аналогичные преобразования для сдвига вправо, чтоб оно работало правильно, а потом уже преобразуй в макрос...
ну вобщем с программой все ясно, а вот как в макрос засунуть временную переменную Т ?
L - да, R - нет... Для того, чтобы циклически сдвинуть вправо кусок битовой последовательности совершенно недостаточно просто поменять все << на >> и наоборот... Проверяем:
... int main() { unsigned s = 13578 * 65536; int n = 7, k = 4;
R(s, n, k); printf("%u", s / 65536); return 0; }
Чему должен быть равен результат?
00110101000010102 сдвигаем выделенную область на 4 бита вправо: 10100011000010102 = 4173810
А теперь запусти программу...
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.