Дано целое неотрицательное число. Произвести в его двоичном представлении обмен битов с номерами 0 и 1, 2 и 3, 4 и 5 и так далее.

Объясните пожалуйста, каким способом нужно производить обмен? Как это вообще будет выглядеть?

Поменять можно так:

 b:=x and 3;          взяли 2 бита
 b:=((b shr 1) or (b shl 1)) and 3;   поменяли..

А использовать все это можно в рекурсивной функции, которая будет состоять максимум из 3-х строк, с учетом этих 2-х

На С можно это уложить в одно выражение...

Только сначала автор должен уточнить, может, Бейсик?

ой! прошу прощения - забыла указать, что это Си

Вроде вот так должно быть...

#include <stdio.h>

int main() {

  int i, f;
  unsigned int n = 0xA7; // То, что надо сконвертировать
  unsigned int b[4] = {0, 2, 1, 3};

  for(i = 0; i < 8*sizeof(int); i += 2) {

    f = (n >> i) & 3;
    n = (n & (~(3 << i))) | (b[f] << i);

  }
  printf("n = %u\n", n);
  return 0;

}

Объясни пожалуйста, для чего мы используем массив b?
И что происходит в следующих 3-х строках (я не смогла разобраться в этом....)

единственное, что поняла - в цикле мы сдвигаем число на определённое кол-во бит - а зачем? что значит побитовое отрицание 3? почему такое условие в цикле - 8*sizeof(int)? почему такой шаг?

Ну вот давай посмотрим на примере конкретного числа... Не будем уходить далеко от примера, возьмём то же самое число 0xA7:


Теперь смотри... Нам надо поменять местами пары битов, так? Какие возможны сочетания 2-х бит? 00, 01, 10, 11 - это как раз индексы массива b... А значения массива b - это значения уже изменённого порядка битов, т.е., 00 меняем местами - получаем 00, результат = 0, 01 меняем биты местами - получаем 10 = 2, и т.д.

Что происходит дальше? Находим f, сдвигая само число на i бит вправо (то есть, добиваясь того, чтобы те биты, которые надо менять местами, были двумя самыми правыми битами), и "умножаем" полученное число логически на 3, т.е. применяем операцию AND:

Учти, при этом значение n не изменяется, работа производится с его копией!!! Это важно...

Теперь в f содержится значение неизменённых битов... Тогда b[f] будет содержать значение уже изменённого порядка битов...

Теперь самая сложная строка:

n = (n & (~(3 << i))) | (b[f] << i);

Здесь делается следующее... Ну, значение изменённого порядка битов мы нашли, только его же надо еще поставить на нужное место в числе, правда? А где это нужное место? Правильно, на первой итерации - это прямо последние 2 бита, для второй - 2 предыдущих, т.е. 2 и 3, считая от 0... В общем случае - это биты, находящиеся на тех же местах, что и единичные биты в (3 << i)...

Приближаемся к развязке этого выражения: допустим, у тебя есть число n = 00001011, и тебе надо обнулить значения выделенных битов, оставляя все остальные неизменными; что надо для этого сделать? Надо произвести AND с инвертированной маской битов, т.е., маска = 00001100, инвертированная маска = 11110011, и когда мы сделаем AND, то все биты, кроме нулевых останутся теми же, а нулевые - сбросятся, потому что 0 and X = 0...

Ты думаешь, а зачем я это все рассказываю? Да потому что в приведённой выше строке на С, я делаю именно это: значению n производится операция and со сдвинуто1 на нужное количество бит и инвертированной 3-кой, этим мы гарантированно сбрасываем те биты, куда должны будем записать значение b[f], а потом к этому вот промежуточному значению "прибавляем" (операция OR) сдвинутое опять же на нужное число бит значение b[f]...

Я понимаю, что это все выглядит очень сложно, но все-таки постарайся понять, это основы работы с битами, без этого более сложные операции (а они могут быть ГОРАЗДО более сложными, поверь мне) ты не сможешь понимать...

а почему используется именно 8*sizeof(int) в условии завершения цикла?

А чтобы не заниматься работой, которую должен делать компилятор... Вот ты знаешь, сколько на твоем компиляторе байт занимает int? А sizeof(int) знает... А битов в числе, значит, содержится в 8 раз больше... Гарантированно обработаются все биты.

Почему нам нужно, чтобы биты, которые нужно менять, были двумя самыми правыми и относительно чего они будут самыми правыми?

Потому что так проще всего их выделить...

Не понял... Что значит, "относительно чего"? Скажем так, это будут LSB - Less Significant Bits (биты с наименьшим весом, нулевой и первый)

почему логическое умножение именно на 3?

Сколько битов нам надо выделить, помнишь? Где они размещаются после сдвига (т.е., куда мы их переместили), помнишь? Тогда расскажи мне, на какую маску надо умножать, чтобы ТОЛЬКО эти 2 бита остались такими, какие они сейчас, а все остальные гарантированно сбросились в 0?

а можно это записать в иной форме, более наглядной и более простой для понимания?

Можно, но тогда сразу говори в следующий раз, что тебе надо не на С, а на Бейсике, с использованием операторов С...

int f, inv, mask, inv_mask;
...
    f = (n >> i) & 3;
    inv = b[f];
    mask = (3 << i);
    inv_mask = ~mask;
    n = n & inv_mask;
    n = n | (inv << i);